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

\section{Introducing SYMPHONY \VER}
\label{whats-new}

Welcome to the SYMPHONY Version \VER\ user's manual. Whether you are a new
user or simply upgrading, this manual will help you get started with what we
hope you will find to be a useful and powerful framework for solving
mixed-integer linear programs (MILP) sequentially or in parallel. The
subroutines in the \BB\ library comprise a state-of-the-art MILP solver with a
modular design that makes it easy to customize for various problem settings.
SYMPHONY works out of the box as a generic MILP solver that can be invoked
from the command line, through an interactive shell, or by linking to the
provided callable library, which has both C and C++ interfaces with a look and
feel similar to that of other popular solvers (see Sections \ref{C_Interface}
and \ref{C++_Interface} for the library routines). Models can be read in MPS
or GMPL (a subset of AMPL) format, as well as by interfacing with more
powerful modeling environments, such as FlopC++ (also provided with the
distribution). To develop a customized SYMPHONY application, various callbacks
can be written and parameters set that modify the default behavior of the
algorithm. Section~\ref{callback} contains an overview of the API for these
subroutines. Files containing function stubs are provided with the
distribution.

SYMPHONY can be built on almost any platform and can be configured either for
serial computation or in a wide variety of parallel modes. The parallel
version can be built for either a fully distributed environment (network of
workstations) or a shared-memory environment simply by changing a few
configuration options (see Chapter~\ref{getting_started}). To run in a
distributed environment, the user must have installed the {\em
\htmladdnormallink{Parallel Virtual Machine}{http://www.ccs.ornl.gov/pvm/}}
(PVM), available for free from Oak Ridge National Laboratories. To run in a
shared-memory environment, the user must have installed an OpenMP compliant
compiler (gcc 4.2 is currently the only compiler tested and fully supported).

\section{What's New}

In SYMPHONY 5.0, we introduced a number of new features that give SYMPHONY
some unique capabilities. These include the ability to solve biobjective
integer programs, the ability to warms start the solution procedure, and the
ability to perform basic sensitivity analyses. These capabilities have been
further developed and enhanced in Version \VER. Other new features and
enhancements are listed below.

\begin{itemize}

\item SYMPHONY now has an interactive optimizer that can be used through a
command shell. In both the sequential and parallel configurations, the user
can set parameters, load and solve instances interactively, and display
results and statistics. For Windows users, this means that SYMPHONY can be
invoked using the familiar procedure of ``double-clicking'' on the
\code{symphony.exe} file in Windows Explorer.

\item SYMPHONY now supports automatic configuration using the new COIN-OR
build system and the GNU autotools. Using the autotools, it is now possible to
build SYMPHONY in most operating systems and with most common compilers
without user intervention.

\item Both the distributed and shared memory parallel configurations are once
  again fully implemented, tested, and supported. The user can now build and
  execute custom SYMPHONY applications in parallel, as well as solving generic
  MILPs in parallel "out of the box."

\item There are now additional options for warm starting. The user can trim the
warm starting tree before starting to resolve a problem. More specifically,
the user can decide to initiate warm starting with a predefined partition of
the final branch-and-cut tree resulting from a previous solution procedure.
This partition can include either a number of nodes created first during the
solution procedure or all of the nodes above a given level of the tree.

\item The COIN-OR repository, the current host of SYMPHONY has
  recently undergone some significant improvements of its own that have
  resulted in improved services to users, detailed below. 

\begin{itemize}

\item SYMPHONY has a new development Web site, where users can submit trouble
  tickets, browse the source code interactively, and get up-to-date
  information on development. The address of the new site is
  \url{https://projects.coin-or.org/SYMPHONY}.

\item SYMPHONY is now hosted using subversion, a version control system with
  features vastly improved over CVS, the previous hosting software. This has
  required some reorganization and renaming of the header files.

\item SYMPHONY is now more tightly integrated with other COIN-OR projects. Due
  to improved procedures for producing stable releases, it will now be much
  easier for us to determine the exact version of SYMPHONY and all other COIN
  projects you are using when you report a bug.

\item SYMPHONY is now distributed with all COIN software needed to build a
  complete solver. Previously, other COIN software packages had to be
  downloaded and installed separately.

\end{itemize}

\end{itemize}

Two features have been deprecated and are no longer supported:

\begin{itemize}

\item The native interfaces to OSL and CPLEX are now deprecated and no longer
supported. These solvers can be called through the COIN-OR OSI interface.

\item Column generation functionality has also been officially deprecated. For
now, there are a number of other software packages that offer better
functionality than SYMPHONY for implementing branch and price algorithms.

\end{itemize}

There were a few minor changes to the API from the previous version of
SYMPHONY to version \VER. 

\begin{itemize}

\item First and foremost, the name of the main header file for SYMPHONY has
been changed from \code{symphony\_api.h} to \code{symphony.h} (though the
former has been retained for backward compatibility purposes).

\item The user can now execute a primal heuristic in the
\ptt{user\_is\_feasible()} callback and return the solution to SYMPHONY, which
required the arguments of this function to be changed slightly.

\item Several new subroutines were added to the callable library API.

\end{itemize}

\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{How to Use This Manual}

The manual is divided into six chapters. The first is the introduction, which
you are reading now. Chapter \ref{getting_started} describes how to install
SYMPHONY from either a source or binary distribution. If you have already
managed to get SYMPHONY running using the instructions in the \code{README}
file, you might want to skip to Chapter~\ref{API-overview}. However, keep in
mind that the manual contains additional details for customizing your build.
Chapter \ref{API-overview} contains an overview of how to use in all three
major modes---as a black-box solver through the interactive shell or on the
command line, as a callable library, and as a customizable framework. Chapter
\ref{SYMPHONY-design} contains further depth and a more complete technical
description of the design and implementation of SYMPHONY. In Section
\ref{design}, we describe the overall design of SYMPHONY without reference to
the implementational details and with only passing reference to parallelism.
In Section \ref{modules}, we discuss the details of the implementation. In
Section \ref{parallelizing}, we briefly discuss issues involved in parallel
execution of SYMPHONY. Chapter \ref{SYMPHONY-development} describes in detail
how to develop a custom application using SYMPHONY. Note that it is not
necessary to read Chapter \ref{SYMPHONY-design} before undertaking development
of a SYMPHONY application, but it may help. Chapter \ref{SYMPHONY-reference}
contains reference material. Section \ref{C_Interface} contains a description
of the native C interface for the callable library. Section
\ref{C++_Interface} contains a description of the interface for C++
environments. Section \ref{API} contains a description of the user callback
functions. SYMPHONY's parameters are described in Section \ref{params}. For
reference use, the HTML version of this manual may be more practical, as the
embedded hyperlinks make it easier to navigate.

\section{Getting Additional Help}
\label{resources}

The main point of entry for additional help, trouble-shooting, and
problem-solving is the SYMPHONY Wiki and development Web site at
\begin{center}
\url{https://projects.coin-or.org/SYMPHONY}
\end{center}
There, bug reports can be submitted by clicking on the ``New Ticket'' button
and also previous bug reports searched. For general questions, there is also a
\BB\ user's mailing list. To subscribe, visit
\begin{center}
\url{http://list.coin-or.org/mailman/listinfo/coin-symphony}
\end{center}


