%%% Local Variables:
%%% mode: latex
%%% TeX-master: "Bonmin_UsersManual"
%%% End:

\begin{htmlonly}

\begin{PageSummary}
\PageName{Introduction}
\PageSection{Types of problems solved}{MathBack}
\PageSection{Algorithms}{Algos}
\PageSection{Required third party code}{ThirdP}
\PageSection{Supported platforms}{Support}
\end{PageSummary}


\begin{quickref}
\quickcitation{An algorithmic framework for convex MINLP. Bonami et.al.}{\BetalLink}
\quickcitation{An outer-approximation algorithm for a class of MINLP. M. Duran and I.E. Grossmann. Mathematical Programming}{\DGLink}
\quickcitation{Branch and bound experiments in convex nonlinear integer programming. O.K. Gupta and V. Ravindran.}{\GuptaLink}
\quickcitation{Solving MINLP by outer approximation.
  R. Fletcher and S. Leyffer. Mathematical Programming.}{\FLLink}
\quickcitation{An LP/NLP based branched and bound algorithm for convex MINLP optimization problems. I. Quesada and I.E. Grossmann.
   Computers and Chemical Engineering.}{\QGLink}\end{quickref}
\end{htmlonly}
\PageTitle{\latexhtml{Introduction}{\Bonmin}}{sec:Intro}
\Bonmin\ (Basic Open-source Nonlinear Mixed INteger programming)
is an open-source code for solving general MINLP (Mixed
Integer NonLinear Programming) problems.
 It is distributed on
\COINOR
\latexhtml{\begin{latexonly} (\tt www.coin-or.org) \end{latexonly}}{}
under the CPL (Common Public
License). The CPL is a license approved by the
\footlink{http://www.opensource.org}{OSI},
(Open Source Initiative),
 thus \Bonmin\ is OSI
Certified Open Source Software.

There are several algorithmic choices that can be selected with \Bonmin.
{\tt B-BB} is a NLP-based branch-and-bound algorithm,
{\tt B-OA} is an
outer-ap\-prox\-i\-ma\-tion decomposition algorithm, {\tt B-QG} is an
implementation of  Quesada and Grossmann's branch-and-cut algorithm,
and {\tt B-Hyb} is a hybrid outer-ap\-prox\-i\-ma\-tion based
branch-and-cut algorithm.


Some of the algorithmic choices require the ability to solve MILP
(Mixed Integer Linear Programming) problems and NLP (NonLinear
Programming) problems. The default solvers for these are,
respectively, the COIN-OR codes \Cbc\ and \Ipopt. In turn,
{\tt Cbc} uses further COIN-OR modules: \Clp\ (for LP (Linear
Programming) problems), \Cgl\ (for generating MILP cutting
planes), as well as various other utilities. It is also possible to
step outside the open-source realm and use
\Cplex\ as the MILP solver. We expect to make an interface to other NLP solvers as well.

Additional documentation is availble on the {\tt Bonmin}
\begin{latexonly} wiki at 
\begin{verbatim}
         https://projects.coin-or.org/Bonmin
\end{verbatim}
\end{latexonly}
\begin{htmlonly} \link{https://projects.coin-or.org/Bonmin}{wiki}. \end{htmlonly}
\subsectionHs{Types of problems solved}{MathBack}
\Bonmin\ solves MINLPs of the form

%\left\{
\begin{align*}
%\begin{array}{l}
&\min f(x) \\
& {\rm s.t.} \\
&g^L \leq g(x) \leq g^U,\\
& x^L \leq x \leq x^U, \\
&x \in \mathbb{R}^n, \;  x_i \in \mathbb{Z} \; \forall i \in I,
%\end{array}
\end{align*}
%\right.
where the functions $f :~\{x\in \mathbb{R}^n : x^L \leq x \leq x^U
\}~ \rightarrow~\mathbb{R}$ and $g:~\{x\in \mathbb{R}^n : x^L \leq x
\leq x^U \}~\rightarrow~\mathbb{R}^m$ are assumed to be twice
continuously differentiable, and $I \subseteq \{1, \ldots,n \}$. We
emphasize that \Bonmin\ treats problems that are cast
in {\em minimization} form.

The different methods that \Bonmin\ implements are exact algorithms when the functions $f$ and $g$ are
convex but are only heuristics when this is not the case (i.e., \Bonmin\ is not a \emph{global} optimizer).\\

\subsectionHs{Algorithms}{Algos}
\Bonmin\ implements four different algorithms for solving
MINLPs:

\begin{itemize}
\item {\tt B-BB}: a simple branch-and-bound algorithm based on solving
a continuous nonlinear program at each node of the search tree and
branching on variables \mycite{Gupta80Nonlinear}{Gupta80};
we also allow the possibility of SOS (Type 1) branching
\item {\tt B-OA}: an outer-approximation based decomposition algorithm
\latexhtml{\begin{latexonly} \cite{DG,FL} \end{latexonly}}
{[\link{\DGLink}{Duran1986},\link{\FLLink}{Leyffer1994}]}
\item {\tt B-QG}: an outer-approximation based branch-and-bound
algorithm
\citeH{QG}{\QGLink}{Quesada1994}
\item {\tt B-Hyb}: a hybrid outer-approximation/nonlinear programming
based branch-and-cut algorithm \citeH{Betal}
{\BetalLink}{Bonami2006}
\end{itemize}

In this manual,  we will not go into a further description of these algorithms.
Mathematical details of these algorithms 
and some details of their implementations can be found in\citeH{Betal}{\BetalLink}{Bonami2006}.

Whether or not you are interested in the details of the algorithms, you certainly
want to know which one of these four algorithms you should choose to solve
your particular problem.
For convex MINLPs, experiments we have made on a reasonably large test set of problems point in favor of using {\tt B-Hyb}
(it solved the most of the problems in our test set in 3 hours of computing time).
Therefore, it is the default algorithm in \Bonmin.
Nevertheless, there are cases where {\tt B-OA} is much faster than {\tt B-Hyb} and others where {\tt B-BB} is interesting.
{\tt B-QG} corresponds mainly to a specific parameter setting of {\tt B-Hyb} where some features are disabled.
For nonconvex MINLPs, we strongly recommend using {\tt B-BB} (the outer-approximation algorithms
have not been tailored to treat nonconvex problems at this point). Although even {\tt B-BB} is only a
heuristic for such problems, we have added several
options to try and improve the quality of the solutions it provides (see \latexhtml{Section \ref{sec:non_convex}}{\link{\OptSetPage #sec:non_convex}{non convex options}}).

\subsectionHs{Required third party code}{ThirdP}
In order to run {\Bonmin}, you have to download other external
libraries (and pay attention to their licenses!):
\begin{itemize}
\item \link{\LapackAddr}{Lapack} (Linear Algebra
PACKage)
\item \link{\BlasAddr}{Blas} (Basic Linear Algebra
Subroutines)
\item a sparse linear solver that is supported by Ipopt, e.g., MA27 from the
\link{\AslAddr}{HSL}
(Harwell Subroutine Library), MUMPS, or Pardiso
\end{itemize}

Note that Lapack and the Blas are free for commercial use from the
\footlink{http://www.netlib.org}{Netlib Repository}, but they are
not OSI Certified Open Source Software. The linear solver MA27 is
freely available for noncommercial use.

The above software is sufficient to run \Bonmin\ as a
stand-alone C++ code, but it does not provide a modeling language.
For functionality from a modeling language, \Bonmin\ can be
invoked from \footlink{http://www.ampl.com}{\tt Ampl} (no extra installation is required provided
that you have a licensed copy of {\tt Ampl} installed), though you
need the {\tt ASL} (Ampl Solver Library) which is obtainable from the Netlib.

\Bonmin\ can use FilterSQP \citeH{FilTer}{\FilterLink}{FletcherLeyffer1998} as an alternative to \Ipopt\ for solving NLPs.

Also, in the outer approximation decomposition method {\tt B-OA}, some MILP problems are
solved. By default \Bonmin\ uses  \Cbc\ to solve them, but it can also be set up to use
the commercial solver \footlink{http://www.ilog.com/products/cplex/product/mip.cfm}{\Cplex}.

\subsectionHs{Tested platforms}{Support}
\Bonmin\ has been installed on the following systems:
\begin{itemize}
\item Linux using g++ version 3.* and 4.* and Intel 9.* and 10.*
\item Windows using version Cygwin 1.5.18
\item Mac OS X using gcc 3.* and 4.* and Intel 9.* and 10.*
\item SunOS 5 using gcc 4.3
\end{itemize}

\latexhtml{}{
\begin{rawhtml}
</div>
</div>
<!--end content -->
<div id="siteInfo">
  <img src="" width="44" height="22"> <a href="#">About Us</a> | <a href="#">Contact Us</a> | &copy;2006
  Carnegie Mellon University, IBM</div>
<br>
\end{rawhtml}
}
