1%%% Local Variables: 2%%% mode: latex 3%%% TeX-master: "Bonmin_UsersManual" 4%%% End: 5 6\html{ 7 8\begin{PageSummary} 9\PageName{Introduction} 10\PageSection{Types of problems solved}{MathBack} 11\PageSection{Algorithms}{Algos} 12\PageSection{Required third party code}{ThirdP} 13\PageSection{Supported platforms}{Support} 14\end{PageSummary} 15 16 17\begin{quickref} 18\quickcitation{An algorithmic framework for convex MINLP. Bonami et.al.}{\BetalLink} 19\quickcitation{Algorithms and Software for Convex Mixed Integer Nonlinear Programs. Bonami, Kilinc, Linderoth}{\HotMINLPLink} 20\quickcitation{An outer-approximation algorithm for a class of MINLP. M. Duran and I.E. Grossmann. Mathematical Programming}{\DGLink} 21\quickcitation{Branch and bound experiments in convex nonlinear integer programming. O.K. Gupta and V. Ravindran.}{\GuptaLink} 22\quickcitation{Solving MINLP by outer approximation. 23 R. Fletcher and S. Leyffer. Mathematical Programming.}{\FLLink} 24\quickcitation{An LP/NLP based branched and bound algorithm for convex MINLP optimization problems. I. Quesada and I.E. Grossmann. 25 Computers and Chemical Engineering.}{\QGLink}\end{quickref} 26} 27 28\PageTitle{\latexhtml{Introduction}{\Bonmin}}{sec:Intro} 29\Bonmin\ (Basic Open-source Nonlinear Mixed INteger programming) 30is an open-source code for solving general MINLP (Mixed 31Integer NonLinear Programming) problems. 32 It is distributed on 33\COINOR\ 34\latexhtml{{(\tt www.coin-or.org)}}{} 35under the EPL (Eclipse Public 36License). The EPL is a license approved by the 37\footlink{http://www.opensource.org}{OSI}, 38(Open Source Initiative), 39 thus \Bonmin\ is OSI 40Certified Open Source Software. 41 42There are several algorithmic choices that can be selected with \Bonmin. 43{\tt B-BB} is a NLP-based branch-and-bound algorithm, 44{\tt B-OA} is an 45outer-ap\-prox\-i\-ma\-tion decomposition algorithm, {\tt B-iFP} is an iterated 46feasibility pump algorithm, {\tt B-QG} is an 47implementation of Quesada and Grossmann's branch-and-cut algorithm, 48{\tt B-Hyb} is a hybrid outer-ap\-prox\-i\-ma\-tion based 49branch-and-cut algorithm and {\tt B-Ecp} is a variant of {\tt B-QG} based 50on adding additional ECP cuts. 51 52 53Some of the algorithmic choices require the ability to solve MILP 54(Mixed Integer Linear Programming) problems and NLP (NonLinear 55Programming) problems. The default solvers for these are, 56respectively, the COIN-OR codes \Cbc\ and \Ipopt. In turn, 57{\tt Cbc} uses further COIN-OR modules: \Clp\ (for LP (Linear 58Programming) problems), \Cgl\ (for generating MILP cutting 59planes), as well as various other utilities. It is also possible to 60step outside the open-source realm and use 61\Cplex\ as the MILP solver and FilterSQP as the NLP solver. 62 63Additional documentation can be found on the {\tt Bonmin} 64\latex{homepage at 65$$ 66 \hbox{\url{http://www.coin-or.org/Bonmin}} 67$$ 68 and wiki at 69$$ 70 \hbox{\url{https://projects.coin-or.org/Bonmin}} 71$$ 72} 73 74\html{ 75\href{http://www.coin-or.org/Bonmin}{homepage} 76and \href{https://projects.coin-or.org/Bonmin}{wiki}.} 77 78\subsectionHs{Types of problems solved}{MathBack} 79\Bonmin\ solves MINLPs of the form 80 81%\left\{ 82\begin{align*} 83%\begin{array}{l} 84&\min f(x) \\ 85& {\rm s.t.} \\ 86&g^L \leq g(x) \leq g^U,\\ 87& x^L \leq x \leq x^U, \\ 88&x \in \mathbb{R}^n, \; x_i \in \mathbb{Z} \; \forall i \in I, 89%\end{array} 90\end{align*} 91%\right. 92where the functions $f :~\{x\in \mathbb{R}^n : x^L \leq x \leq x^U 93\}~ \rightarrow~\mathbb{R}$ and $g:~\{x\in \mathbb{R}^n : x^L \leq x 94\leq x^U \}~\rightarrow~\mathbb{R}^m$ are assumed to be twice 95continuously differentiable, and $I \subseteq \{1, \ldots,n \}$. We 96emphasize that \Bonmin\ treats problems that are cast 97in {\em minimization} form. 98 99The different methods that \Bonmin\ implements are exact algorithms when the functions $f$ and $g$ are 100convex but are only heuristics when this is not the case (i.e., \Bonmin\ is not a \emph{global} optimizer). 101 102\subsectionHs{Algorithms}{Algos} 103\Bonmin\ implements six different algorithms for solving 104MINLPs: 105 106\begin{itemize} 107\item {\tt B-BB}: a simple branch-and-bound algorithm based on solving 108a continuous nonlinear program at each node of the search tree and 109branching on variables \mycite{Gupta80Nonlinear}{Gupta 1980}; 110we also allow the possibility of SOS (Type 1) branching 111\item {\tt B-OA}: an outer-approximation based decomposition algorithm 112\latexhtml{\cite{DG,FL}} 113{[\href{\DGLink}{Duran Grossmann 1986},\href{\FLLink}{Fletcher Leyffer 1994}]} 114\item {\tt B-QG}: an outer-approximation based branch-and-cut 115algorithm 116\citeH{QG}{\QGLink}{Quesada Grossmann 1994} 117\item {\tt B-Hyb}: a hybrid outer-approximation / nonlinear programming 118based branch-and-cut algorithm \citeH{Betal} 119{\BetalLink}{Bonami et al. 2008} 120\item {\tt B-Ecp}: another outer-approximation based branch-and-cut inspired 121by the settings described in \citeH{abhishek.leyffer.linderoth:06}{\AbhishekLink}{Abhishek Leyffer Linderoth 2006} 122\item {\tt B-iFP}: an iterated feasibility pump algorithm \citeH{bonami.etal:06}{\FPLink}{Bonami Cornu\eacute jols Lodi Margot 2009}. 123\end{itemize} 124 125In this manual, we will not go into a further description of these algorithms. 126Mathematical details of these algorithms 127and some details of their implementations can be found in \citeH{Betal}{\BetalLink}{Bonami et al. 2008} and \citeH{hot:2009}{\HotMINLPLink}{Bonami K\i ln\i c Linderoth 2009}. 128 129Whether or not you are interested in the details of the algorithms, you certainly 130want to know which one of these six algorithms you should choose to solve 131your particular problem. 132For convex MINLPs, experiments we have made on a reasonably large test set of problems point in favor of using {\tt B-Hyb} 133(it solved the most of the problems in our test set in 3 hours of computing time). 134Nevertheless, there are cases where {\tt B-OA} is much faster than {\tt B-Hyb} and others where {\tt B-BB} is interesting. 135{\tt B-QG} and {\tt B-ECP} correspond mainly to a specific parameter setting of {\tt B-Hyb} but they can be faster in some case. {\tt B-iFP} is more tailored at finding quickly good solutions to very hard convex MINLP. 136For nonconvex MINLPs, we strongly recommend using {\tt B-BB} (the outer-approximation algorithms 137have not been tailored to treat nonconvex problems at this point). Although even {\tt B-BB} is only a 138heuristic for such problems, we have added several 139options to try and improve the quality of the solutions it provides (see \latexhtml{Section \ref{sec:non_convex}}{\href{\OptSetPage \#sec:non_convex}{non convex options}}). 140Because it is applicable to more classes problem {\tt B-BB} is the default algorithm in \Bonmin. 141 142\subsectionHs{Required third party code}{ThirdP} 143In order to run {\Bonmin}, you have to download other external 144libraries (and pay attention to their licenses!): 145\begin{itemize} 146\item \href{\LapackAddr}{Lapack} (Linear Algebra 147PACKage) 148\item \href{\BlasAddr}{Blas} (Basic Linear Algebra 149Subroutines) 150\item a sparse linear solver that is supported by Ipopt, e.g., MA27 from the 151\href{\AslAddr}{HSL} 152(Harwell Subroutine Library), MUMPS, or Pardiso. 153\end{itemize} 154 155Note that Lapack and the Blas are free for commercial use from the 156\footlink{http://www.netlib.org}{Netlib Repository}, but they are 157not OSI Certified Open Source Software. The linear solver MA27 is 158freely available for noncommercial use. 159 160The above software is sufficient to run \Bonmin\ as a 161stand-alone C++ code, but it does not provide a modeling language. 162For functionality from a modeling language, \Bonmin\ can be 163invoked from \footlink{http://www.ampl.com}{\tt AMPL} (no extra installation is required provided 164that you have a licensed copy of {\tt AMPL} installed), though you 165need the {\tt ASL} (AMPL Solver Library) which is obtainable from the Netlib. 166 167\Bonmin\ can use FilterSQP \citeH{FiLter}{\FilterLink}{FletcherLeyffer1998} as an alternative to \Ipopt\ for solving NLPs. 168 169Also, in the outer approximation methods {\tt B-OA} and {\tt B-iFP}, some MILP problems are 170solved. By default \Bonmin\ uses \Cbc\ to solve them, but it can also be set up to use 171the commercial solver \footlink{http://www.cplex.com}{\Cplex}. 172 173%\subsectionHs{Tested platforms}{Support} 174%\Bonmin\ has been installed on the following systems: 175%\begin{itemize} 176%\item Linux using g++ version 3.* and 4.* until 4.6 and Intel 9.* and 10.* 177%\item Windows using version Cygwin 1.5.18 178%\item Mac OS X using gcc 3.* and 4.* until 4.3 and Intel 9.* and 10.* 179%\item SunOS 5 using gcc 4.3 180%\end{itemize} 181 182