Section8.3Solving Integer Optimization Problems with Sage
In Section 2.4 and Section 3.3, we solved canonical and non-canonical linear optimization problems. Solving such problems by hand could be tedious, and the techniques to solve integer optimization problems are even more involved. In this section, we solve integer optimization problems using sage.
Since integer optimization is more difficult computationally than linear optimization, we use different commands to find solutions. Rather than use InteractiveLPProblem, we use MixedIntegerLinearProgram.
Activity8.3.1.
Say we want to solve the integer optimization problem:
\begin{align*}
\textbf{Minimize: } f(\mathbf{x}) & = 3x_1+4x_2+2x_3\\
\textbf{subject to: } x_1& \leq 7\\
x_2+x_3& \geq 5\\
5x_1+3x_2+2x_3& \leq 37\\
x_1, x_2, x_3& \geq 0,\text{ and are integers}.
\end{align*}
(a)
Record this non-canonical problem using Sage:
(b)
We can then find the optimal solution:
(c)
We could also minimize \(f\) if we chose:
(d)
We could also have solved the linear relaxation of the original problem \(f\) if we chose:
