\chapter{Integer Linear Programming}\label{C:Integer_Linear_Programming}
\section{An Introduction to Integer Linear Programming and the Branch and Bound Method}\label{S:Intro_IP_Branch_and_Bound_Method}
\setcounter{progress_ck_counter}{0}

\noi For many linear programming applications, we seek solutions in which
all decision variables are integer-valued. We have already discovered that, under
certain conditions, the solution of a minimum cost network flow problem has
this property. In this section we discover a general technique for solving
linear programming problems that require integer-valued solutions. Such an LP is
called an \emph{integer linear programming problem}\index{integer linear programming problem (ILP)}, or ILP.

\subsection{A Simple Example}\label{S:Int_Prog_relaxation}

\noi To gain a sense of how to solve ILPs, we first consider a simple
production problem faced by the
\emph{Great Lakes Kayak Company}\index{integer linear programming problem!Great Lakes Kayak Company ILP} (GLKC), which manufactures two types of kayaks, one
a recreational, i.e., ``rec'' kayak, suitable for use on inland lakes and calm rivers, and
the other a larger sea kayak suitable for open water paddling on the Great Lakes and the ocean.
Both kayaks are comprised of two grades of plastic, labeled
grades A and B. Each ``rec'' kayak requires 20 pounds of each grade plastic and sells for \$300. The sea kayak, on the other hand, requires 10 pounds of grade A and and 30 pounds of grade B and sells for \$400. Suppose the daily availability of the plastic is given by 60 pounds for grade A and 90 pounds for grade B. Under the assumption the company sells all the kayaks that
it produces, we wish to determine how many kayaks of each type should be produced, subject to
the given constraints, so
as to maximize daily revenue.

\newpar
Letting $x_1$ and $x_2$ denote the numbers of produced rec kayaks and sea kayaks,
respectively, we can easily formulate GLKC's goal as that of solving ILP
(\ref{E:Int_Prog_kayak1}):
	
\begin{align}\label{E:Int_Prog_kayak1}
 \mbox{maximize } z &=3x_1 +4x_2  \\
	\mbox{ subject to} \notag\\
	2x_1+x_2 &\leq 6 \notag \\
	2x_1 + 3 x_2 &\leq 9  \notag \\
	x_1, x_2 \geq 0 &; x_1,x_2 \in \Z. \notag
	\end{align}

\noi Here, $z$ represents the revenue, measured in hundreds of dollars. Note, in particular,
we require that $x_1$ and $x_2$ be integer-valued in the solution.

\newpar
Figure \ref{Fi:Int_Prog_kayak_solution_window} illustrates the candidate solution values of $x_1$ and $x_2$ for ILP \ref{E:Int_Prog_kayak1}, namely the ordered pairs in the shaded region whose entries
are integer-valued. We call such candidates, feasible
\emph{lattice points}.\index{lattice points}

\newpar
One approach to solving ILP \ref{E:Int_Prog_kayak1} is of course to merely evaluate the objective
function at all feasible lattice points and to determine which produces the largest objective value. If the inequalities that comprise the ILP produce a bounded region, then there exist only a finite number of candidates from which to choose. For small-scale problems, this approach is satisfactory, but for larger-scale problems, it proves extremely inefficient, thereby motivating the need for different methods.

\subsection{The Relaxation of an ILP}\label{S:Int_Prog_relaxation}

\noi
To any ILP, there corresponds an LP, called the \emph{relaxation}\index{relaxation|see{integer linear programming problem!relaxation}} of the ILP, which is formed by
using the ILP but eliminating the constraint requirement that decision variables be integer-valued.
For (\ref{E:Int_Prog_kayak1}), the relaxation solution is straightforward to
compute and is given by
\begin{equation}\label{E:Int_Prog_kayak_solution}
	\vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}=\begin{bmatrix} 9/4 \\ 3/2 \end{bmatrix}=
\begin{bmatrix} 2.25 \\ 1.5 \end{bmatrix} \mbox{ and} \quad z=\frac{51}{4}=12.75.
\end{equation}

\noi Because (\ref{E:Int_Prog_kayak1}) is a maximization problem and because the constraints in (\ref{E:Int_Prog_kayak1}) are more restrictive than those in the
relaxation, we may be assured that the objective value in
the solution of (\ref{E:Int_Prog_kayak1}) is no larger than $z=12.75$. This principle holds in general:  The optimal objective value of an ILP involving maximization is no larger than that of the corresponding relaxation LP. Consequently, if the relaxation has a solution whose decision variables happen to be integer-valued, then this
solution coincides with that of the original ILP. As we shall discover, this fact proves crucial for developing a means of solving ILPs.

\newpar
Usually, the relaxation produces a solution in which decision variables are not integer-valued.
Figure \ref{Fi:Int_Prog_kayak_solution_window} illustrates such an outcome for the GLKC LP. While the shaded portion represents the feasible region for the relaxation LP, only the lattice points in this feasible region are also feasible for the ILP.


\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\psfrag{solution}[Bc][Bc]{$\left(\frac{9}{4} \frac{3}{2} \right)$}
\includegraphics[width=.7 \linewidth]{images/f06x01x01.eps}
\caption{Feasible region and solution for the GLKC ILP relaxation.}\label{Fi:Int_Prog_kayak_solution_window}
\end{figure}

\newpar
A naive approach to solving the ILP consists of rounding off the relaxation solution to
the nearest lattice point. Unfortunately,
this approach can lead to decision variable values that do not correspond to the optimal solution
or are infeasible to begin with.

\begin{progress_ck}
Determine the solution of ILP (\ref{E:Int_Prog_kayak1}) by graphical inspection of Figure
\ref{Fi:Int_Prog_kayak_solution_window}. How does this solution compare to that of the relaxation or to that obtained by rounding off the relaxation solution?
\end{progress_ck}

\subsection{The Branch and Bound Method}\label{S:Int_Prog_branch_and_bound}

\noi The \emph{branch and bound method}\index{branch and bound method} is a technique for solving an ILP, which is based upon solving a carefully chosen sequence of closely related LPs. The first step of the method
 requires solving the corresponding relaxation LP. If the solution $(x_1,x_2)$ of the relaxation is integer valued, then this
solution coincides with that of the ILP. If not, the original feasible region is partitioned into two disjoint (i.e., non-overlapping) regions, neither of which contains $(x_1,x_2)$. Each of these
two regions gives rise to a new LP, which is merely the original LP together
with an additional constraint. These two new LPs are then solved, a process we shall refer to
as \emph{branching}. If an integer-valued solution arises from one of these new LPs, then it becomes a candidate solution for the original ILP. If an integer-valued solution does not arise, then
the corresponding region is again partitioned, and the process repeats itself. Eventually, all cases are exhausted, and we obtain an optimal solution for the ILP.

\newpar
We illustrate the technique by applying it to the GLKC ILP. The solution of the relaxation is given by
\begin{equation*}
	\vecx=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}=\begin{bmatrix} 2.25 \\ 1.5 \end{bmatrix}
\mbox{ and} \quad z=12.75.
\end{equation*}
Neither of the decision variables in this solution is integer-valued.
To partition the feasible region into two disjoint regions neither of
which contains $\left(2.25,1.5 \right)$, we have a choice of \emph{branching} on
either of the decision variables in a way that removes the given solution value from consideration
in a newly designed LP.

\newpar
By \emph{branching}\index{branch and bound method!branching} at a particular stage on a decision variable $x_i$
in an LP's solution, we simply mean we solve two new LPs. If
$ \tilde{x}_i $ denotes the value of the decision variable $x_i$ in the LPs solution, which is not integer-valued
at that stage, the first new LP is
the LP at that stage, together with the added constraint that
$x_i$ is greater than or equal to the smallest integer greater than $\tilde{x}_i$.
The second LP is defined analogously, but the added constraint is instead that $x_i$ is less
than or equal to the largest integer less than $\tilde{x}_i$.

\newpar
Here we elect to branch on $x_1$. To eliminate
$\ds x_1=2.25$ from arising in a new solution, we consider two new LPs:

	\begin{align}\label{E:Int_Prog_branch1_1}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	x_1, x_2\geq 0 \notag
	\end{align}
and
	\begin{align}\label{E:Int_Prog_branch1_2}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \geq 3  \notag \\
	x_1, x_2\geq 0 . \notag
	\end{align}
Note that
the first of these LPs is nothing more than our original LP using that portion of its feasible region in Figure \ref{Fi:Int_Prog_kayak_branch} that falls to the left of $x_1=2$. The second LP uses that portion to
the right of $x_1=3$.

\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f06x01x02.eps}
\caption{Branching on $x_1$ in the feasible region of the relaxation LP.}\label{Fi:Int_Prog_kayak_branch}
\end{figure}

\newpar
Solving LPs (\ref{E:Int_Prog_branch1_1}) and (\ref{E:Int_Prog_branch1_2}) we
obtain the following solutions, respectively:
	\be
	\item
		$\ds
		x_1=2, \quad x_2=  1.\bar{6}  ,  \quad
		\mbox{and} \quad z=12.\bar{6};
		$
	\item
		$\ds
		x_1=3 \quad x_2=0, \quad
		\mbox{and} \quad z=9.
		$
	\ee
We now branch again by using these results and adding more constraints
to the corresponding LPs. However, the solution of (\ref{E:Int_Prog_branch1_2}) is integer-valued, so adding more constraints to (\ref{E:Int_Prog_branch1_2}) can only produce an LP whose optimal objective
value is no greater than 9. For this reason, we label $\vecx=\begin{bmatrix} 3 \\ 0 \end{bmatrix}$, which corresponds to $z=9$, a \emph{candidate}\index{branch and bound method!candidate solution} for the optimal solution of (\ref{E:Int_Prog_kayak_solution}), and we branch no further on LP (\ref{E:Int_Prog_branch1_2}).

\newpar
The solution of (\ref{E:Int_Prog_branch1_1}) produces a value of $x_2$ that is not integer-valued, so we branch on $x_2$ and form two new LPs that arise by eliminating $x_2=1.\bar{6}$ from consideration. These
are given as follows:

	\begin{align}\label{E:Int_Prog_branch2_1}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	\x \x x_2 \leq 1  \notag \\
	x_1, x_2\geq 0 \notag
	\end{align}
	and
	\begin{align}\label{E:Int_Prog_branch2_2}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	\x \x x_2 \geq 2  \notag \\
	x_1, x_2\geq 0. \notag
	\end{align}
	
\newpar
The respective solutions of (\ref{E:Int_Prog_branch2_1}) and (\ref{E:Int_Prog_branch2_2}) are as
follows:
\be
	\item
		$\ds
		x_1=2, \quad x_2=1,  \quad
		\mbox{and} \quad z=10;
		$
	\item
		$\ds
		x_1=1.5, \quad  x_2=2, \quad
		\mbox{and} \quad z=12.5.
		$
	\ee

\noi These results indicate that $\vecx=\begin{bmatrix} 2 \\ 1 \end{bmatrix}$ is also a candidate solution. Because its objective value is larger than that
 produced by the first candidate solution, $\ds \vecx=\begin{bmatrix} 3 \\ 0 \end{bmatrix}$, we
 eliminate the first candidate from further consideration.

\newpar
The solution of (\ref{E:Int_Prog_branch2_2}) produces a value of $x_1$ that is not integer-valued, so we branch on $x_1$, creating two new LPs that arise by eliminating $x_1=1.5$ from consideration:

	\begin{align}\label{E:Int_Prog_branch3_1}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	\x \x x_2 \geq 2  \notag \\
    \x \x x_1 \leq 1  \notag \\
	x_1, x_2\geq 0 \notag
	\end{align}
	and
	\begin{align}\label{E:Int_Prog_branch3_2}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	\x \x x_2 \geq 2  \notag \\
    \x \x x_1 \geq 2  \notag \\
	x_1, x_2\geq 0. \notag
	\end{align}
	
\noi
Clearly, the first constraint in (\ref{E:Int_Prog_branch3_1}) is redundant in light of the newly added, more restrictive
third constraint. Moreover, the first and third constraints in (\ref{E:Int_Prog_branch3_2})
can be combined into the equality constraint, $x_1=2$. We only express the constraints for each LP in this manner so as to emphasize the manner in which we are adding more and more constraints to the original LP at each stage of branching.

\newpar
The second of the preceding LPs is infeasible. The first has its solution given by
\begin{equation*}
		x_1=1, \quad  x_2=2.\bar{3}, \quad
		\mbox{and} \quad z=12.\bar{3}.
\end{equation*}

\newpar
Branching on $x_2$ in (\ref{E:Int_Prog_branch3_1}) gives two more LPs:

\begin{align}\label{E:Int_Prog_branch4_1}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	\x \x x_2 \geq 2  \notag \\
    \x \x x_1 \leq 1  \notag \\
    \x \x x_2 \leq 2  \notag \\
	x_1, x_2\geq 0, \notag
	\end{align}
together with

\begin{align}\label{E:Int_Prog_branch4_2}
	\mbox{maximize } z =3x_1& +4x_2  \\
	\mbox{ subject to} \notag\\
	\mbox{Original constraints plus} \notag \\
	\x \x x_1 \leq 2  \notag \\
	\x \x x_2 \geq 2  \notag \\
    \x \x x_1 \leq 1  \notag \\
    \x \x x_2 \geq 3  \notag \\
	x_1, x_2\geq 0. \notag
	\end{align}

\newpar
LPs (\ref{E:Int_Prog_branch4_1}) and (\ref{E:Int_Prog_branch4_2}) produce
solutions of $\ds \vecx=\begin{bmatrix}  1 \\ 2 \end{bmatrix}$
and $\ds \vecx=\begin{bmatrix}  0 \\ 3 \end{bmatrix}$, respectively,
with corresponding objective values of $z=11$ and $z=12$. Both are candidate solutions,
so we branch no further.

\newpar
At this stage the branching process is complete, and we have determined
four candidate solutions exist. The first of these, $\ds \vecx=\begin{bmatrix} 3 \\ 0 \end{bmatrix}$,
has already been eliminated from consideration. Of the remaining three,
$\ds \vecx=\begin{bmatrix} 2 \\ 1 \end{bmatrix}$, $\ds \vecx=\begin{bmatrix} 1 \\ 2 \end{bmatrix}$,
and $\ds \vecx=\begin{bmatrix} 0 \\ 3 \end{bmatrix}$, the last yields the largest
objective value of $z=12$. Thus, ILP (\ref{E:Int_Prog_kayak1}) has its solution given by
$\ds \vecx=\begin{bmatrix} 0 \\ 3 \end{bmatrix}$ so that GLKC should produce no ``rec'' kayaks and
three sea kayaks.

\newpar
The branching process outlined in the preceding discussion can be visualized through construction of a \emph{tree diagram}\index{branch and bound method!tree diagram} as shown in Figure
\ref{Fi:TreeDiagram}. When passing from one LP to an LP in a lower-level branch, we merely add a new constraint.
\newpage

\begin{minipage}[t]{\linewidth}
\raggedleft
\raisebox{-4.5in}{\scalebox{.8}{\input{branch_and_bound_tree_diagram}}}
\end{minipage}

\newpar
\begin{figure}[h]
\centering
\caption{Tree diagram for ILP (\ref{E:Int_Prog_kayak1}).}\label{Fi:TreeDiagram}
\end{figure}

\newpage
\noi
Here are some points to bear in mind when using the branch and bound method.
	\be
	\item Create a tree diagram with nodes and arrows. Each node should clearly
	convey the LP being solved, together with its optimal solution, especially
	the objective function value.
	\item Along each branch, or edge, of the tree diagram connecting two nodes,
	indicate the constraint that is added to the LP
	at the top node in order to formulate the LP of the bottom node.
	\item Before branching on a particular variable, pause to consider whether
	doing so is absolutely necessary. Remember that in a maximization (resp. minimization) problem, objective
	values can only decrease (resp. increase) from one node to a lower node connected along a particular branch.
	\item At a certain point in the solution process, all possible cases along a branch become
	exhausted and other previously constructed branches must be examined
	for candidate solutions. \emph{Backtracking},\index{branch and bound method!backtracking} the process of revisiting	
	unresolved branches in exactly the reverse order they were created, is a systematic
	means for carrying out this process.
	\ee
	
\subsection{Practicing the Branch and Bound Method with Maple}\label{S:Int_Prog_branch_and_bound}\index{branch and bound method!practicing with Maple}

\noi Practicing the branch and bound method is straightforward using Maple's \mf{LPSolve} command. We first solve the relaxation LP and then progressively add more inequalities to the constraint list until the ILP is solved. Here is syntax from a worksheet, \textbf{ Practicing the Branch and Bound Method.mw} that solves the relaxation of the GLKC ILP, along with the LP formed by adding the inequality $x_1 \geq 3$ to the relaxation at the first branch.

\begin{maplelist}
\item \mf{restart:with(LinearAlgebra):with(Optimization):}
\item \mf{c:= Vector[row]([3,4]);
\newline \# Enter objective coefficients.}
\mo{c:=\begin{bmatrix} 3 & 4 \end{bmatrix}}
\item \mf{A:=Matrix(2,2,[2,1,2,3]); \newline \# Enter constraint matrix.}
\mo{A:=\begin{bmatrix} 2 & 1 \\ 2 & 3 \end{bmatrix}}
\item \mf{b:=<6,9>; \newline \# Enter constraint bounds.}
\mo{b:=\begin{bmatrix} 6 \\ 9 \end{bmatrix}}
\item \mf{x:=<x1,x2>; \newline \# Create vector of decision variables.}
\mo{x:=\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}}
\item \mf{ConstraintMatrix:=A.x-b:}
\item \mf{Constraints:=seq(ConstraintMatrix[i]<=0,i=1..2);
\newline \newline \# Form constraints by extracting components of Ax-b as 
\newline a sequence and setting each component less than or 
\newline equal to 0.}
\mo{constraints := 2x_1+x_2-6<=0, 2x_1+3x_2-9<=0}
\item \mf{LPSolve(c.x,[constraints],assume='nonnegative',
\newline 'maximize'); \# Solve relaxation.}
\mo{ [12.750000000000, [x_1 = 2.25000000000000000, x_2 = 1.50000000000000022]]}
\item \mf{LPSolve(c.x,[constraints,x1 >=3],assume='nonnegative','maximize');
\newline \# Add an inequality to form a new list of
constraints. 
\newline Then solve the resulting LP.}
\mo{ [9, [x1 = 3, x2 = 0]]}
\end{maplelist}

\newpar
Remaining LPs that result from further branching are handled in a similar manner so as
to obtain the final solution of $\ds \vecx=\begin{bmatrix} 0 \\ 3 \end{bmatrix}$.

\subsection{Binary and Mixed Integer Linear Programming}\label{S:Int_Prog_Binary_and_MILP}

\noi Two very important subclasses of ILPs arise frequently in real-world applications.
The first consists of \emph{binary linear programming problem}, or BLPs\index{integer linear programming problem!binary linear programming problem}, in which each decision variable must assume the value of zero or one in the final solution. The second is comprised of \emph{mixed integer linear programming problems}\index{integer linear programming problem!mixed integer linear programming problem}, or MILPs, in which some, but not all decision variables must be integer-valued in the solution. Solving mixed MILPs is easily accomplished using the branch and bound method, with branching done only on those variables required to be integer-valued.

\newpar
For example, consider the mixed MILP,
\begin{align}\label{E:Int_Prog_mixed_ILP}
 \mbox{maximize } z &=x_1+3x_2+3x_3  \\
	\mbox{ subject to} \notag\\
	x_1+3x_2 +2x_3&\leq 7 \notag \\
	2x_1 + 2 x_2+x_3 &\leq 11  \notag \\
	x_1, x_2,x_3 \geq 0 &; x_1, x_3 \in \Z. \notag
	\end{align}
The solution to the relaxation
of (\ref{E:Int_Prog_mixed_ILP} ) is given by $\ds \vecx=\begin{bmatrix} 0 \\ 0 \\ 3.5 \end{bmatrix}$ with corresponding objective value, $z=31.5$. Since only $x_1$ and $x_3$ must be integer-valued, we restrict all branching to these two variables. As the former is already integer-valued in the relaxed solution, we branch on $x_3$ and consider the original constraints together with two different possibilities for $x_3$:
$x_3 \leq 3$ and $x_3 \geq 4$. The former case leads to a candidate solution for the MILP; the latter
leads to infeasibility. The candidate solution is optimal and is labeled in Figure \ref{Fi:MILPTreeDiagram}.
%Figure
%\ref{Fi:Int_Prog_mixed_ILP}.

\scalebox{.9}{\begin{minipage}[l]{1\linewidth}
\input{branch_and_bound_tree_diagram2}
\end{minipage}}

\newpar
\begin{figure}[h]
\centering
\caption{Tree diagram for MILP (\ref{E:Int_Prog_mixed_ILP}).}\label{Fi:MILPTreeDiagram}
\end{figure}

\vspace{.3in}
\subsection{Solving ILPs Directly with Maple}\label{S:Int_Prog_Maple_Excel}\index{integer linear programming problem!solving with Maple}

\noi While Maple's \mf{LPSolve} command is useful for practicing the branch and bound method, the command already has built-in options for solving ILPs directly. To solve an ILP having no sign restrictions, simply add the option \ma{assume=integer}. For an ILP requiring nonnegative decision variable values, add \ma{assume=nonnegint} instead. For a MILP, the option
\mf{integervariables=[\ma{list}]} specifies which particular variables are required to
take on integer variables. For a BLP, adding \ma{assume=binary} requires
all decision variables equal to 0 or 1 in the solution, whereas
\mf{binaryvariables=[\ma{list}]} specifies which subset of the decision variables have
binary values. Finally, the option \ma{depthlimit=\emph{n}} specifies the number
of branching levels used by Maple in its solution process. For the GLKC ILP, four branching levels were required. Since Maple's default number is three, an error message is returned
 unless the \ma{depthlimit} is assigned a sufficiently large value.

\newpar
Here is a sample worksheet illustrating the use of these command options. In the
first example, Maple solves
 the GLKC ILP (\ref{E:Int_Prog_kayak1}) using the matrix inequality form
 as discussed in Section \ref{S:LP_Prototype_Standard_Form_Matrix_Form}. In the second,
 Maple solves MILP (\ref{E:Int_Prog_mixed_ILP}).

\begin{maplelist}
\item \mf{restart:with(LinearAlgebra):with(Optimization):}
\item \mf{c:=Vector[row]([3,4]); \newline \# Create vector of objective coefficients.}
\mo{c:=\begin{bmatrix} 3 & 4 \end{bmatrix}}
\item \mf{A:=Matrix(2,2,[2,1,2,3]); \newline \# Matrix of constraint coefficients.}
\mo{A:=\begin{bmatrix} 2 & 1 \\ 2 & 3 \end{bmatrix}}
\item \mf{b:=<6,9>; \newline \# Constraint bounds.}
\mo{b:=\begin{bmatrix} 6 \\ 9 \end{bmatrix}}
\item \mf{LPSolve(c, [A, b], assume = nonnegint, 'maximize', depthlimit = 5);}
\mo{\begin{bmatrix} 12 & \begin{bmatrix} 0 \\ 3 \end{bmatrix} \end{bmatrix}}
\item \mf{LPSolve(x1+3x2+3x3,[x1+3x2+2x3<=7, 2x1+2x2+x3<=11],
\newline assume=nonnegative, integervariables=[x1,x3],'maximize');
\newline \# Solve the LP, specifying x1 and x3 are integer-valued.}
\mo{[10.000000000000, [x_1 = 0, x_2 = .333333333333333315, x3 = 3]] }
\end{maplelist}

\subsection{An Application of Integer Linear Programming: The Traveling Salesperson Problem}\label{S:Int_Prog_TSP}\index{integer linear programming problem!traveling salesperson problem}

\noi Integer linear programming has an enormous, diverse number of applications. One of the most
widely studied problems in this area consists of the ``Traveling Salesperson Problem,'' or TSP.

\newpar
The TSP seeks to determine the minimum distance an individual must travel in order to begin at
one location, pass through each of a list of other intermediate
locations exactly one time, and return to the starting point. Such a round trip is known as a \emph{tour}\index{tour}.

\newpar
We will consider the general setting consisting of $n$ destinations, where
$n \geq 2$. Figure \ref{Fi:Int_Prog_TSP_tour} illustrates an example of a tour for the particular case of $n=4$. We can represent this example through the notation $1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 1$.

\begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f06x01x03.eps}
\caption{Tour consisting of 4 destinations.}\label{Fi:Int_Prog_TSP_tour}
\end{figure}

\newpar
To solve the TSP, we first define the binary decision variables,
$\ds x_{ij}$, where $1 \leq i,j \leq n$. A value of $x_{ij}=1$ in the final solution indicates that travel takes place from destination $i$ to $j$; a value of 0 indicates that no such travel takes place. That no travel takes place from a destination to itself dictates that the problem
 formulation must guarantee a solution in which $x_{ii}=0$, for
$1 \leq i \leq n$.

\newpar
Each location is the starting point from which one travels to a new destination, a condition
expressed as $\ds \sum_{j=1}^n x_{ij}=1$ for $1 \leq i \leq n$. Similarly, each destination
is also ending point of travel from a previous destination so that
$\ds \sum_{j=1}^n x_{ji}=1$ for $1 \leq i \leq n$. We will denote the distance between locations
$i$ and $j$, where $1 \leq i,j \leq n$, by $d_{ij}$. Of course, $d_{ij}=d_{ji}$, and to ensure that
 $x_{ii}=0$ for $1 \leq i \leq n$, we set each $d_{ii}=M$, where $M$ is a number much larger
 than any distance between two different destinations. With this notation, the total distance
 traveled is given by $\ds D= \sum_{i=1}^n \sum_{j=1}^n d_{ij}x_{ij}$.

\newpar At first glance, it might
then appear that the solution to the TSP is the same as that obtained by solving the BLP

\begin{align}\label{E:Int_Prog_TSP1}
 \mbox{minimize } D &= \sum_{i=1}^n \sum_{j=1}^n d_{ij}x_{ij}  \\
	\mbox{ subject to} \notag \\
	\sum_{i=1}^n x_{ij}&=1 , \quad 1 \leq i \leq n \notag \\
	\sum_{j=1}^n x_{ji}&=1 , \quad 1  \leq i \leq n \notag \\
	x_{i,j} &\in \{0,1\} , \quad  1 \leq i,j \leq n. \notag
	\end{align}

\newpar
Unfortunately, (\ref{E:Int_Prog_TSP1}) possesses a major problem. Namely, it includes
as feasible solutions, decision variable values that do not correspond to tours, but instead
to combinations of \emph{subtours}. A \emph{subtour}\index{subtour} is a tour of a proper subset
of the set of destinations.

\newpar
Figure \ref{Fi:TSP_subtours} illustrates an example consisting of two subtours
of  $n=4$ destinations. In terms of notation, $1 \rightarrow 3 \rightarrow 1$ and
 $ 2 \rightarrow 4 \rightarrow 2$. The decision variable values equal to 1 are precisely
 $x_{13}$, $x_{31}$, $x_{24}$, and $x_{42}$. These values satisfy the feasibility criteria
 in (\ref{E:Int_Prog_TSP1}), but they do not form a tour.

 \begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f06x01x04.eps}
\caption{Two subtours of 4 destinations.}\label{Fi:TSP_subtours}
\end{figure}

\newpar
To guarantee that only tours, and not subtours, are feasible, we must introduce more decision
variables and use these to add additional constraints to (\ref{E:Int_Prog_TSP1}). We label these
decision variables as $p_i$, where $1 \leq i \leq n$, and let each $p_i$ denote the position of destination $i$ in a tour. For example, if  $1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 1$, then
$p_1=1$, $p_3=2$, $p_2=3$, and $p_4=4$. Note that for each $i$, $1 \leq p_i \leq n$. Furthermore, to solve the
TSP, we may assume we start at location 1, meaning $p_1=1$.

\newpar
As we shall discover, a family of additional constraints that guarantees only tours, and not combinations of subtours, are feasible in (\ref{E:Int_Prog_TSP1}) can be formulated as
\begin{equation}\label{E:Int_Prog_TSP_NewConstraints}
p_i - p_j +1 \leq (n-1)(1-x_{ij}) \mbox{ where } 2 \leq i,j \leq n.
\end{equation}

\newpar
To verify that all tours satisfy (\ref{E:Int_Prog_TSP_NewConstraints}), we consider two
cases for each pair of distinct destinations, $i$ and $j$, in a tour, where
$2 \leq i,j \leq n$. In the first case $x_{ij}=1$, meaning direct travel takes place from destination $i$ to $j$ and $p_j-p_i=1$. Therefore,
\begin{align*}
%\label{E:Int_Prog_TSP_NewConstraints_Feasible1}
p_i - p_j +1 &=0 \notag \\
            &=  (n-1)(1-x_{ij}) \notag
 \end{align*}
 so that (\ref{E:Int_Prog_TSP_NewConstraints}) holds. In the second case
$x_{ij}=0$, and no such direct travel takes
place. Since $p_1=1$ and $2 \leq i,j \leq n$, we have $p_i-p_j \leq n-2$ so that $p_i-p_j+1 \leq n-1$.
Thus, (\ref{E:Int_Prog_TSP_NewConstraints}) holds for the second case as well.

\newpar
We now verify that values of decision variables corresponding to a combination of subtours
passing through all destinations do not satisfy (\ref{E:Int_Prog_TSP_NewConstraints}). To do so, we assume to the contrary
that a combination of subtours exists, satisfying (\ref{E:Int_Prog_TSP_NewConstraints}), and, from there, we establish a contradiction.

\newpar
We begin by selecting the subtour not containing the first destination.
Then, for some $k$ satisfying $2 \leq k \leq n-1$ and for some
subset $\left\{ i_1, i_2, \ldots, i_k\right\}$ of distinct elements of
$\left\{2, \ldots, n \right\}$,
\begin{equation*}
i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \ldots \rightarrow i_k=i_1.
\end{equation*}
By repeated application of (\ref{E:Int_Prog_TSP_NewConstraints}), we obtain
the $k-1$ inequalities
\begin{align}\label{E:Int_Prog_TSP_SubtourInequalities}
p_{i_1} - p_{i_2} +1 &\leq (n-1)(1-x_{i_1 i_2}),  \\
p_{i_2} - p_{i_3} +1 &\leq (n-1)(1-x_{i_2 i_3}), \notag \\
\vdots  \qquad &\leq \qquad \vdots \notag \\
p_{i_{k-1}} - p_{i_k} +1 &\leq (n-1)(1-x_{i_{k-1} i_k}). \notag
\end{align}

\noi
Because $x_{i_m i_{m+1}}=1$ for $m=1,2,\ldots ,k-1$, the
sum of the $k-1$ inequalities in (\ref{E:Int_Prog_TSP_SubtourInequalities})
simplifies to
\begin{equation}\label{E:Int_Prog_TSP_SubtourInequalitiesSummed}
p_{i_1}-p_{i_k} + (k-1) \leq 0.
\end{equation}
However, $i_1=i_k$ so that $\ds p_{i_1}=p_{i_k}$, from which it follows $k \leq 1$. But this result  contradicts our assumption $k \geq 2$. We may therefore
conclude that decision variables corresponding to a subtour do not
satisfy constraints (\ref{E:Int_Prog_TSP_NewConstraints}).

\newpar
Combining all these results, we finally obtain an ILP formulation of the TSP:

\begin{align}\label{E:Int_Prog_TSP_Final}
 \mbox{minimize } D &= \sum_{i=1}^n \sum_{j=1}^n d_{ij}x_{ij}  \\
	\mbox{ subject to} \notag \\
	\sum_{i=1}^n x_{ij}&=1 , \quad 1 \leq i \leq n \notag \\
	\sum_{j=1}^n x_{ji}&=1 , \quad 1  \leq i \leq n \notag \\
p_i - p_j +1 &\leq (n-1)(1-x_{ij}) , \quad 2 \leq i,j \leq n \notag \\
p_1&=1 \notag \\
 2 \leq p_i &\leq n, \quad  2 \leq i \leq n \notag \\
p_i &\in \Z , \quad  1 \leq i \leq n. \notag \\
	x_{i,j} &\in \{0,1\} , \quad  1 \leq i,j \leq n. \notag
	\end{align}

\newpar
\begin{progress_ck}
Jane wishes to ride her bicycle on a tour passing through five towns. The
names of the towns and the distances between them are summarized in Table \ref{Ta:bicycling_distances}. Assume that Jane's ride starts in Jamestown. Use Maple to determine the tour that minimizes her total distance traveled. Hint: Define the two families of variables in (\ref{E:Int_Prog_TSP_Final})
using arrays:
\begin{maplelist}
\item \mf{x:=array(1..5,1..5):}
\item \mf{p:=array(1..5):}
\end{maplelist}

\noi
The first two families of constraints can be formulated by combining the \mf{add} and \mf{seq} commands.
For the third family of constraints, nest two \mf{seq} commands as follows:
\begin{maplelist}
\item \mf{seq(seq(p[i]-p[j]+1<=4*(1-x[i,j]),j=2..n),i=2..n):}
\end{maplelist}

\noi
Your results should indicate that Jane rides from
Jamestown to Cutlerville to Caledonia to Dorr to Byron Center, and back to Jamestown.

\end{progress_ck}
\begin{table}[h]
\caption{Distances between towns for Jane's bicycle ride}\label{Ta:bicycling_distances}
\begin{tabular}{|l|c|c|c|c|c|}
\hline
City  & Jamestown & Dorr & Byron Center & Caledonia & Cutlerville \\
\hline \hline
Jamestown & $\bs$ & 13 & 7 & 22 & 11           \\ \hline
Dorr & 13 & $\bs$ & 6 & 15 & 11           \\ \hline
Byron Center & 7 & 6 & $\bs$ & 13 & 6           \\ \hline
Caledonia & 22 & 15 & 13 & $\bs$ & 12           \\ \hline
Cutlerville & 11 & 11 & 6 & 12 & $\bs$           \\ \hline
\end{tabular}
\end{table}

\newpar
While (\ref{E:Int_Prog_TSP_Final}) provides a means of stating the TSP as an ILP, the
task of solving it proves inefficient, even for problems involving a moderate number of decision variables. For this reason, determining more efficient methods for solving larger-scale TSPs remains a much-pursued goal in the field of
linear programming.

\section*{Exercises Section \protect\ref{S:Intro_IP_Branch_and_Bound_Method}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Int_Prog}	
	
\endinput
	
	