Skip to main content
Contents Index Calc Dark Mode Prev Up Next \(\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R}
\newcommand{\mc}[1]{\multicolumn{1}{c}{#1}}
\DeclareMathOperator{\cone}{cone} \newcommand{\x}{\mathbf x} \newcommand{\y}{\mathbf y} \newcommand{\z}{\mathbf z}
\newcommand{\vc}{\mathbf c} \newcommand{\vb}{\mathbf b}
\newcommand{\vs}{\mathbf s} \newcommand{\vt}{\mathbf t} \newcommand{\p}{\mathbf p} \newcommand{\q}{\mathbf q}
\newcommand{\ec}[1]{\enclose{circle}{#1}} \DeclareMathOperator{\lcm}{lcm} \newcommand{\eb}[1]{\enclose{box}{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 8.3 Solving Integer Optimization Problems with Sage
In
Section 2.4 and
Section 3.3 , we solved canonical and noncanonical 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.
Activity 8.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 noncanonical 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:
Activity 8.3.2 .
Solve:
\begin{align*}
\textbf{Maximize: } f(\mathbf{x}) &= 3x_1+2x_2\\
\textbf{subject to: } 4x_1+5x_2 &\leq 39\\
7x_1+3x_2 &\geq 20\\
x_2 &\leq 5\\
x_1, x_2 & \text{ are integers.}
\end{align*}
