% MODIFY THE FOLLOWING TO INCLUDE THE LECTURE #, TOPIC, DATE, and YOUR NAME
\lecturetitle{10}{Integer Programming 1}{1 Oct 97}{Andrew Begel}

% INCLUDE AN OUTLINE OF THE CLASS TOPICS
\begin{itemize} 
  \item History

  \item Knapsack Problem

  \item Traveling Salesman Problem

  \item Algorithms
    \begin{enumerate}
    \item Linear Program as Approximation
    \item Branch and Bound (integer ranges)
    \item Implicit (0-1 variables)
    \item Cutting Planes ($postponed$)
    \end{enumerate}
\end{itemize}

\section{Introduction and History}

Linear integer programming (often just called integer programming, or IP)
is a linear program with the additional constraint that all
variables must be integers, for example:  

\begin{quote}
\begin{tabular}{rl}
maximize & $c x$ \\
subject to & $Ax \leq b$ \\
           & $x \geq 0$ \\
           & $x \in {\cal Z}^n$
\end{tabular}
\end{quote}

%\centerline{\psfig{file=../lecture10/pict1.EPS}}

There are several problems related to integer programming: 

\begin{description}
\item[Mixed integer programming (MIP):]
Some of the variables are constrained to be integers
and others are not.
\item[zero-one programming:] 
All the variables are constrained to be binary (0 or 1).
\item[Integer quadratic programming:]
The cost function can be quadratic.
\end{description}

Integer programming was introduced by Danzig in 1951. In 1954, he
showed that TSP (traveling salesman problem) was a special case of
integer programming. Gomory found the first convergent algorithm in
1958. In 1960, Land and Doig created the first general branch and
bound techniques for solving integer programming problems. 

Integer and mixed integer programming has become ``dominant'' over linear
programming in the past decade. It saves many industries
(e.g. airline, trucking) more than one billion dollars a year.
The state of the art in algorithms is branch-and-bound + cutting plane
+ separation (solving sub-problems).  General purpose packages don't
tend to work as well with integer programming as they do with linear
programming. Most techniques employ some form of problem-specific
knowledge. 

\section{Applications}

IP and MIP can be applied to a number of different
problem areas: 

\begin{itemize}
  \item Facility location -- Where should we locate a warehouse or a Burger
King to minimize shipping costs? 

  \item Set covering and Set partitioning -- Scheduling crews for Delta

  \item Multicomodity distribution -- Routing deliveries for Safeway 

  \item Capital budgeting -- Developing a budget for Microsoft

  \item Other applications -- VLSI layout, clustering, etc. 
\end{itemize}

Here we will describe how various problems can be expressed as
integer programs.

\subsection{Knapsack Problem}

It looks trivial, but it's NP-complete.

\begin{quote}
\begin{tabular}{lcl}
Maximize & &$c x$ \\
subject to & & $a x \leq b$,\\
           & & $x$ binary
\end{tabular}
\end{quote} 
where:
\begin{eqnarray*}
b &=& \mbox{maximum weight}\\
c_i &=& \mbox{utility of item } i\\
a_i &=& \mbox{weight of item } i\\
x_{i} &=&
\left\{
\begin{array}{lll}
1, & & \mbox{if item $i$ is selected}\\
0, & & \mbox{otherwise}
\end{array}
\right.
\end{eqnarray*}

\subsection{Traveling Salesman Problem}

\begin{eqnarray*}
\mbox{We want to minimize} & &\sum_{i=1}^{n}\sum_{j=1}^{n} c_{i,j} x_{i,j} \\
\mbox{subject to} & & \\
\sum_{j=0}^n x_{i,j} & = & 1, \hspace{.4in} \mbox{for } i = 1, \ldots, n\\
\sum_{i=0}^n x_{i,j} & = & 1, \hspace{.4in} \mbox{for } j = 1, \ldots, n\\
t_i - t_j + n x_{i,j} & \leq & n -1,
                              \hspace{.4in} \mbox{for } i,j = 2, \ldots, n\\
\end{eqnarray*}
where:
\begin{eqnarray*}
c_{i,j} &=& \mbox{distance from city $i$ to city $j$}\\
x_{i,j} &=&
\left\{
\begin{array}{lll}
1, & & \mbox{if city $j$ visited immediately after city $i$}\\
0, & & \mbox{otherwise}
\end{array}
\right.\\
t_i & = & \parbox[t]{4in}{arbitrary real numbers we need to solve for,\\ but we
don't really care about their values}
\end{eqnarray*}

The first set of $n$ constraint restricts the number of times the
solution enters each city to 1.  The second set of $n$ constraint
restricts the number of times the solution leaves each city to 1.
The last set of constraints are used to eliminate subtours.
In particular the constraints make sure that any tour includes city 1, which
in conjunction with  the first and second set of constraints forces
a single tour.

To see why the last set of constraints forces any tour to include city
1, lets consider a tour that does not include the city and show a
contradiction.   Lets say the tour visits the sequence of
cities $v_1,v_2,v_3,\ldots,v_l$ none of which is city 1.   Lets
add up the equations taken from the last set of constraints 
for each pair of cities that are visited one
after the other in the tour.  Since it is a tour, each $t_{v_i}$ will appear
once positively and once negatively in this sum, and will therefore cancel.
This leaves us with $n l \leq (n-1) l$, which is clearly a contradiction.


\subsection{Other Constraints Expressible with Integer Programming}

Logical constraints ($x_1, x_2$ binary):
\begin{eqnarray*}
\mbox{Either } x_1 \mbox{ or } x_2 & \Rightarrow & x_1 + x_2 = 1\\
\mbox{If } x_1 \mbox{ then } x_2 & \Rightarrow & x_1 - x_2 \leq 0
\end{eqnarray*}

Integer constraints can also be applied to combine constraints:

\begin{eqnarray*}
\mbox{Either or }
\begin{array}{lll}
a_1 x & \leq& b_1 \\
a_2 x &\leq& b_2\\
  \end{array}
& \Rightarrow &
\begin{array}{lll}
a_1 x - My & \leq& b_1\\
a_2 x - M(1-y)&\leq& b_2\\
y \mbox{ binary}\\
  \end{array}
  \end{eqnarray*}
The $M$ is a scalar and needs to be ``large'' 
($x$, $a_1$, and $a_2$ are vectors).
This works since if $y = 1$ 1 then the first equation is always true
and the second needs to be satisfied, while if $y = 0$ then the second
is always true and the first needs to be satisfied.  Since $y$ is constrained
to be binary, one needs to be satisfied.

A similar approach can be used to handle $m$ out of $n$ constraints.

\subsection{Piecewise Linear Functions}

Consider a minimization problem with the following objective function
\[ c(x) = \left\{
\begin{array}{lll}
0 && x = 0\\
k + c x && x \geq 0
\end{array}\right.
\]
and assume that $x \leq M$.
This can be expressed as the following integer program:

\begin{quote}
\begin{tabular}{ll}
minimize   & $k y + c x$ \\
such that  & $x_i \leq M y$ \\
           & $x_i \geq 0$ \\
           & $y \in \{0,1\}$
\end{tabular}
\end{quote}
The first inequality forces $y$ to be 1 if $x$ is anything other than 0.
This basic approach can be generalized to 
arbitrary piecewise linear functions.

\section{Algorithms}

\subsection{Linear Programming Approximations}

The LP solution is an upper bound on the IP solution. If the LP is
infeasible, then the IP is infeasible. If the LP solution is integral
(all variables have integer values), then it is the IP solution,
too. 

Some LP problems (e.g. transportation problem, assignment problem,
min-cost network flow) will always have integer solutions. These can
be classified as problems with a unimodular matrix $A$. (Unimodular
$\Rightarrow detA = 0, 1$ or $-1$). 

Other LP problems have real solutions that must be rounded to the
nearest integer. This can violate constraints, however, as well as
being non-optimal. It is good enough if integer values take on large
values or the accuracy of constraints is questionable. You
can also preprocess problems and add constraints to make the solutions
come out closer to integers. 

\subsection{Search Techniques}

We will now describe two search techniques for solving integer
programms both based on a general Branch-and-Bound approach.
The first technique works for general integer programs and the
second for 0-1 programs.  For historical reasons, the first
is called the Branch and Bound algorithm, even though both
algorithms are in fact based on branch and bound.
Both algorithms require exponential time in the general case.

\subsubsection{Branch and Bound}
\index{Branch and Bound Enumeration}

The branch and bound approach basically builds a tree of possible
solutions by splitting at each node of the tree based on a value for
one of the variables ({\em e.g.,} all solutions with $x < 3$ go to the
left branch and all solutions with $x \geq 3$ go to the right branch).
Such a tree can easily end up having a number of nodes that is
exponential in the number of variables.  However, by judicially
pruning the tree we can hope to greatly reduce the number of nodes
that have to be searched.  The ``bound'' refers to the pruning of the
tree so that we don't have to search further.

Each time the algorithms branches left or right it adds a constraint
({\em e.g.,} $x < 3$).  The pruning is based on keeping the best
previous solution found (lets assume a maximization problem) and then
using a linear program to get an upper bound on the solution given the
current constraints.  If the solution to the linear program is less
than the best previous solution then the node does not have to be
searched further.  There is freedom in the basic algorithm in
selecting the next node to expand.  The most common approaches are to
use either a depth first search (DFS) or best-first search.  Depth-first
search has
the advantage that it more quickly finds an initial solution and
leaves less nodes ``open'' (each of which requires space to store).
Best-first search has the advantage that it might find the best
solution faster.  A compromise is to use beam search by limiting
the number of partial solutions that can be left open in a best-first
search.

Figure~\ref{figure:bb} shows a branch-and-bound algorithm 
that uses DFS and pruning to solve the maximization problem
\begin{quote}
\begin{tabular}{lcl}
maximize & &$c x$ \\
subject to & & $Ax \leq b$, $x \geq 0$, $x \in {\cal Z}^n$
\end{tabular}
\end{quote}

\begin{figure}
\begin{quote}
\begin{tabbing}
{\bf function} $IP(C,c,z*)$\\
~~~~~// C is the set of constraints $Ax \leq b$\\
~~~~~// c is the objective vector\\
~~~~~// $z*$ is the cost of the current best solution (initially $-\infty$) \\[.05in]
~~~~~// Returns the cost of the optimal solution with constraints $C$ \\
~~~~~~~~~~if better than $z*$, otherwise returns z* \\[.15in]
~~$z,x,f = LP(C,c)$\\
~~~~~// $f$ indicates whether $LP(C,c)$ is feasible or not\\[.15in]
~~{\bf if} not($f$) {\bf return} $z*$
~~~~~~~~~// no feasible solution\\
~~{\bf if} $z \leq z*$ {\bf return} $z*$
~~~~~~~~~// upper bound less than current best solution\\
~~{\bf if} integer($x$) {\bf return} $z$
~~~~~~~~~// new best solution found\\[.15in]
~~pick a non integer variable $x_i'$ from x\\[.15in]
~~$C_d = C,x_i \leq \lfloor x_i' \rfloor$\\
~~$z* = IP(C_d,c,z*)$\\[.15in]
~~$C_u = C,-x_i \leq -\lceil x_i' \rceil$\\
~~$z* = IP(C_u,c,z*)$\\[.15in]
~~{\bf return} $z*$\\
{\bf end}
\end{tabbing}
\end{quote}
\caption{The Branch and Bound Algorithm for Integer Programming.}
\label{figure:bb}
\end{figure}

The algorithm passes around the current best solution $z*$ and adds
constraints to the constraint set $C$ each time it expands a node by
making recursive calls.  The algorithm stops expanding a node (bounds
or prunes the node) if either (1) the linear program given the current
set of constraints is infeasible (2) the solution to the linear program
is less than the current best solution (3) the linear program
has an integer solution.

Note that given the solution of the linear program at a node, solving
the problem at the two children is much easier than solving it from
scratch since we are already very close to the solution.  The dual
simplex method can be used to quickly resolve an LP after adding one
additional constraint.

\subsection{Implicit Enumeration (0-1 Programs)}
\index{Implicit Enumeration}

We want to solve the problem:
\begin{quote}
\begin{tabular}{lcl}
minimize & &$c x$ \\
subject to & & $Ax \leq b$, $c \geq 0$, $x \in {\{0,1\}}^n$
\end{tabular}
\end{quote}
Note that this formulation assumes that the coefficients of $c$ are all
positive.  It is not hard to convert problems with negative
coefficients into this form.  

\begin{figure}
\begin{quote}
\begin{tabbing}
{\bf function} $IP(C,c,x_f,z*)$\\
~~~~~// C is the set of constraints $Ax \leq b$\\
~~~~~// c is the objective vector\\
~~~~~// $x_f$ a subset of the variables which are fixed\\
~~~~~// z* is the cost of the current best solution\\[.15in]
~~$x = x_f + 0$ (set free variables to zero)\\
~~~~~// this is the best solution ignoring inequalities since $c \geq 0$\\
~~~~~// it is not necessarily feasible\\[.15in]
~~{\bf if} $c x \geq z*$ {\bf return} $z*$
~~~~~~~~~// lower bound greater than current best solution\\
~~{\bf if} feasible$(C,x)$ {\bf return} $c x$
~~~~~~~~~// new best feasible solution found\\
~~{\bf if} no feasible completion to $x_f$ {\bf return} $z*$\\[.15in]
~~pick a non fixed variable $x_i$ from x\\[.15in]
~~$x_{f0} = x_f \cup \{x_i = 0\}$\\
~~$z* = IP(A,c,x_{f0},z*)$\\[.15in]
~~$x_{f1} = x_f \cup \{x_i = 1\}$\\
~~$z* = IP(A,c,x_{f1},z*)$\\[.15in]
~~{\bf return} $z*$\\
{\bf end}
\end{tabbing}
\end{quote}
\caption{The Implicit Enumeration Algorithm for 0-1 Programming.}
\label{figure:ie}
\end{figure}

Figure~\ref{figure:ie} shows an algorithm based on the ``implicit
enumeration'' with depth-first-search for solving such a problem.
Unlike the previous technique, implicit enumeration does not require
linear programming.  To generate a lower bound on the solution (upper
bound for a maximization problem) it uses a solution in which all
variables are binary but that does not necessarily obey the inequality
constraints.  The previous branch-and-bound technique generated
the upper bound by using a solution (the LP solution) that obeys all
the inequality constraints, but is not necessarily integral.

Here's how to implement the substeps. 
To check for feasible$(C,x)$ we can just plug $x$ into $C$.
To check if there are no feasible completions we can check each
constraint. 

For example, if \[ x_f = \{x_1 = 1, x_3 = 0\} \]
and one of the constraints is
\[3 x_1 + 2 x_2 - x_3 + x_4 \leq 2 \]
then 
\begin{eqnarray*}
 3 \cdot 1 + 2 x_2 - 1 \cdot 0 + x_4 & \leq & 2 \\
 2 x_2 + x_4 & \leq & -1
\end{eqnarray*}
which is impossible since $x_1$ and $x_2$ are binary.

Note that this check is not necessarily always going to tell us
that there are no possible completions even if there aren't.
It is also possible to run more complicated tests that involve multiple
inequalities at a time, which might find a completion is infeasible
when the simple technique does not.

