%===========================================================================%
%                                                                           %
% This file is part of the documentation for the SYMPHONY MILP Solver.      %
%                                                                           %
% SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and         %
% Laci Ladanyi (ladanyi@us.ibm.com).                                        %
%                                                                           %
% (c) Copyright 2000-2011 Ted Ralphs. All Rights Reserved.                  %
%                                                                           %
% SYMPHONY is licensed under the Eclipse Public License. Please see         %
% accompanying file for terms.                                              %
%                                                                           %
%===========================================================================%

\section{A Brief History}
\label{history}

Since the inception of optimization as a recognized field of study in
mathematics, researchers have been both intrigued and stymied by the
difficulty of solving many of the most interesting classes of discrete
optimization problems. Even combinatorial problems, though
conceptually easy to model as integer programs, have long remained
challenging to solve in practice. The last two decades have seen
tremendous progress in our ability to solve large-scale discrete
optimization problems. These advances have culminated in the approach
that we now call {\it branch and cut}, a technique (see \cite{Grotschel84cut,padb:branc,hoff:LP}) which brings the computational tools of branch and bound
algorithms together with the theoretical tools of polyhedral
combinatorics. Indeed, in 1998, Applegate, Bixby, Chv\'atal, and Cook
used this technique to solve a {\em Traveling Salesman Problem}
instance with 13,509 cities, a full order of magnitude larger than
what had been possible just a decade earlier \cite{concorde} and two
orders of magnitude larger than the largest problem that had been
solved up until 1978. This feat becomes even more impressive when one
realizes that the number of variables in the standard formulation for
this problem is approximately the {\em square} of the number of
cities. Hence, we are talking about solving a problem with roughly
{\em 100 million variables}.

There are several reasons for this impressive progress. Perhaps the
most important is the dramatic increase in available computing power
over the last decade, both in terms of processor speed and memory.
This increase in the power of hardware has subsequently facilitated
the development of increasingly sophisticated software for
optimization, built on a wealth of theoretical results. As software
development has become a central theme of optimization research
efforts, many theoretical results have been ``re-discovered'' in light
of their new-found computational importance. Finally, the use of
parallel computing has allowed researchers to further leverage their
gains.

Because of the rapidly increasing sophistication of computational
techniques, one of the main difficulties faced by researchers who wish
to apply these techniques is the level of effort required to develop
an efficient implementation. The inherent need for incorporating
problem-dependent methods (most notably for dynamic generation of
variables and cutting planes) has typically required the
time-consuming development of custom implementations. Around 1993,
this led to the development by two independent research groups of
software libraries aimed at providing a generic framework that users
could easily customize for use in a particular problem setting. One of
these groups, headed by J\"unger and Thienel, eventually produced
ABACUS (A Branch And CUt System) \cite{abacus1}, while the other,
headed by the authors, produced what was then known as COMPSys
(Combinatorial Optimization Multi-processing System). After several
revisions to enable more broad functionality, COMPSys became SYMPHONY
(Single- or Multi-Process Optimization over Networks). 
A version of SYMPHONY written in C++, which we call
COIN/BCP has also been produced at IBM under the COIN-OR project
\cite{coin-or}. The COIN/BCP package takes substantially the same
approach and has the same functionality as SYMPHONY, but has extended
SYMPHONY's capabilities in some areas.

\section{Related Work}
\label{related}

The 1990's witnessed a broad development of software for discrete
optimization. Almost without exception, these new software packages
were based on the techniques of branch, cut, and price. The packages
fell into two main categories---those based on general-purpose
algorithms for solving mixed-integer linear programs (MILPs)
(without the use of special structure)
and those facilitating the use of special structure by interfacing
with user-supplied, problem-specific subroutines. We will call
packages in this second category {\em frameworks}. There have also
been numerous special-purpose codes developed for use in particular
problem settings.

Of the two categories, MILP solvers are the most common. Among the
dozens of offerings in this category are MINTO \cite{MINTO}, MIPO
\cite{MIPO}, bc-opt \cite{bc-opt}, and SIP \cite{SIP}. Generic
frameworks, on the other hand, are far less numerous. The three
frameworks we have already mentioned (SYMPHONY, ABACUS, and COIN/BCP)
are the most full-featured packages available. Several others, such as
MINTO, originated as MILP solvers but have the capability of utilizing
problem-specific subroutines. CONCORDE \cite{concorde, concorde2}, a
package for solving the {\em Traveling Salesman Problem} (TSP), also
deserves mention as the most sophisticated special-purpose code
developed to date.

Other related software includes several frameworks for implementing
parallel branch and bound. Frameworks for general parallel branch and
bound include PUBB \cite{PUBB}, BoB \cite{BoB}, PPBB-Lib
\cite{PPBB-Lib}, and PICO \cite{PICO}. PARINO \cite{PARINO} and FATCOP
\cite{chen:fatcop2} are parallel MILP solvers.

\section{Introduction to Branch, Cut, and Price}
\label{B&C-intro}

\subsection{Branch and Bound}

{\em Branch and bound} is the broad class of algorithms from which
branch, cut, and price is descended. A branch and bound algorithm uses
a divide and conquer strategy to partition the solution space into
{\em subproblems} and then optimizes individually over each
subproblem. For instance, let $S$ be the set of solutions to a given
problem, and let $c \in {\bf R}^S$ be a vector of costs associated
with members of S. Suppose we wish to determine a least cost member of
S and we are given $\hat{s} \in S$, a ``good'' solution determined
heuristically. Using branch and bound, we initially examine the entire
solution space $S$. In the {\em processing} or {\em bounding} phase,
we relax the problem. In so doing, we admit solutions that are not in
the feasible set $S$. Solving this relaxation yields a lower bound on
the value of an optimal solution. If the solution to this relaxation
is a member of $S$ or has cost equal to $\hat{s}$, then we are
done---either the new solution or $\hat{s}$, respectively, is optimal.
Otherwise, we identify $n$ subsets of $S$, $S_1, \ldots, S_n$, such
that $\cup_{i = 1}^n S_i = S$. Each of these subsets is called a {\em
subproblem}; $S_1, \ldots, S_n$ are sometimes called the {\em
children} of $S$. We add the children of $S$ to the list of {\em
candidate subproblems} (those which need processing). This is called
{\em branching}.

To continue the algorithm, we select one of the candidate subproblems
and process it. There are four possible results. If we find a feasible
solution better than $\hat{s}$, then we replace $\hat{s}$ with the new
solution and continue. We may also find that the subproblem has no
solutions, in which case we discard, or {\em prune} it. Otherwise, we
compare the lower bound to our global upper bound. If it is greater
than or equal to our current upper bound, then we may again prune the
subproblem. Finally, if we cannot prune the subproblem, we are forced
to branch and add the children of this subproblem to the list of
active candidates. We continue in this way until the list of active
subproblems is empty, at which point our current best solution is the
optimal one.

\subsection{Branch, Cut, and Price}
\label{branchandcut}

In many applications, the bounding operation is accomplished using the
tools of linear programming (LP), a technique first described in full
generality by Hoffman and Padberg \cite{hoff:LP}. This general class of
algorithms is known as {\em LP-based branch and bound}. Typically, the
integrality constraints of an integer programming formulation of the
problem are relaxed to obtain a {\em LP relaxation}, which is then
solved to obtain a lower bound for the problem. In \cite{padb:branc},
Padberg and Rinaldi improved on this basic idea by describing a method
of using globally valid inequalities (i.e., inequalities valid for the
convex hull of integer solutions) to strengthen the LP relaxation.
They called this technique {\em branch and cut}. Since then, many
implementations (including ours) have been fashioned around the
framework they described for solving the Traveling Salesman Problem.

\begin{figure}
\framebox[6.5in]{
\begin{minipage}{6.0in}
\vskip .1in
{\rm
{\bf Bounding Operation}\\
\underbar{Input:} A subproblem ${\cal S}$, described in
terms of a ``small'' set of inequalities ${\cal L'}$ such that ${\cal
S} = \{x^s : s \in {\cal F}\;\hbox{\rm and}\;ax^s \leq \beta\;\forall
\;(a,\beta) \in {\cal L'}\}$ and $\alpha$, an upper bound on the global 
optimal value. \\
\underbar{Output:} Either (1) an optimal solution $s^* \in {\cal S}$ to
the subproblem, (2) a lower bound on the optimal value of the 
subproblem, or (3) a message {\tt pruned} indicating that the
subproblem should not be considered further. \\
{\bf Step 1.} Set ${\cal C} \leftarrow {\cal L'}$. \\ 
{\bf Step 2.} Solve the LP $\min\{cx : ax \leq \beta\;\forall\;(a, \beta) 
\in {\cal C}\}$. \\
{\bf Step 3.} If the LP has a feasible solution $\hat{x}$, then go to
Step 4. Otherwise, STOP and output {\tt pruned}. This subproblem has no 
feasible solutions. \\ 
{\bf Step 4.} If $c\hat{x} < \alpha$, then go to Step
5. Otherwise, STOP and output {\tt pruned}. This subproblem
cannot produce a solution of value better than $\alpha$. \\ 
{\bf Step 5.} If $\hat{x}$ is the incidence vector of some $\hat{s}
\in {\cal S}$, then $\hat{s}$ is the optimal solution to this
subproblem. STOP and output $\hat{s}$ as $s^*$. Otherwise, apply
separation algorithms and heuristics to $\hat{x}$ to get a set of
violated inequalities ${\cal C'}$. If ${\cal C'} = \emptyset$, then
$c\hat{x}$ is a lower bound on the value of an optimal element of
${\cal S}$.  STOP and return $\hat{x}$ and the lower bound
$c\hat{x}$. Otherwise, set ${\cal C} \leftarrow {\cal C} \cup {\cal
C'}$ and go to Step 2.}
\end{minipage}
}
\caption{Bounding in the branch and cut algorithm}
\label{proc-bound}
\end{figure}
As an example, let a combinatorial optimization problem $\hbox{\em CP} =
(E, {\cal F})$ with {\em ground set} $E$ and {\em feasible set} ${\cal F}
\subseteq 2^E$ be given along with a cost function $c \in {\bf R}^E$.
The incidence vectors corresponding to the members of ${\cal F}$ are
sometimes specified as the the set of all incidence vectors obeying a
(relatively) small set of inequalities. These inequalities are
typically the ones used in the initial LP relaxation. Now let ${\cal
P}$ be the convex hull of incidence vectors of members of ${\cal
F}$. Then we know by Weyl's Theorem (see \cite{nemwol88}) that there exists
a finite set ${\cal L}$ of inequalities valid for ${\cal P}$ such that
\begin{equation}
\label{the-polyhedron}
{\cal P} = \{x \in {\bf R}^n: ax \leq \beta\;\;\forall\;(a, \beta) \in 
{\cal L}\}.
\end{equation}
The inequalities in ${\cal L}$ are the potential cutting planes to be
added to the relaxation as needed. Unfortunately, it is usually
difficult, if not impossible, to enumerate all of inequalities in
${\cal L}$ or we could simply solve the problem using linear
programming. Instead, they are defined implicitly and we use
separation algorithms and heuristics to generate these inequalities
when they are violated. In Figure \ref{proc-bound}, we describe more
precisely how the bounding operation is carried out in branch and cut.
\begin{figure}
\framebox[6.5in]{
\begin{minipage}{6.0in}
\vskip .1in
{\rm
{\bf Branching Operation} \\
\underbar{Input:} A subproblem ${\cal S}$ and $\hat{x}$, the LP solution
yielding the lower bound. \\
\underbar{Output:} $S_1, \ldots, S_p$ such that ${\cal S} = \cup_{i = 1}^p
S_i$. \\
{\bf Step 1.} Determine sets ${\cal L}_1, \ldots, {\cal L}_p$ of
inequalities such that ${\cal S} = \cup_{i = 1}^n \{x \in {\cal S}: ax \leq
\beta\;\forall\;(a, \beta) \in {\cal L}_i\}$ and $\hat{x} \notin
\cup_{i = 1}^n S_i$. \\
{\bf Step 2.} Set $S_i = \{x \in {\cal S}: ax \leq
\beta\;\;\forall\;(a, \beta) \in {\cal L}_i \cup {\cal L}'\}$ where 
${\cal L'}$ is the set of inequalities used to describe ${\cal S}$.}
\end{minipage}
}
\caption{Branching in the branch and cut algorithm}
\label{branching-fig}
\end{figure}

\indent Once we have failed to either prune the current subproblem or separate
the current fractional solution from ${\cal P}$, we are forced to
branch. The branching operation is accomplished by specifying a set of
hyperplanes which divide the current subproblem in such a way that the
current solution is not feasible for the LP relaxation of any of the
new subproblems. For example, in a combinatorial optimization problem,
branching could be accomplished simply by fixing a variable whose
current value is fractional to 0 in one branch and 1
in the other. The procedure is described more formally in Figure
\ref{branching-fig}. Figure \ref{gb&c} gives a high level description
of the generic branch and cut algorithm.
\begin{figure}
\framebox[6.5in]{
\begin{minipage}{6.0in}
\vskip .1in
{\rm
{\bf Generic Branch and Cut Algorithm}\\
\underbar{Input:} A data array specifying the problem instance.\\
\underbar{Output:} The global optimal solution $s^*$ to the problem
instance. \\
{\bf Step 1.} Generate a ``good'' feasible solution ${\hat s}$ using 
heuristics. Set $\alpha \leftarrow c(\hat{s})$. \\
{\bf Step 2.} Generate the first subproblem ${\cal S}^I$ by constructing a
small set ${\cal L'}$ of inequalities valid for ${\cal P}$. Set $A
\leftarrow \{{\cal S}^I\}$. \\
{\bf Step 3.} If $A = \emptyset$, STOP and output $\hat{s}$ as the
global optimum $s^*$. Otherwise, choose some ${\cal S} \in A$. Set $A
\leftarrow A \setminus \{{\cal S}\}$. Process ${\cal S}$. \\
{\bf Step 4.} If the result of Step 3 is a feasible solution
$\overline{s}$, then $c\overline{s} < c\hat{s}$.
Set $\hat{s} \leftarrow \overline{s}$ and $\alpha \leftarrow 
c(\overline{s})$ and go to Step 3. If the subproblem was pruned, go to
Step 3. Otherwise, go to Step 5. \\
{\bf Step 5.} Perform the branching operation. Add the set of
subproblems generated to $A$ and go to Step 3.}
\end{minipage}
}
\caption{Description of the generic branch and cut algorithm}
\label{gb&c}
\end{figure}

As with cutting planes, the columns of $A$ can also be defined
implicitly if $n$ is large. If column $i$ is not present in the
current matrix, then variable $x_i$ is implicitly taken to have value
zero. The process of dynamically generating variables is called {\em
pricing} in the jargon of linear programming, but can also be viewed
as that of generating cutting planes for the dual of the current
LP relaxation. Hence, LP-based branch and bound algorithms in which
the variables are generated dynamically when needed are known as {\em
branch and price} algorithms. In \cite{barn:branc}, Barnhart,
et al. provide a thorough review of these methods. 

When both variables and cutting planes are generated dynamically
during LP-based branch and bound, the technique becomes known as {\em
branch, cut, and price} (BCP). In such a scheme, there is a pleasing
symmetry between the treatment of cuts and that of variables. We
further examine this symmetry later in the manual. For
now, however, it is important to note that while branch, cut, and
price does combine ideas from both branch and cut and branch and price
(which are very similar to each other anyway), combining the two
techniques requires much more sophisticated methods than either one
requires on its own. This is an important idea that is at the core of
our design.

In the remainder of the manual, we often use the term {\em search
tree}. This term derives from the common representation of the list of
subproblems as the nodes of a graph in which each subproblem is
connected only to its parent and its children. Storing the subproblems
in such a form is an important aspect of our global data structures.
Since the subproblems correspond to the nodes of this graph, they are
sometimes be referred to as {\em nodes in the search tree} or simply
as {\em nodes}. The {\em root node} or {\em root} of the tree is the
node representing the initial subproblem.

