# source:trunk/SYMPHONY/Doc/man-intro.tex@1614

Last change on this file since 1614 was 1614, checked in by tkr, 5 years ago

Updating version numbers

• Property svn:eol-style set to native
• Property svn:keywords set to Author Date Id Revision
File size: 14.0 KB
Line
1%===========================================================================%
2%                                                                           %
3% This file is part of the documentation for the SYMPHONY MILP Solver.      %
4%                                                                           %
5% SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and         %
7%                                                                           %
9%                                                                           %
11% accompanying file for terms.                                              %
12%                                                                           %
13%===========================================================================%
14
15\section{Introducing SYMPHONY \VER}
16\label{whats-new}
17
18Welcome to the SYMPHONY Version \VER\ user's manual. Whether you are a new
20hope you will find to be a useful and powerful framework for solving
21mixed-integer linear programs (MILP) sequentially or in parallel. The
22subroutines in the \BB\ library comprise a state-of-the-art MILP solver with a
23modular design that makes it easy to customize for various problem settings.
24SYMPHONY works out of the box as a generic MILP solver that can be invoked
25from the command line, through an interactive shell, or by linking to the
26provided callable library, which has both C and C++ interfaces with a look and
27feel similar to that of other popular solvers (see Sections \ref{C_Interface}
28and \ref{C++_Interface} for the library routines). Models can be read in MPS
29or GMPL (a subset of AMPL) format, as well as by interfacing with more
30powerful modeling environments, such as FlopC++ (also provided with the
31distribution). To develop a customized SYMPHONY application, various callbacks
32can be written and parameters set that modify the default behavior of the
33algorithm. Section~\ref{callback} contains an overview of the API for these
34subroutines. Files containing function stubs are provided with the
35distribution.
36
37SYMPHONY can be built on almost any platform and can be configured either for
38serial computation or in a wide variety of parallel modes. The parallel
39version can be built for either a fully distributed environment (network of
40workstations) or a shared-memory environment simply by changing a few
41configuration options (see Chapter~\ref{getting_started}). To run in a
42distributed environment, the user must have installed the {\em
44(PVM), available for free from Oak Ridge National Laboratories. To run in a
45shared-memory environment, the user must have installed an OpenMP compliant
46compiler (gcc 4.2 is currently the only compiler tested and fully supported).
47
48\section{What's New}
49
50Starting in SYMPHONY 5.0, we introduced a number of new features that give
51SYMPHONY some unique capabilities. These include the ability to solve
52biobjective integer programs, the ability to warms start the solution
53procedure, and the ability to perform basic sensitivity analyses. These
54capabilities have been further developed and enhanced with the introduction of
55Versions 5.1 and 5.2. Other new features and enhancements are listed below.
56
57\begin{itemize}
58
59\item SYMPHONY has an interactive optimizer that can be used through a
60command shell. In both the sequential and parallel configurations, the user
61can set parameters, load and solve instances interactively, and display
62results and statistics. For Windows users, this means that SYMPHONY can be
63invoked using the familiar procedure of double-clicking'' on the
64\code{symphony.exe} file in Windows Explorer.
65
66\item SYMPHONY supports automatic configuration using the new COIN-OR
67build system and the GNU autotools. Using the autotools, it is now possible to
68build SYMPHONY in most operating systems and with most common compilers
69without user intervention.
70
71\item Both the distributed and shared memory parallel configurations are fully
72 implemented, tested, and supported. The user can now build and execute custom
73 SYMPHONY applications in parallel, as well as solving generic MILPs in
74 parallel "out of the box."
75
76\item There are additional options for warm starting. The user can trim the
77warm starting tree before starting to resolve a problem. More specifically,
78the user can decide to initiate warm starting with a predefined partition of
79the final branch-and-cut tree resulting from a previous solution procedure.
80This partition can include either a number of nodes created first during the
81solution procedure or all of the nodes above a given level of the tree.
82
83\item The COIN-OR repository, the current host of SYMPHONY has
84  recently undergone some significant improvements of its own that have
85  resulted in improved services to users, detailed below.
86
87\begin{itemize}
88
89\item SYMPHONY has a project management Web site, where users can submit
90  trouble tickets, browse the source code interactively, and get up-to-date
91  information on development. The address of the new site is
92  \url{https://projects.coin-or.org/SYMPHONY}.
93
94\item SYMPHONY is hosted using subversion, a version control system with
95  features vastly improved over CVS, the previous hosting software. This has
96  required some reorganization and renaming of the header files.
97
98\item SYMPHONY is tightly integrated with other COIN-OR projects. Due
99  to improved procedures for producing stable releases, it will now be much
100  easier for us to determine the exact version of SYMPHONY and all other COIN
101  projects you are using when you report a bug.
102
103\item SYMPHONY is distributed with all COIN software needed to build a
104  complete solver. Previously, other COIN software packages had to be
106
107\end{itemize}
108
109\end{itemize}
110
111Two features have been deprecated and are no longer supported:
112
113\begin{itemize}
114
115\item The native interfaces to OSL and CPLEX are now deprecated and no longer
116supported. These solvers can be called through the COIN-OR OSI interface.
117
118\item Column generation functionality has also been officially deprecated. For
119now, there are a number of other software packages that offer better
120functionality than SYMPHONY for implementing branch and price algorithms.
121
122\end{itemize}
123
125file that comes with the distribution.
126
127\section{A Brief History}
128\label{history}
129
130Since the inception of optimization as a recognized field of study in
131mathematics, researchers have been both intrigued and stymied by the
132difficulty of solving many of the most interesting classes of discrete
133optimization problems. Even combinatorial problems, though conceptually easy
134to model as integer programs, have long remained challenging to solve in
135practice. The last two decades have seen tremendous progress in our ability to
136solve large-scale discrete optimization problems. These advances have
137culminated in the approach that we now call {\it branch and cut}, a technique
138(see \cite{Grotschel84cut,padb:branc,hoff:LP}) which brings the computational
139tools of branch and bound algorithms together with the theoretical tools of
140polyhedral combinatorics. Indeed, in 1998, Applegate, Bixby, Chv\'atal, and
141Cook used this technique to solve a {\em Traveling Salesman Problem} instance
142with 13,509 cities, a full order of magnitude larger than what had been
143possible just a decade earlier \cite{concorde} and two orders of magnitude
144larger than the largest problem that had been solved up until 1978. This feat
145becomes even more impressive when one realizes that the number of variables in
146the standard formulation for this problem is approximately the {\em square} of
147the number of cities. Hence, we are talking about solving a problem with
148roughly {\em 100 million variables}.
149
150There are several reasons for this impressive progress. Perhaps the most
151important is the dramatic increase in available computing power over the last
152decade, both in terms of processor speed and memory. This increase in the
153power of hardware has subsequently facilitated the development of increasingly
154sophisticated software for optimization, built on a wealth of theoretical
155results. As software development has become a central theme of optimization
156research efforts, many theoretical results have been re-discovered'' in
157light of their new-found computational importance. Finally, the use of
158parallel computing has allowed researchers to further leverage their gains.
159
160Because of the rapidly increasing sophistication of computational techniques,
161one of the main difficulties faced by researchers who wish to apply these
162techniques is the level of effort required to develop an efficient
163implementation. The inherent need for incorporating problem-dependent methods
164(most notably for dynamic generation of variables and cutting planes) has
165typically required the time-consuming development of custom implementations.
166Around 1993, this led to the development by two independent research groups of
167software libraries aimed at providing a generic framework that users could
168easily customize for use in a particular problem setting. One of these groups,
169headed by J\"unger and Thienel, eventually produced ABACUS (A Branch And CUt
170System) \cite{abacus1}, while the other, headed by the authors, produced what
171was then known as COMPSys (Combinatorial Optimization Multi-processing
172System). After several revisions to enable more broad functionality, COMPSys
173became SYMPHONY (Single- or Multi-Process Optimization over Networks). A
174version of SYMPHONY written in C++, which we call COIN/BCP has also been
175produced at IBM under the COIN-OR project \cite{coin-or}. The COIN/BCP package
176takes substantially the same approach and has the same functionality as
177SYMPHONY, but has extended SYMPHONY's capabilities in some areas.
178
179\section{Related Work}
180\label{related}
181
182The 1990's witnessed a broad development of software for discrete
183optimization. Almost without exception, these new software packages were based
184on the techniques of branch, cut, and price. The packages fell into two main
185categories---those based on general-purpose algorithms for solving
186mixed-integer linear programs (MILPs) (without the use of special structure)
187and those facilitating the use of special structure by interfacing with
188user-supplied, problem-specific subroutines. We will call packages in this
189second category {\em frameworks}. There have also been numerous
190special-purpose codes developed for use in particular problem settings.
191
192Of the two categories, MILP solvers are the most common. Among the dozens of
193offerings in this category are MINTO \cite{MINTO}, MIPO \cite{MIPO}, bc-opt
194\cite{bc-opt}, and SIP \cite{SIP}. Generic frameworks, on the other hand, are
195far less numerous. The three frameworks we have already mentioned (SYMPHONY,
196ABACUS, and COIN/BCP) are the most full-featured packages available. Several
197others, such as MINTO, originated as MILP solvers but have the capability of
198utilizing problem-specific subroutines. CONCORDE \cite{concorde, concorde2}, a
199package for solving the {\em Traveling Salesman Problem} (TSP), also deserves
200mention as the most sophisticated special-purpose code developed to date.
201
202Other related software includes several frameworks for implementing parallel
203branch and bound. Frameworks for general parallel branch and bound include
204PUBB \cite{PUBB}, BoB \cite{BoB}, PPBB-Lib \cite{PPBB-Lib}, and PICO
205\cite{PICO}. PARINO \cite{PARINO} and FATCOP \cite{chen:fatcop2} are parallel
206MILP solvers.
207
208\section{How to Use This Manual}
209
210The manual is divided into six chapters. The first is the introduction, which
211you are reading now. Chapter \ref{getting_started} describes how to install
212SYMPHONY from either a source or binary distribution. If you have already
213managed to get SYMPHONY running using the instructions in the \code{README}
216Chapter \ref{API-overview} contains an overview of how to use in all three
217major modes---as a black-box solver through the interactive shell or on the
218command line, as a callable library, and as a customizable framework. Chapter
219\ref{SYMPHONY-design} contains further depth and a more complete technical
220description of the design and implementation of SYMPHONY. In Section
221\ref{design}, we describe the overall design of SYMPHONY without reference to
222the implementational details and with only passing reference to parallelism.
223In Section \ref{modules}, we discuss the details of the implementation. In
224Section \ref{parallelizing}, we briefly discuss issues involved in parallel
225execution of SYMPHONY. Chapter \ref{SYMPHONY-development} describes in detail
226how to develop a custom application using SYMPHONY. Note that it is not
227necessary to read Chapter \ref{SYMPHONY-design} before undertaking development
228of a SYMPHONY application, but it may help. Chapter \ref{SYMPHONY-reference}
229contains reference material. Section \ref{C_Interface} contains a description
230of the native C interface for the callable library. Section
231\ref{C++_Interface} contains a description of the interface for C++
232environments. Section \ref{API} contains a description of the user callback
233functions. SYMPHONY's parameters are described in Section \ref{params}. For
234reference use, the HTML version of this manual may be more practical, as the
235embedded hyperlinks make it easier to navigate.
236
238\label{resources}
239
240The main point of entry for additional help, trouble-shooting, and
241problem-solving is the SYMPHONY Wiki and development Web site at
242\begin{center}
243\url{https://projects.coin-or.org/SYMPHONY}
244\end{center}
245There, bug reports can be submitted by clicking on the New Ticket'' button
246and also previous bug reports searched. For general questions, there is also a
247\BB\ user's mailing list. To subscribe, visit
248\begin{center}
249\url{http://list.coin-or.org/mailman/listinfo/coin-symphony}
250\end{center}
251
252
Note: See TracBrowser for help on using the repository browser.