\section{A Brief History}

Since the inception of optimization as a mathematical discipline,
researchers have been intrigued and stymied by the
difficulty of solving discrete
optimization problems. Even problems with natural and concise formulations
remain 
challenging to solve in practice. The most significant advance in general
methodologies occured in 1991 when Padberg and Rinaldi
\cite{A:padberg-rinaldi} merged the enumeration approach of branch and bound
algorithms with the polyhedral approach of cutting planes to create
the technique we call {\em branch, cut
and price} or simply {\em BCP}. 
Integrating the contributions of many in the field , their paper launched a
new era in discrete optimization techniques.

In the last two decades, we have seen tremendous progress in our
ability to solve specially structured large-scale discrete 
optimization problems. Indeed,
in 1998, Applegate, Bixby, Cook, and Chv\'atal \cite{W:concorde}
solved a {\em Traveling
Salesman Problem} (TSP) instance with 13,509 cities; a full order of
magnitude larger than what had been possible just a decade earlier
and two orders of magnitude larger than the largest
problem that had been solved up until 1978. This progress 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 problem size. Hence, we are talking about solving a
problem with somewhere in excess of {\em 100 million variables}.

This fantastic progress can be attributed to several factors. 
The increase in available computing power over the last decade, both
in terms of processor speed and memory, has been nothing short of
amazing. This hardware improvement made it possible to tackle larger problems
thus accumulating knowledge about how the large problems ``behave''. In turn,
this led to increasingly sophisticated software for
optimization, and to a wealth of theoretical results.
Also, many theoretical results, which had no computational importance for
small problems, were ``re-discovered'' as larger problems
became the target. Finally, the use of
parallel computing has allowed researchers to further leverage their
gains.

As computational research in optimization becomes more widespread and
the sophistication of computational techniques increases, 
one of the main difficulties faced by researchers in the area
is the level of effort required to
develop an efficient implementation. The need for
incorporating problem-dependent methods (most notably dynamic
generation of variables and cutting planes) typically required
time-consuming development of custom implementations. In the early 1990's
a research group was formed with the goal of creating 
a generic software framework which users
could easily customize for their particular problem class. This
group eventually produced what was then known as COMPSys
(Combinatorial Optimization Multi-processing System) \cite{P:compsys}. 
After several
revisions which broadened the framework's functionality, 
COMPSys became SYMPHONY
(Single- or Multi-Process Optimization over Networks)
\cite{W:symphony}. Starting in 1998 a total reimplementation in C++ was
undertaken at IBM research to enable greater flexibility. The result of this
effort was opened up as an open-source project in 2000 under the auspices of
the Common Optimization INterface for Operations Research (COIN-OR) 
\cite{W:coin-or} and is codenamed \BB.

\section{Related Work}

In the 1990's, there was a virtual explosion of software for discrete
optimization. Almost without exception, these new software packages
were based on the basic techniques of branch, cut and price. The
general-purpose packages fall into two main
categories -- those based on algorithms not exploing special structures 
for solving general
mixed integer programs (MIPs)
and those facilitating the use of special structure via
user-supplied, problem-specific subroutines. We will call
packages in this second category {\em frameworks}. There have also been
numerous special-purpose codes developed specifically for use in a
particular problem setting. 

Of the two categories, general-purpose MIP solvers are the most common. 
Among the 
dozens of offerings in this category, the most notable are MINTO
\cite{W:minto}, MIPO \cite{W:mipo}, bc-opt \cite{W:bcopt} and 
several commercial
packages. 

Generic
frameworks, on the other hand, are far less numerous. The most full-featured
packages available are the two frameworks we have already mentioned (SYMPHONY
and \BB) and a commercial product, ABACUS \cite{W:abacus}.
Some general-purpose MIP solver, such as
MINTO \cite{W:minto} and several commercial packages, now have a limited
capability of utilizing problem-specific subroutines.

Related software includes general MIP solvers implementing
parallel branch and bound (PARINO \cite{W:parino} and FATCOP
\cite{W:fatcop}); frameworks for general parallel branch and 
bound (PUBB \cite{W:pubb}, BoB \cite{W:bob}, PPBB-Lib
\cite{W:ppbb-lib}, and PICO \cite{W:pico}) and special-purpose codes, like 
CONCORDE, a package for solving the {\em Traveling Salesman Problem}
(TSP). This latter code is the  most sophisticated special-purpose
code developed to date.

%If the objective function $f$ is linear, and the set $S$
%consists of $n$-dimensional vectors, then it is sufficient to 

%and are
%important both from a practical and a theoretical perspective. 
%and Integer Programming have always been
%important application areas
%Although parallel computation has been a hot research topic for a
%number of years, few researchers have been devoted to solving 
%hard discrete ongoing in the computer
%science community for years, very little of the knowledge that has
%been developed in that community has made the crossover to
%applications in other fields. This is especially true for Operations
%Research in general and discrete optimization specifically, where many
%problems lend themselves naturally to to parallelization.

%Throughout the 1990's, the pace of change in computing was more rapid
%than ever before. Faster chips, more memory, and better software were
%were a demanded by businesses who wanted to keep their competitive
%edge. Customers insisted on faster, better service and Web servers had to
%deal with an ever increasing desire for information. In the face of
%this increasing need for computing power, many companies began to turn to
%multi-processor servers as an economical alternative to buying and
%networking multiple single-processor computers. Today, small
%shared-memory parallel computers are common-place in many companies.
%Most large vendors now offer multi-processor servers as a mainstay of
%their high-end product lines. We are now entering the age of parallel
%computing.

%During the coming decade, the pace of development of both hardware and
%software that can take advantage of parallelism to deliver superior
%computing performance will no doubt increase. Research in application
%areas such as discrete optimization will help spur this development
%and allow the US to maintain it's competitive edge in world markets. 

\section{Organization of the Manual}

The manual is divided into three parts. Part I is a gentle
introduction to branch, cut and price algorithms, including an
overview of the design of \BB. Anyone interested in learning
about or using the framework should spend time with Part I;
those already familiar with BCP algorithms will probably want to skim
the introductory sections. The reader merely
interested in only a high-level description of the framework may wish to
stop after reading Part I. Part II
is intended to provide the specific details needed
to actually develop applications using \BB. This includes ``how-to''
descriptions of customizing the Makefiles, compiling the sample code, deciding
wich built-in methods to override, 
and performing other development tasks such as
debugging. Part III illustrates these principles with a concrete
example. A reference manual of every class structure is available in
HTML format and is part of the standard distribution.

\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; it partitions the solution space into
{\em subproblems} and then optimizes over each subproblem 
individually. 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. Whenever a new, better solution is found we will replace 
$\hat{s}$ with the new solution. Thus the value of $\hat{s}$ is always a
{\em global upper bound} on th eoptimal value.
In the branch and bound algorithm we maintain a list of 
{\em candidate subproblems} each of which contain 
a subset of the original feasible solutions. This list is
initialized by placing $S$ on it.
In the {\em processing} or {\em bounding} phase of the algorithm we take 
an entry, say $S'$. from the candidate list and remove it from the list.
We {\em relax} $S'$, that is, we admit solutions that are not in $S'$ and
solve the relaxd problem. There are four possible results. 
\begin{itemize}
\item The relaxed problem is found to be infeasible. In this case we 
  obviously cannot find a new feasible solution that is feasible and is in 
  $S'$, thus we can {\em prune} (or {\em fathom}) the subproblem, that is, we
  discard it.
\item The optimal solution to the relaxed problem is not better 
  (not lower) than the global upper bound. In this case the value of any
  feasible solution in $S'$ must also not be better than the global upper
  bound thus we cannot find a feasible solution in $s'$ that would be better
  than the currently known best solution. Therefore we can fathom the 
  subproblem in this case, too.
\item The optimal solution to the relaxed problem is better than the global
  upper bound {\em and} it is in $S'$, i.e., it is feasible. In this case we
  replace $\hat{s}$ with this new solution. Also, we cannot find any even
  better solution in this subproblem thus we can fathom it.
\item The optimal solution to the relaxed problem is better than the global
  upper bound but is not in $S'$. In this case we {\em branch}, i.e., we 
  identify $n$ subsets of 
  $S'$, $S'_1, \ldots, S'_n$, such that $\cup_{i = 1}^n S'_i = S'$. 
  Each of these subsets, the {\em children} of $S'$, is a new candidate
  subproblem and is added to the candidate list. 
\end{itemize}
After a subproblem is processed (and either pruned or branched) a new
subproblem is 
selected for processing as long as the candidate list is not empty, at 
which point our current best solution is the optimal one.

%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. If we find that the subproblem has no
%solutions we discard, or {\em prune} (or {\em fathom} 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 can 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.

The sequence of subproblems generated can be displayed as a rooted directed
graph; the original problem being the root and there are edges from each
subproblem to its children. This graph is the {\em search tree} and the
expression {\em search (tree) node} is used interchangeably with 
{\em subproblem}.

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{A:hoffman-padberg}. 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.

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

Padberg and Rinaldi \cite{A:padberg-rinaldi} improved on the basic idea of 
LP-based branch and 
bound 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.

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$.
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{B:nemhauser-wolsey}) 
that there 
exists a finite set of inequalities ${\cal L}$ which are 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}
Unfortunately, it is usually
difficult, if not impossible, to enumerate all inequalities in
${\cal L}$ (or even just those that describe the convex hull near the 
optimal corner) or we could simply solve the problem using linear
programming.

The set of incidence vectors corresponding to the members of ${\cal F}$ is
sometimes approximated as 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). Then in each node of
the search tree globally valid inequalities are generated (the best such
inequalities are in ${\cal L}$) using separation algorithms and heuristics.
One could say that the inequalities describing ${\cal P}$ are defined
implicitely and generated as they are needed.

This way the relaxation is tightened thus the bounding step has a better
chance to fathom the node based on the objective value.
In Figure \ref{proc-bound}, we describe more
precisely how cut generation is employed within the bounding operation 
of the branch and cut technique.

\begin{figure}
\framebox[5.75in]{
\begin{minipage}{5.25in}
\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}

Once we have failed to generate cuts and the subproblem still cannot be pruned
based on the objective value, 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[5.75in]{
\begin{minipage}{5.25in}
\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}

\begin{figure}
\framebox[5.75in]{
\begin{minipage}{5.25in}
\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}

Note that adding cutting planes only increases the lower bound at a search
tree node hence as soon as the lower bound on a node exceeds the value of the
best known solution the search tree node can be fathomed.

\subsection{Branch and Price}
\label{branchandprice}

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. The term originates from
computing the {\em reduced cost} of the column and adding the column to the
formulation if it has a negative reduced cost. This procedure
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. Savelsbergh,
et al. \cite{branchandprice} provide a thorough review of these methods. 

Although ``branch and cut'' and ``branch and price'' look very symmetric there
is a very significant difference. When cuts are introduced the lower bound on
the relaxation can only increase while introducing new columns can lower the
lower bound. Therefore a search tree node cannot be fathomed until all
variables are priced out {\em and} the lower bound is higher than the best
known solution value. For this reason frequently the {\em price and branch}
algorithm is executed, that is first we price, then we do plain branch and
bound. Obviously, this will most likely result in a suboptimal solution, but
for practical purposes this is usually sufficient.

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

Finally, 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 variables.
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. The effects of this observation are noticable throughout
the design of \BB\ (see, in particular, Section \ref{data-structures}).

\section{Design of \BB}
\label{design}

\BB\ was designed with three major goals in mind -- portability, 
efficiency and
ease of use. With respect to ease of use, we aimed for a ``black box''
design, whereby the user would not be required to know anything about
the implementation of the library, but only about the user interface.
With respect to portability, we aimed not only for it to be {\em
possible} to use the framework in a wide variety of settings and on a
wide variety of hardware, but also for it to perform {\em effectively} in all
these settings. Our primary measure of effectiveness is
how well the framework performs in comparison to problem-specific
(or hardware-specific) implementation written ``from scratch.''

It is important to point out that achieving such design goals involves
a number of very difficult tradeoffs, which we will highlight
throughout the rest of the manual. For instance, ease of use is quite
often at odds with efficiency. In several instances, we had to give up
some efficiency to make the code easy to work with and to maintain a
true black box implementation. Maintaining portability across a wide
variety of hardware, both sequential and parallel, also required some
difficult choices. For example, solving large-scale problems on
sequential platforms requires extremely memory-efficient data
structures in order to maintain the very large search trees that can
be generated. However, these storage schemes are highly centralized
and do not scale well to large numbers of processors. 

\subsection{An Object-oriented Approach}
\label{object-oriented}

Applying BCP to large-scale problems
presents several difficult challenges. First and foremost is designing
methods and data structures capable of handling the potentially huge
number of global cuts and variables that need to be accounted for
during the solution process. A second challenge, which is closely
related to the first, is effectively dealing with the very large
search trees that can be generated for difficult problem instances. A
third challenge is to deal with these issues using a
problem-independent approach. 
%From this point of view, it quickly
%became evident that the vast majority of the procedures in branch and
%cut that depend on the problem setting have to do with generating,
%manipulating, and storing the cuts and variables.

Describing a node in the search tree consists of, among other things,
specifying which cuts and variables are initially {\em active} in the
subproblem. Hence, the central ``objects'' in our framework
are the cuts and variables. From the user's perspective, implementing
a BCP algorithm using \BB\ consists primarily of specifying
various properties of objects, such as how they are generated, how
they are represented, and how they should be realized within the
context of a particular subproblem. This is achieved using class derivation
and virtual methods. There are a few base classes defined in \BB\ that the
user can derive classes from and then she can override the virtual methods
hence modifying the behavior of the code. Some methods she must override, and
for some she can just let the method in the base class executed thus selecting
the default behavior. 
In Sections \ref{dev:overview-hierarchy} and \ref{dev:user-derived} a more
detailed 
description is given about the classes the user can derive new object types
from. 

\subsection{Data Structures and Storage}
\label{data-structures}

Both the memory required to store the search tree and the time
required to process a node are largely dependent on the number of
objects (cuts and variables) that are active in each subproblem.
Keeping this active set as small as possible is one of the keys to
efficiently implementing BCP. For this reason, we chose data
structures that enhance our ability to efficiently move objects in and
out of the active set. Allowing sets of cuts and variables to move in
and out of the linear programs simultaneously is one of the most
significant challenges of BCP. We do this by maintaining an abstract
{\em representation} of each global object that contains information
about how to add it to a particular LP relaxation. 

In the literature on linear and integer programming, the terms {\em
cut} and {\em row} are typically used interchangeably. Similarly, {\em
variable} and {\em column} are often used with similar meanings. In
many situations, this is appropriate and does not cause confusion.
However, in object-oriented BCP frameworks, such as \BB\ or ABACUS,
a {\em cut} and a {\em row} are {\bf fundamentally different objects}. 
A {\em cut} (also referred to as a {\em
constraint}) is a user-defined representation of an abstract object
which can only be realized as a row in an LP matrix {\bf with respect
to a particular set of active variables}. Similarly, a {\em variable}
is a representation which can only be realized as a column of an LP
matrix {\bf with respect to a particular set of cuts}. This
distinction between the {\em representation} and the {\em realization}
of objects is a crucial design element and is what allows us to
effectively address some of the challenges inherent in BCP. In the
remainder of this section, we will further discuss this distinction
and the details of how it is implemented.

%In later sections, we will discuss the computational issues involved
%in the efficient processing of individual subproblem.

\subsubsection{Variables and Cuts}
\label{variables-cuts}

Although their algorithmic roles are different, variables and cuts as objects
are treated identically in \BB. We will describe the various types of
variables.

The variables are divided into two main groups, core variables and extra
variables. The core variables are active in all subproblems, whereas the extra
variables can be added and removed. There is no theoretical difference between
core and extra variables; however, designating a well-chosen set of core
variables can significantly increase efficiency. Because they can move in and
out of the problem, maintaining extra variables requires additional
bookkeeping and computation. If the user has reason to believe a priori that a
variable is ``good'' or has a high probability of having a non-zero value in
some optimal solution to the problem, then that variable should be designated
as a core variable. It is up to the user to designate which variables should
be active in the root subproblem. Typically, only core variables are active,
but there are times when extra variables are also included. Note that using
extra variables is only necessary if the user wishes to take advantage of the
column-generation features of the framework. For problems with a moderate
number of variables, it is probably more efficient to designate every variable
as core variable.

The extra variables are also subdivided into two category. First, there are
the indexed variables which are represented by a unique global user index
which is (as the name suggests) assigned to these variables by the user. This
index represents each variable's position in a ``virtual'' global list known
only to the user. The main requirement of this indexing scheme is that, given
an index and a list of active cuts, the user must be able to generate the
corresponding column to be added to the matrix. For example, in problems
where the variables correspond to the edges of an underlying graph, the index
could be derived from a lexicographic ordering of the edges.

The indexing scheme provides a very compact representation, as well as a
simple and effective means of moving variables in and out of the active set.
However, it means that the user must have a priori knowledge of all problem
variables and a method for indexing them. For combinatorial models such as the
Traveling Salesman Problem, this usually does not present a problem. 
However, for airline schedule planning models, for instance, the number of
columns (each one corresponds to a possible plane route) is not known in 
advance. In such cases the user may use algorithmic variables. For
algorithmic variables there must exists an algorithm that, given the set of
active constraints, can create the column corresponding to the variable. Using
the schedule planning example, the compact representation may be the
information which flight legs a particular plane is going to fly. From this
information it's easy to derive when the plane is on the ground and hence it
is easy to compute the coefficients of the column for constraints that, say,
specify that at a given time at a given airport only so many planes can be on
the ground.


To summarize the advantages and disadvantages of the various variable types:
\begin{itemize}
\item core variable: always stay in the formulation which is both good (no
  bookkeeping required and decreases communication) and bad (the LP relaxation
  will always have at least 
  those variables in the formulation); 
\item indexed variables: they can leave the formulation (good) but there are
  some bookkeeping involved and all must be accounted for in advance (bad);
  and 
\item algorithmic variables: gives absolute freedom, there can be as many as
  the user wants (good) but there is fair amount of bookkeeping involved (bad).
\end{itemize}

Now we give examples for {\em indexed} and {\em algorithmic cuts}. 
The already mentioned
``gate constraints'' for the schedule planning problem are typical indexed
cuts. There is one for every airport for every minute during the day. Most
likely very few of them would ever be violated, but they must be satisfied.
Including all as core cuts would increase the problem size enormously.
Therefore they better be generated on the fly, and since we can enumerate them
in advance, i.e., we can assign an index to each of them, they can be indexed
cuts. An algorithmic cut is, for example, a subtour elimination constraint
for the TSP. These constraint express that a tour must cross every cut at
least twice. There are so many of them ($2^n-2$ for a problem with $n$ nodes)
that we cannot enumerate all of them and assign indeces to them. Thus we need
a representation and an algorithm that computes the coefficients for every
active variable. A compact representation could be the list of graph nodes on
the smaller side of the cut. From this it is easy to deduce which variables
(edges) are in the cut, i.e., we can compute the coefficients.

% Note again that the user is not {\em required} to designate a compact
% representation scheme. Cuts can simply be represented explicitly as
% matrix rows using the global set of variables. However, designating a
% compact form can result in large reductions in memory use if the number
% of variables in the problem is large. 

\subsubsection{Search Tree}

Having described the basics of how objects are represented, we now describe
the representation of search tree nodes. Since the core constraints and
variables are present in every subproblem, only the indices of the extra
constraints and variables are stored in each node's description. Also warm
starting information is maintained at the search tree nodes to speed up
solving the LP relaxation when the processing of a search tree node begins.
This warm start information is either inherited from the parent or comes from
earlier partial processing of the node itself (see Section \ref{two-phase}).
Along with the set of active objects, we must also store the branching
information that was used to generate the node. The branching operation is
described in Section \ref{branching}.

Because the set of active objects and the LP solution (hence the warm starting
information) do not tend to change much from parent to child, all of these
data are stored as differences with respect to the parent when that
description is smaller than the explicit one. This method of storing the
entire tree is highly memory-efficient. The list of nodes that are candidates
for processing is stored in a heap ordered by a comparison function defined by
the search strategy (see \ref{tree-management}). This allows efficient
generation of the next node to be processed.

\subsection{Modular Implementation}

\BB's functions are currently grouped into four independent computational
modules. This modular implementation not only facilitates code maintenance,
but also allows easy and highly configurable parallelization. All modules are
present in the executable file but depending on the computational setting,
either they run alternating thus executing the algorithm as a serial process
or in each process only one module will be running thus executing the
algorithm in parallel over a network. The modules pass data through a
message-passing protocol defined in a separate communications API. In the
remainder of the section, we describe the modularization scheme and the
implementation of each module in a sequential environment. We will defer
serious discussion of the issues involved in parallel execution of the code
until Section \ref{parallelization}.

%\begin{figure}
%\centering
%\psfig{figure=bcp.eps}
%\caption{Schematic overview of the branch, cut, and price algorithm}
%\label{overview}
%\end{figure}

%\begin{figure}
%\framebox[5.75in]{
%\begin{minipage}{5.25in}
%\vskip .1in
%{\rm
%{\bf Parallel Branch and Cut Algorithm}\\
%\underbar{Input:} A data array specifying the problem instance. \\
%\underbar{Output:} The optimal solution $x^*$ to the problem instance.\\
%{\bf Step 1.} If both the active node and candidate node
%lists are empty, then the algorithm has finished. Report run data to
%the master program and exit.\\
%{\bf Step 2.} If there is an idle LP process, then select the ``best''
%subproblem in the candidate list and send it to the idle process.
%Continue to execute this step until either the candidate node list is
%empty or all LP's are busy.\\
%{\bf Step 3.} Otherwise, wait for a message to arrive and process it
%according to the following list:
%\begin{list}{}
%       \item {\tt UPPER BOUND:} Receive the new upper bound and
%broadcast it to all other LP processes.
%       \item {\tt LP IS FREE:} This message indicates that the sender
%is an LP which is currently idle and requests work. If there are 
%candidate nodes on the list, then send one out to this
%process. Otherwise, just mark that LP process as idle.
%       \item {\tt CANDIDATE NODE DATA:} Indicates that the message 
%contains data for a newly generated subproblem to be added to the 
%candidate node list.
%\end{list}
%\noindent Go to Step 1.}
%\end{minipage}
%}
%\caption{Management of the parallel branch and cut algorithm}
%\label{pb&ca}
%\end{figure}

\subsubsection{The Tree Manager Module}
\label{master-process}

The {\em tree manager module} (TM) first performs problem initialization
and I/O and then becomes the master process controlling the overall
execution of the algorithm. It tracks the status of all processes, as
well as that of the search tree, and distributes the subproblems to be
processed to the LP module(s). Specific functions performed by the
tree manager module are:
%\underbar{Overall Function:} Handle input/output, maintain the data
%for the problem instance and serve requests to send out that
%data. Keep track of the best solution found so far.\\
%\underbar{Specific Functions:}
\begin{itemize}
\item Read in the parameters from a data file.
\item Read in the data for the problem instance.
\item Compute an initial upper bound using heuristics.
\item Perform problem preprocessing.
\item Initialize the BCP algorithm by constructing the root node.
\item Initialize output devices and act as a central repository for output.
\item Process requests for problem data.
\item Receive new solutions and store the best one.
\item Receive data for subproblems to be held for later processing.
\item Handle requests from linear programming modules to
  release a subproblem for processing.
\item Receive branching object information, set up data structures
  for the children, and add them to the list of candidate subproblems.
\item Keep track of the global upper bound and notify all LP
  processes when it changes.
\item Write current state information out to disk periodically
  to allow a warm restart in the event of a system crash.
\item Receive the message that the algorithm is finished and
  print out run data.
\end{itemize}

\subsubsection{The Linear Programming Module}

The {\em linear programming} (LP) module is the most complex and
computationally intensive of the four processes. Its job is to perform
the bounding and branching operations. These operations
are, of course, central to the performance of the algorithm. Functions
performed by the LP module are:
%\underbar{Overall Function:} Process and bound subproblems. Branch and
%produce new subproblems. \\
%\underbar{Specific Functions:} 
\begin{itemize}
\item Inform the tree manager when a new subproblem is needed.
\item Receive a subproblem. Process the subproblem in conjunction
  with the cut generator. % and the cut pool.
\item If necessary, choose a branching object and send its
  description back to the tree manager.
\end{itemize} 

\subsubsection{The Cut Generator Module}

The {\em cut generator} performs only one function -- generating valid
inequalities violated by the current fractional solution and sending
them back to the requesting LP process. Here are the functions
performed by the cut generator module:
%\underbar{Overall Function:} Receive solution vectors from the LP
%processes and generate valid inequalities violated by these vectors.\\
%\underbar{Specific Functions:}
\begin{itemize}
\item Receive an LP solution and attempt to separate it from the convex hull
  of all solutions. 
\item Send generated valid inequalities back to the LP solver.  
\item When finished processing a solution vector, inform the
  LP not to expect any more cuts in case it is still waiting.
\end{itemize}

\subsubsection{The Variable Generator Module}

The function of the {\em variable generator} (VG) is dual to that of the
cut generator. Given a dual solution vector, the variable generator
attempts to generate variables with negative reduced cost and sends
them back to the requesting LP process if any are found. Here are the
functions performed by the variable generator module:
%\underbar{Overall Function:} Receive solution vectors from the LP
%processes and generate valid inequalities violated by these vectors.\\
%\underbar{Specific Functions:}
\begin{itemize}
\item Receive a set of dual values and attempt to generate variables with
  negative reduced cost. 
\item Send generated variables back to the LP solver.   
\item When finished processing a dual solution vector, inform the
  LP not to expect any more variables in case it is still waiting.
\end{itemize}

%\subsubsection{The Cut Pool Module}
%
%The concept of a {\em cut pool} was first suggested by Padberg and
%Rinaldi \cite{P&R}, and is based on the observation that in BCP, the
%inequalities which are generated while processing a particular node in
%the search tree are also generally valid and potentially useful at
%other nodes. Since generating these cuts is usually a relatively
%expensive operation, the cut pool maintains a list of the ``best'' or
%``strongest'' cuts found in the tree so far for use in processing
%future subproblems. Hence, the cut pool functions as an auxiliary cut
%generator. More explicitly, here are the functions of the cut pool
%module:

%%\underbar{Overall Function:} Maintain a list of ``effective'' valid
%%inequalities for use in processing the subproblems.\\
%%\underbar{Specific Functions:}

%\begin{itemize}
%       \item Receive cuts generated by other processes and store them
%in the pool.
%       \item Receive an LP solution and return a
%set of cuts from the pool which this solution violates.
%       \item Periodically purge ``ineffective'' and duplicate cuts
%from the pool to control its size.
%\end{itemize}

\subsection{\BB\ Overview}

Currently, \BB\ is what is known as a single-pool BCP algorithm.
The term {\em single-pool} refers to the fact that there is a single
central list of candidate subproblems to be processed, which is
maintained by the tree manager. Most sequential implementations use
such a single-pool scheme. However, other schemes may be used in
parallel implementations. For a description of various types of
parallel branch and bound, see \cite{A:gendron-crainic}.

The tree manager module begins by reading in the parameters and
problem data. After initial I/O is completed, subroutines for finding
an initial upper bound and constructing the root node are executed.
During construction of the root node, the user must designate the
initial set of active cuts and variables, after which the data for the
root node are used to initialize the list of candidate nodes. The tree
manager then sets up the cut pool module(s), the linear programming
module(s), and the cut generator module(s). All LP modules are marked
as idle. The algorithm is now ready for execution.

In the steady state, the tree manager controls the execution by
maintaining the list of candidate subproblems and sending them to the
LP modules as they become idle. The LP modules receive nodes from
the tree manager, process them, branch (if required), and send back
the identity of the chosen branching object to the tree manager, which
in turn generates the children and places them on the list of
candidates to be processed.

The preference ordering for processing nodes is a run-time parameter (or can
be controlled by a user-defined method).
Typically, the node with the smallest lower bound is chosen to be
processed next since this strategy minimizes the overall size of the
search tree. However, at times, it will be advantageous to {\em dive}
down in the tree. The concepts of {\em diving} and {\em search
chains}, introduced in Section \ref{tree-management}, extend the basic
``best-first'' approach.


%\section{The Design of \BB}
%\label{design}

%\BB\ was designed with two major goals in mind---effectiveness for 
%a wide variety of problem settings and ease of use. The effectiveness of
%\BB\ stems from the enhancements and extensions to the generic
%algorithm (to be described in this section), most of which are
%transparent to the casual user. The ease of use comes from the
%well-designed user interface to the library. To implement a branch and
%cut algorithm, the user provides files containing C subroutines that
%implement program functions requiring knowledge of the problem
%setting. The most obvious example of this is separation subroutines,
%which are a mainstay of any branch and cut implementation. Although it
%is possible to use generic separation routines, the most effective
%algorithms are those that utilize problem structure in searching
%for violated constraints. In addition to the required subroutines, the
%user can provide other optional subroutines that customize the
%execution of the algorithm. The interfaces between the library and the
%user functions are straightforward and do not require the user to have
%any knowledge of the inner workings of \BB.
%
%\subsection{Computing Environment}

%\BB\ is a highly flexible and easy-to-use environment. The same
%source code can be built for either shared-memory or
%distributed-memory environments. The distributed version of \BB
%requires the {\em \htmladdnormallink{Parallel Virtual
%Machine}{http://www.ccs.ornl.gov/pvm/}} (PVM) message-passing library,
%which is available free for most platforms from Oak Ridge National
%Laboratories \cite{pvm}. Compiling the code for shared memory
%architectures requires an OpenMP compliant compiler.

\section{Details of the Implementation}
\label{modules}

\subsection{The Tree Manager Module}
\label{master}

The primary functions performed by the tree manager were listed in
Section \ref{master-process}. During initialization, the user can
provide a routine to read problem-specific parameters in from the
parameter file. She can also provide a subroutine for upper bounding
if desired, though upper bounds can also be provided explicitly. A
good initial upper bound can dramatically decrease the solution time
by allowing more variable-fixing and earlier pruning of search tree
nodes. If no upper bounding subroutine is available, then the
two-phase algorithm, in which a good upper bound is found quickly in
the first phase using a reduced set of variables can be advantageous.
See Section \ref{two-phase} for details. The user's only unavoidable
obligation during preprocessing is to specify the core of the problem, that
is, the list of core variables and cuts as well as the corresponding matrix.
If desired, a list of extra variables and cuts that are to be active in the
root node can be specified. Again, we point out that selecting a good set
of core variables can make a marked difference in solution speed,
especially using the two-phase algorithm.

\subsubsection{Search Chains and Diving}
\label{tree-management}

Once execution of the algorithm begins, the tree manager's primary job
is to guide the search by deciding which candidate node should be
chosen as the next to be processed. This is done using either one of the
several built-in rules or a user-specified method. 
As mentioned earlier, we typically choose the
node with the smallest lower bound because this rule minimizes
the size of the search tree. However, there are several reasons why we
might want to deviate from this rule. 

One reason for not strictly enforcing the search order is because it
is somewhat expensive to construct a search node, send it to the LP
solver and set it up for processing. If, after branching, we choose to
continue processing one of the children of the current subproblem, we
avoid the set-up cost, as well as the cost of communicating the node
description of the retained child subproblem back to the tree manager.
This is called {\em diving} and the resulting chain of nodes is called
a {\em search chain}. There are a number of rules for deciding when an
LP process should be allowed to dive. One such rule is to look at the
number of variables in the current LP solution that have fractional
values (i.e., are causing infeasibility). When this number is low,
there is a good chance of finding a feasible integer solution quickly
by diving. This rule has the advantage of not requiring any global
information.

We also dive if one of the children is ``close'' to being the best
node, where ``close'' is defined by a chosen parameter. In addition to
the time saved by avoiding reconstruction of the LP in the child,
diving has the apparent advantage of quickly leading to the discovery
of feasible solutions and hence better upper bounds. Since every
feasible solution lies at the end of a search chain, it is reasonable
to dive periodically if there is reason to believe the current upper
bound is not very good. Therefore, random diving also takes place
according to a specified parameter.

\subsubsection{The Two-Phase Algorithm}
\label{two-phase}

As in branch and bound, finding good feasible solutions quickly is
critical to the efficiency of the algorithm. Good feasible solutions
provide upper bounds, which in turn allow us to prune unpromising
nodes and process other nodes more efficiently. There are several ways
in which feasible solutions can be found. First, the user can provide
a subroutine that derives an upper bound through heuristic techniques
that will be run before beginning to explore the branch and cut tree.
Providing a good initial upper bound can dramatically decrease the
overall solution time. Another way of finding feasible solutions is to
discover them while exploring the search tree, as discussed above.

If no upper bounding subroutine is available, then a unique two-phase
algorithm can also be invoked. In the two-phase method, the algorithm
is first run to completion on the specified set of core variables. Any
node that would have been pruned in the first phase is sent to a pool
of candidates for the second phase instead. If the set of core
variables is small, but well-chosen, this first phase should be quick
and should result in a near-optimal solution, and hence a good upper
bound. In addition, the first phase will produce a list of useful
cuts. Using the upper bound and the list of cuts from the first phase,
the root node is {\em repriced} -- that is, it is reprocessed with the
full set of variables and cuts, the hope being that most or all of the
variables not included in the first phase will be priced out of the
problem in the new root node. Any variable so priced out can be
eliminated from the problem globally. If we are successful at pricing
out all the inactive variables, we have shown that the solution from
the first phase was, in fact, optimal. If not, we must go back and
price out the (reduced) set of extra variables in each one of the
leaves of the search tree produced during the first phase. We then
continue processing any node in which we fail to price out all the
variables. 

In order to avoid pricing variables in every leaf of the tree, we can
{\em trim the tree} before the start of the second phase. Trimming the
tree consists of eliminating the children of any node whose
aforementioned children all have lower bounds above the current upper
bound. We then reprocess the parent node itself. This is typically
more efficient since there is a high probability that, given the new
upper bound and cuts, we will be able to prune the parent node and
save the work of processing each child individually.

%The tree manager's primary job is to control the execution of the
%algorithm by deciding which candidate node should be chosen as the
%next to be processed. This is done using one of the several built-in
%rules such as selecting the node with the lowest lower bound. Because
%it is expensive to construct a search node from scratch, the tree
%manager will often allow an LP process to retain one of the children
%resulting from branching in order to avoid the set-up costs associated
%with redistributing that node at a later time. This is called {\em
%diving} and the resulting chain of nodes is called a {\em search
%chain}. There are various rules available for deciding when an LP
%process should be allowed to dive. One such rule is to look at the
%number of variables in the current LP solution that are fractional.
%When this number is low, there is a good chance of finding a feasible
%solution quickly by diving. We also dive if one of the children is
%``close'' to being the best node, where ``close'' is defined by a
%chosen parameter. In addition to the time saved by avoiding
%reconstruction of the LP in the child, diving has the apparent
%advantage of leading to the discovery of feasible solutions quickly.
%Since every feasible solution lies at the end of a search chain, it
%seems reasonable to dive periodically. Therefore, random diving takes
%place according to a specified parameter.

%\subsubsection{Finding Feasible Solutions}
%\label{master}

%As in branch and bound, finding good feasible solutions quickly is
%critical to the efficiency of the algorithm. Good feasible solutions
%provide upper bounds, which in turn allow us to prune unpromising
%nodes. Using techniques from mathematical programming, good upper
%bounds can also allow us to process promising subproblems more
%efficiently. This issue is again even more important in a parallel
%setting.

%There are several ways in which feasible solutions can be found.
%First, the user can provide a subroutine that derives an upper bound
%through heuristic techniques that will be run before beginning to
%explore the branch and cut tree. Providing a good initial upper bound
%can dramatically decrease the overall solution time. If the upper
%bounding subroutine is sequential, however, one must be careful since
%this inherently limits speedup (recall Amdahl). If no upper bounding
%subroutine is available, then a unique two-phase algorithm (available
%in \BB), in which a good upper bound is found quickly in the
%first phase using a reduced set of variables, can be employed as a
%substitute. Another way of finding feasible solutions is to discover
%them while exploring the search tree. This will be discussed in the
%next section.

\subsection{The LP Module}

\subsubsection{The LP Engine}

\BB\ requires the use of a third-party callable library (referred
to as the {\em LP engine} or {\em LP library}) to solve the LP
relaxations once they are formulated. \BB\ communicates with the LP engine
through the {\em Open Solver Interface} (OSI) an API that provides a uniform
API to various LP solvers. Therefore \BB\ is able to work with any LP engine
that has an OSI interface (currently OSL, CPLEX, XPRESS-MP and the Volume
Algorithm has OSI interfaces). OSI is also part of the COIN \cite{W:coin-or}
project.

\subsubsection{Managing the LP Relaxation}
\label{lp-relaxation}

The majority of the computational effort of branch and cut is spent
solving LPs and hence a major emphasis in the development was to make
this process as efficient as possible. Besides using a good LP engine,
the primary way in which this is done is by controlling the size of
each relaxation, both in terms of number of active variables and
number of active constraints. 

The number of constraints is controlled through use of a local cut
pool and through purging of ineffective constraints. When a cut is
generated by the cut generator, it is first sent to the local cut
pool. In each iteration, up to a specified number of the strongest
cuts (measured by degree of violation) from the local pool are added
to the problem. Cuts that are not strong enough to be added to the
relaxation are eventually purged from the list. In addition, cuts are
purged from the LP itself when they have been deemed ineffective for
more than a specified number of iterations and the lower bound on the LP
relaxation has increased since the cut was added to the formulation. 
The meaning of the term ``ineffective'' can be specified by a parameter and
it is defined as either (1) the corresponding slack variable is positive or
(3) the dual value corresponding to the row is zero. The second condition for
purging a cut is necessary to avoid cycling.

The number of variables (columns) in the relaxation is controlled
through {\em reduced cost fixing} and {\em dynamic column generation}.
Periodically, each active variable is {\em priced} to see if it can be
tightened based on their reduced cost. Note that a variable can be tightened
by reduced cost fixing only if {\em every} extra variable is known to price
out (has non-negative reduced cost). Also, in every iteration the user is
given the opportunity to tighten bounds on any variable.

FIXME: ... Must write some more about dynamic column generation ...

%FIXME: May need to better describe column generation here, including
%algorithmic variables, etc.
%Dynamic column generation is costly and hence takes place only either
%(1) before branching (optional), or (2) when a node is about to be
%pruned (depending on the phase---see the description of the two-phase
%algorithm in Section \ref{two-phase}). To use dynamic column
%generation, the user must supply a subroutine which generates the
%column corresponding to a particular user index, given the list of
%active constraints in the current relaxation. When column generation
%occurs, each column not currently active that has not been previously
%priced out is either priced out immediately, or becomes active in the
%current relaxation. Only a specified number of columns may enter the
%problem at a time, so when that limit is reached, column generation
%ceases. Further discussion of column generation will take place in
%Section \ref{two-phase}, where the two-phase algorithm is described.

%Since the matrix is stored in compressed form, it can be expensive to
%add and remove rows and columns. Hence, rows and columns are only
%physically removed from the problem when there are enough of them to
%make it ``worthwhile.'' Otherwise, deleted rows and columns remain in
%the matrix but are simply ignored by the computation. This is
%a convenient way to handle row deletion since rows
%are expensive to delete from a column-ordered matrix and they tend to
%move in and out more frequently.

\subsubsection{Branching}
\label{branching}

Branching takes place whenever either (1) both cut generation and
column generation (if it is performed) have failed; (2) ``tailing
off'' in the objective function value has been detected (if this
option is selected); or (3) the user chooses to force
branching. A general {\em branching object} specifies new bounds for a set of
variables and/or cuts in every children. The well-known 
{\em branching variable} is a special case: a fractional variable is selected
and two children are created as usual. Selecting a branching object can be
fully automated (in which case branching variables are selected) or fully
controlled by the user, as desired. Branching can result in as many children
as the user desires though two is typical.
Once it is decided that branching will occur, the user must
either select the list of candidates for {\em strong branching} (see
below for the procedure) or allow \BB\ to do so automatically
by using one of several built-in strategies, such as branching on the
variable whose value is farthest from integrality. The number of
candidates can depend on the level of the current node in the tree.
For instance, it is usually best to expend more effort on branching
near the top of the tree where it is more ``important''.

After the list of candidates is selected, each candidate is {\em
presolved}, i.e., a quick near-optimization is done (like performing a
specified number of iterations of the dual simplex algorithm) 
in each of the resulting subproblems. Based on
the objective function values obtained in each of the potential
children, the final branching object is selected, again either by the
user or by built-in rule. When the branching object has been selected,
the LP process sends a description of that object to the tree manager,
which then creates the children and adds them to the list of candidate
nodes. It is then up to the tree manager to specify which node the
now-idle LP process should process next. That issue will be addressed
in Section \ref{tree-management} below.

\subsection{The Cut Generator Module}

To implement the cut generator process, the user must provide a
method that accepts an LP solution and returns cuts violated by that
solution to the LP module. In parallel configurations, each cut is
returned immediately to the LP module, rather than being passed back
as a group once the function exits. This allows the LP to begin adding
cuts and solving the current relaxation before the cut generator is
finished if desired. Parameters controlling if and when the LP should
begin solving the relaxation before the cut generator is finished can
be set by the user.

\subsection{The Variable Generator Module}

The variable generator functions very similarly to the cut generator.
To implement the variable generator process, the user must provide a
method that accepts a dual solution vector and returns variables
with negative reduced cost. As with the cut generator, in parallel
configurations, each variable is returned immediately to the LP
module, rather than being passed back as a group once the function
exits. This allows the LP to begin adding variables and solving the
current relaxation before the variable generator is finished if
desired. Parameters controlling if and when the LP should begin
solving the relaxation before the variable generator is finished can
be set by the user.

%\subsection{The Cut Pool Module}
%
%\subsubsection{Maintaining and Scanning the Pool}
%
%The cut pool's primary job is to receive a fractional solution from an
%LP process and return cuts from the pool that are violated by it. The
%cuts are stored along with two pieces of information---the level of
%the tree on which the cut was generated, known simply as the {\em
%level} of the cut, and the number of times it has been checked for
%violation since the last time it was actually found to be violated,
%known as the number of {\em touches}. The number of touches
%can be used as a simplistic measure of its effectiveness. Since the pool
%can get quite large, the user can choose to scan only cuts whose
%number of touches is below a specified threshold and/or cuts that were
%generated on a level at or above the current one in the tree. The idea
%behind this second criteria is to try to avoid checking cuts that were
%not generated ``nearby'' in the tree, as they are less likely to be
%effective. Any cut that was generated at a level in the tree that is
%below the level of the current node must have been generated in a
%different part of the tree. This is admittedly a naive method. 
%
%On the other hand, the user may define her own measure of quality for
%each cut and that will be used instead. For example, the degree of
%violation is a simple example. This measure of quality must be
%computed by the user since the cut pool does not know anything about
%the packed cuts. The quality is recomputed every time the user checks
%the cut for violation and a running average is used as the final
%quality measure. The cuts in the pool are periodically sorted by this
%measure of quality and only the highest quality cuts are checked each
%time. All duplicate cuts, as well as all cuts whose number of touches
%has exceeded or quality is below a specified threshold are
%periodically purged from the pool to keep it as small as possible.
%
%\subsubsection{Using Multiple Pools}
%\label{multi-cut-pools}
%
%For several reasons, it may be desirable to have multiple cut pools.
%When there are multiple cut pools, each pool is initially assigned
%to a particular node in the search tree. After being assigned to that
%node, the pool services requests for cuts from that node and all
%of its descendants until such time as one of its descendants gets
%assigned to another cut pool. After that, it continues to
%serve all the descendants of its assigned node that are not assigned
%to other cut pools.
%
%Initially, the first cut pool is assigned to the root
%node. All other cut pools are unassigned. During execution, when a new
%node is sent to be processed, the tree manager must determine
%which cut pool the node should be serviced by. The default is to use
%the same cut pool as its parent. However, if there is currently an
%idle cut pool process (either it has never been assigned to any node
%or all the descendants of its assigned node have been processed or
%reassigned), then that cut pool is assigned to this new node. All the
%cuts currently in the cut pool of its parent node are copied to the
%new pool to initialize it, after which the two pools operate
%independently on their respective subtrees. When generating cuts, the
%LP process sends the new cuts to the cut pool assigned to
%service the node during whose processing the cuts were generated.
%
%The primary motivation behind the idea of multiple cut pools is
%two-fold. First, we want simply to limit the size of each pool as
%much as possible. By limiting the number of nodes that a cut pool has
%to service, the number of cuts in the pool will be similarly limited.
%This not only allows cut storage to spread over multiple processors,
%and hence increases the available memory, but at the same time, the
%efficiency with which the cut pool can be scanned for violated cuts is
%also increased. A secondary reason for maintaining multiple cut pools is
%that it allows us to limit the scanning of cuts to only those that
%were generated in the same subtree as the current search node. As
%described above, this helps focus the search and should increase the
%efficiency and effectiveness of the search.

\section{Parallelizing \BB}
\label{parallelizing}

Because of the clear partitioning of work that occurs when the
branching operation generates new subproblems, branch and bound
algorithms lend themselves well to parallelization. As a result, there
is already a significant body of research on performing branch and
bound in parallel environments. We again point the reader to the
survey of parallel branch and bound algorithms by Gendron and Crainic
\cite{A:gendron-crainic}.

In parallel BCP, as in general branch and bound, there are two major
sources of parallelism. First, it is clear that any number of
subproblems on the current candidate list can be processed
simultaneously. Once a subproblem has been added to the list, it can
be properly processed before, during, or after the processing of any
other subproblem. This is not to say that processing a particular node
at a different point in the algorithm won't produce different
results -- it most certainly will -- but the algorithm will terminate
correctly in any case. The second major source of parallelism is to
parallelize the processing of individual subproblems. By allowing
separation to be performed in parallel with the solution of the linear
programs, we can theoretically process a node in little more than the
amount of time it takes to solve the sequence of LP relaxations. Both
of these sources of parallelism can be easily exploited using the
\BB\ framework.

The most straightforward parallel implementation, which is the one we
currently employ, is a master-slave model, in which there is a central
manager responsible for partitioning the work and parceling it out to
the various slave processes that perform the actual computation. The
reason we chose this approach is because it allows memory-efficient
data structures for sequential computation and yet is conceptually
easy to parallelized. This approach has limited scalability, but given
the tradeoffs, we decided to accept that for the time-being. In future
versions of the software, we hope to ``decentralize'' the
implementation in order to allow better scalability. see \cite{W:pico}
for an idea of how this could be done.

\subsection{Parallel Execution and Inter-process Communication}

\BB\ supports both a sequential and a parallel, distributed execution. All the
user has to specify is the message passing protocol to be used. At the moment
\BB\ has interfaces to the Parallel Virtual Machine (PVM) \cite{W:pvm} protocol
and to a single process protocol that is used to execute the algorithm
sequentially. This latter protocol emulates being parallel thus there is no
need to change anything in \BB\ or in the user code to do serial execution.
(Granted, because of the emulation the serial code at the moment has
significant overheads.) Theoretically \BB\ can utilize any third-party
communication protocol supporting dynamic spawning of processes and basic
message-passing functions. All communication subroutines interface with
\BB\ through a separate communications API. As mentioned above, currently
PVM is the only message-passing protocol supported, but interfacing with
another protocol is a straightforward exercise.

\subsection{Fault Tolerance}
\label{fault-tolerance} 

Fault tolerance is an important consideration for solving large problems on
networks whose nodes may fail unpredictably. The tree manager tracks the
status of all processes and can restart them as necessary. It doesn't matter
(too much) if a slave process is killed, the most that can be lost is the work
that had been completed on that particular search tree node. Furthermore, new
processors can be added to the parallel configuration on the fly
and the TM process can spawn new slaves on those processes.
