Maximizing or Minimizing Systems of Linear Inequalities with Linear Programming

## Description

Here, we will maximize x and y where $f = x + 3y$ and x and y are restricted by the following system of linear inequalities with a MixedIntegerLinearProgram
object:

(1)
\begin{align} 1.5 - 2x &\geq y \\ 1 - x &\geq y \\ 1 - x &\leq 2y \\ x &\geq 0 \\ y &\geq 0 \end{align}

## Sage Cell

We'll go over this line-by-line:

Line 1: We create a new MixedIntegerLinearProgram with the name LP. We then tell it to maximize the objective by setting maximization to true. If we wanted to minimize the objective, we would set it to false.

Line 2: We make a new variable named x in LP. x is actually an infinite array of variables, so all variables used in the program will just be different indices of x. An index must be an integer greater than or equal to 0, but the don't have to be consecutive. In the program we use x[1] and x[2] for simplicity's sake, but we could just as easily have used x[42] and x[9999999] and been fine.

Line 3: We set the objective we want to optimize. The objective is in normal Sage notation, except $x$ and $y$ have been replaced with x{1] and x[2], respectively. If the objective is unset, the program will automatically try to maximize the variable with the lowest index.

Lines 4-8: We set the constraints of the linear system of inequalities here. Again, we use normal Sage notation, but replace $x$ and $y$ with x[1] and x[2].

Lines 9-10: Here, we print the answer to our problem. LP.solve() gives us our optimized value of $f$ in $f = x + 3y$, while LP.get_values( x ) gives us all initialized values in the array x, from lowest to highest index. Since we only used two values, we are only returned two values.

#### Code

LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable()
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
print LP.solve()
print LP.get_values( x )


#### Minimization

Here we will use the exact same objective and system of inequalities, except we wish to minimize $f = x + 3y$. This is accomplished simply by setting maximization to false when making a MixedIntegerLinearProgram object.

#### Code

LP = MixedIntegerLinearProgram (maximization = false)
x = LP.new_variable()
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
print LP.solve()
print LP.get_values( x )


## Options

#### Multiple Variable Letters

We can set different variable letters in the same object; this also means we'll have to call .get_values() multiple times, as it only works with one array of variables at a time.

#### Code

LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable()
y = LP.new_variable()
LP.set_objective(x[1] + 3*y[1])
LP.add_constraint( 1.5 - 2*x[1] >= y[1] )
LP.add_constraint( 1 - x[1] >= y[1] )
LP.add_constraint( 1 - x[1] <= 2*y[1] )
print LP.solve()
print LP.get_values( x )
print LP.get_values( y )


#### .show()

Using .show will provide a human-readable summary of the object:

#### Code

LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable()
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
LP.show()
print LP.solve()
print LP.get_values( x )


#### Setting Nonnegativity

If we set nonnegative = true when declaring a new array of variables, we don't need a >= 0 constraint for the set.

#### Code

LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable(nonnegative = true)
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
print LP.solve()
print LP.get_values( x )


#### Integer-only Solutions

We can tell our program that specific variables may only be integers in the optimization, using integer=true when declaring a new variable:

#### Code

LP = MixedIntegerLinearProgram (maximization = true)
x = LP.new_variable(nonnegative = true, integer=true)
LP.set_objective(x[1] + 3*x[2])
LP.add_constraint( 1.5 - 2*x[1] >= x[2] )
LP.add_constraint( 1 - x[1] >= x[2] )
LP.add_constraint( 1 - x[1] <= 2*x[2] )
print LP.solve()
print LP.get_values( x )


## Tags

Primary Tags:

Secondary Tags:

A list of possible tags can be found at The WeBWorK Open Problem Library. For linear algebra tags see the Curated Courses Project.

## Related Cells

Any related cells go here. Provide a link to the page containing the information about the cell.