source: html/Intro.html @ 1586

Last change on this file since 1586 was 1586, checked in by pbonami, 10 years ago

Two typos in links

File size: 18.5 KB
Line 
1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" 
2  "http://www.w3.org/TR/html4/loose.dtd"> 
3<html > 
4<head><title></title> 
5<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> 
6<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)"> 
7<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)"> 
8<!-- html --> 
9<meta name="src" content="tmp.tex"> 
10<meta name="date" content="2010-01-23 16:47:00"> 
11<link rel="stylesheet" type="text/css" href="bonmin.css"> 
12</head><body 
13>
14<!--l. 8--><p class="noindent" ><div id="header">   <h1 id="siteName"><TT> <big> BONMIN </big> </tt> Users' Manual</h1>   <div id="globalNav">   <a href="Intro.html">Introduction</a> |   <a href="Obtain.html">Download</a> |  <a href="Install.html">Install</a> |   <a href="use.html">Use</a> |   <a href="options_set.html">Setting Options</a> |   <a href="options_list.html">Options List</a> |   <a href="bib.html">Bibliography</a> |  </div>   </div>  <div id="leftPanel"> <div id="side-bar">  <ul> <li class="main"><a href="/Bonmin/index.html">Bonmin</a></li>  <li><a href="https://projects.coin-or.org/Bonmin">Wiki</a></li>   <li><a href="http://neos.mcs.anl.gov/neos/solvers/minco:Bonmin/AMPL.html"> NEOS </a> </li>  <li><a href="http://egon.cheme.cmu.edu/ibm/page.htm">IBM-CMU OCR </a></li>  <li><a href="http://domino.research.ibm.com/comm/research_projects.nsf/pages/minlp.index.html">  IBM MINLP </a></li>  <br>  <br>  <li class="main"><a href="/index.html">COIN-OR Home</a></li>  <li><a href="/projects.html">Projects</a></li>  <li><a href="/faqs.html">FAQs</a></li>   <li><a href="/download.html">Download</a></li>  <li><a href="/mail.html">Mailing Lists</a></li>  <li><a href="/how-to-help.html">Get Involved</a></li>  <li><a href="/resources.html">Related Resources</a></li>  <li class="main"><a href="/foundation.html">  <br>  <br>  COIN-OR Foundation  </a></li>   <li><a href="/events.html">Events</a></li>  <li><a href="/members.html">Members</a></li>  </ul>  </div> </div> <!--end navBar div -->  <br>   <h2 id="pageName"> Introduction  </h2>  <a href="#MathBack " > Types of problems
15solved  </a> / <a href="#Algos " > Algorithms  </a> / <a href="#ThirdP " > Required third party code  </a> / <a href="#Support " >
16Supported platforms  </a> /   </div> 
17<!--l. 17--><p class="noindent" > <div id="rightPanel"> <div id="headlines"> <h4>References </h4>    <div id="refer"> <p>  1 <a 
18href="http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/fdb4630e33bd2876852570b20062af37?OpenDocument" >An algorithmic framework for convex MINLP. Bonami et.al.</a>  </p> </div>       <div id="refer"> <p>  2 <a 
19href="http://hal.archives-ouvertes.fr/hal-00423416/en/" >Algorithms
20and Software for Convex Mixed Integer Nonlinear Programs. Bonami, Kilinc,
21Linderoth</a>  </p> </div>       <div id="refer"> <p>  3 <a 
22href="../bib/index.html#DG" >An outer-approximation algorithm for a class of MINLP.
23M. Duran and I.E. Grossmann. Mathematical Programming</a>  </p> </div>       <div id="refer"> <p>  4 <a 
24href="../bib/index.html#Gupta80Nonlinear" >Branch
25and bound experiments in convex nonlinear integer programming. O.K.
26Gupta and V. Ravindran.</a>  </p> </div>       <div id="refer"> <p>  5 <a 
27href="http://dx.doi.org/10.1007/BF01581153" >Solving MINLP by outer approximation. R.
28Fletcher and S. Leyffer. Mathematical Programming.</a>  </p> </div>       <div id="refer"> <p>  6 <a 
29href="http://dx.doi.org/10.1016/0098-1354(92)80028-8" >An LP/NLP based
30branched and bound algorithm for convex MINLP optimization problems. I.
31Quesada and I.E. Grossmann. Computers and Chemical Engineering.</a>  </p> </div>    </div> </div> 
32<!--l. 28--><p class="noindent" > </div> <div id="content"> <div class="feature"> <h3> <span 
33class="cmtt-10">BONMIN </span></h3> <span 
34class="cmtt-10">BONMIN</span>&#x00A0;(Basic Open-source Nonlinear Mixed INteger programming) is
35an open-source code for solving general MINLP (Mixed Integer NonLinear
36Programming) problems. It is distributed on <a 
37href="http://www.coin-or.org" >COIN-OR</a> under the CPL (Common
38Public License). The CPL is a license approved by the <a 
39href="http://www.opensource.org" >OSI</a>, (Open Source Initiative),
40thus <span 
41class="cmtt-10">BONMIN</span>&#x00A0;is OSI Certified Open Source Software.
42<!--l. 42--><p class="indent" >   There are several algorithmic choices that can be selected with <span 
43class="cmtt-10">BONMIN</span>. <span 
44class="cmtt-10">B-BB </span>is a
45NLP-based branch-and-bound algorithm, <span 
46class="cmtt-10">B-OA </span>is an outer-approximation
47decomposition algorithm, <span 
48class="cmtt-10">B-iFP </span>is an iterated feasibility pump algorithm,
49<span 
50class="cmtt-10">B-QG </span>is an implementation of Quesada and Grossmann&#8217;s branch-and-cut
51algorithm, <span 
52class="cmtt-10">B-Hyb </span>is a hybrid outer-approximation based branch-and-cut
53algorithm and <span 
54class="cmtt-10">B-Ecp </span>is a variant of <span 
55class="cmtt-10">B-QG </span>based on adding additional ECP
56cuts.
57<!--l. 53--><p class="indent" >   Some of the algorithmic choices require the ability to solve MILP (Mixed Integer
58Linear Programming) problems and NLP (NonLinear Programming) problems. The
59default solvers for these are, respectively, the COIN-OR codes <a 
60href="https://projects.coin-or.org/Cbc" ><span 
61class="cmtt-10">Cbc</span></a>&#x00A0;and <a 
62href="https://projects.coin-or.org/Ipopt" ><span 
63class="cmtt-10">Ipopt</span></a>. In
64turn, <span 
65class="cmtt-10">Cbc </span>uses further COIN-OR modules: <a 
66href="https://projects.coin-or.org/Clp" ><span 
67class="cmtt-10">Clp</span></a>&#x00A0;(for LP (Linear Programming)
68problems), <a 
69href="https://projects.coin-or.org/Cgl" ><span 
70class="cmtt-10">Cgl</span></a>&#x00A0;(for generating MILP cutting planes), as well as various other
71utilities. It is also possible to step outside the open-source realm and use <a 
72href="http://www.ilog.com/products/cplex/product/mip.cfm" ><span 
73class="cmtt-10">Cplex</span></a>&#x00A0;as
74the MILP solver and FilterSQP as the NLP solver.
75<!--l. 63--><p class="indent" >   Additional documentation can be found on the <span 
76class="cmtt-10">Bonmin  </span><a 
77href="http://www.coin-or.org/Bonmin" >homepage</a> and <a 
78href="https://projects.coin-or.org/Bonmin" >wiki</a>.     </div> <div class="story"> <h3><a name= 
79&#8221;MathBack&#8221; ></a> Types of problems solved  </h3>   <span 
80class="cmtt-10">BONMIN</span>&#x00A0;solves MINLPs of the
81form
82<!--l. 79--><p class="indent" >
83
84<table 
85class="align-star">
86                        <tr><td 
87class="align-odd"></td>                        <td 
88class="align-even">min<span 
89class="cmmi-10">f</span>(<span 
90class="cmmi-10">x</span>)</td>                                   <td 
91class="align-label"></td>                        <td 
92class="align-label">
93                        </td></tr><tr><td 
94class="align-odd"></td>                        <td 
95class="align-even"><span 
96class="cmmi-10">s.t.</span></td>                                        <td 
97class="align-label"></td>                        <td 
98class="align-label">
99                        </td></tr><tr><td 
100class="align-odd"></td>                        <td 
101class="align-even"><span 
102class="cmmi-10">g</span><sup><span 
103class="cmmi-7">L</span></sup> <span 
104class="cmsy-10">&#x2264; </span><span 
105class="cmmi-10">g</span>(<span 
106class="cmmi-10">x</span>) <span 
107class="cmsy-10">&#x2264; </span><span 
108class="cmmi-10">g</span><sup><span 
109class="cmmi-7">U</span></sup><span 
110class="cmmi-10">,</span></td>                             <td 
111class="align-label"></td>                        <td 
112class="align-label">
113                        </td></tr><tr><td 
114class="align-odd"></td>                        <td 
115class="align-even"><span 
116class="cmmi-10">x</span><sup><span 
117class="cmmi-7">L</span></sup> <span 
118class="cmsy-10">&#x2264; </span><span 
119class="cmmi-10">x </span><span 
120class="cmsy-10">&#x2264; </span><span 
121class="cmmi-10">x</span><sup><span 
122class="cmmi-7">U</span></sup><span 
123class="cmmi-10">,</span></td>                               <td 
124class="align-label"></td>                        <td 
125class="align-label">
126                        </td></tr><tr><td 
127class="align-odd"></td>                        <td 
128class="align-even"><span 
129class="cmmi-10">x </span><span 
130class="cmsy-10"><img 
131src="cmsy10-32.png" alt="&#x2208;" class="10x-x-32" /> </span><span 
132class="msbm-10"><img 
133src="msbm10-52.png" alt="&#x211D;" class="10x-x-52" /></span><sup><span 
134class="cmmi-7">n</span></sup><span 
135class="cmmi-10">, x</span><sub>
136<span 
137class="cmmi-7">i</span></sub> <span 
138class="cmsy-10"><img 
139src="cmsy10-32.png" alt="&#x2208;" class="10x-x-32" /> </span><span 
140class="msbm-10">&#x2124; </span><span 
141class="cmsy-10">&#x2200;</span><span 
142class="cmmi-10">i </span><span 
143class="cmsy-10"><img 
144src="cmsy10-32.png" alt="&#x2208;" class="10x-x-32" /> </span><span 
145class="cmmi-10">I,</span></td>                        <td 
146class="align-label"></td>                        <td 
147class="align-label"></td></tr></table>
148where the functions <span 
149class="cmmi-10">f </span>: <span 
150class="cmmi-10">&#x00A0;</span><span 
151class="cmsy-10">{</span><span 
152class="cmmi-10">x </span><span 
153class="cmsy-10"><img 
154src="cmsy10-32.png" alt="&#x2208;" class="10x-x-32" /> </span><span 
155class="msbm-10"><img 
156src="msbm10-52.png" alt="&#x211D;" class="10x-x-52" /></span><sup><span 
157class="cmmi-7">n</span></sup> : <span 
158class="cmmi-10">x</span><sup><span 
159class="cmmi-7">L</span></sup> <span 
160class="cmsy-10">&#x2264; </span><span 
161class="cmmi-10">x </span><span 
162class="cmsy-10">&#x2264; </span><span 
163class="cmmi-10">x</span><sup><span 
164class="cmmi-7">U</span></sup><span 
165class="cmsy-10">}</span><span 
166class="cmmi-10">&#x00A0; </span><span 
167class="cmsy-10">&#x2192;</span> <span 
168class="cmmi-10">&#x00A0;</span><span 
169class="msbm-10"><img 
170src="msbm10-52.png" alt="&#x211D;" class="10x-x-52" /> </span>and
171<span 
172class="cmmi-10">g </span>: <span 
173class="cmmi-10">&#x00A0;</span><span 
174class="cmsy-10">{</span><span 
175class="cmmi-10">x </span><span 
176class="cmsy-10"><img 
177src="cmsy10-32.png" alt="&#x2208;" class="10x-x-32" /> </span><span 
178class="msbm-10"><img 
179src="msbm10-52.png" alt="&#x211D;" class="10x-x-52" /></span><sup><span 
180class="cmmi-7">n</span></sup> : <span 
181class="cmmi-10">x</span><sup><span 
182class="cmmi-7">L</span></sup> <span 
183class="cmsy-10">&#x2264; </span><span 
184class="cmmi-10">x </span><span 
185class="cmsy-10">&#x2264; </span><span 
186class="cmmi-10">x</span><sup><span 
187class="cmmi-7">U</span></sup><span 
188class="cmsy-10">}</span><span 
189class="cmmi-10">&#x00A0; </span><span 
190class="cmsy-10">&#x2192;</span> <span 
191class="cmmi-10">&#x00A0;</span><span 
192class="msbm-10"><img 
193src="msbm10-52.png" alt="&#x211D;" class="10x-x-52" /></span><sup><span 
194class="cmmi-7">m</span></sup> are assumed to be twice continuously
195differentiable, and <span 
196class="cmmi-10">I </span><span 
197class="cmsy-10">&#x2286;{</span>1<span 
198class="cmmi-10">,</span><span 
199class="cmmi-10">&#x2026;</span><span 
200class="cmmi-10">,n</span><span 
201class="cmsy-10">}</span>. We emphasize that <span 
202class="cmtt-10">BONMIN</span>&#x00A0;treats problems that are
203cast in <span 
204class="cmti-10">minimization </span>form.
205<!--l. 96--><p class="indent" >   The different methods that <span 
206class="cmtt-10">BONMIN</span>&#x00A0;implements are exact algorithms when the
207functions <span 
208class="cmmi-10">f </span>and <span 
209class="cmmi-10">g </span>are convex but are only heuristics when this is not the case (i.e.,
210<span 
211class="cmtt-10">BONMIN</span>&#x00A0;is not a <span 
212class="cmti-10">global </span>optimizer).
213<br class="newline" />
214<!--l. 99--><p class="indent" >    </div> <div class="story"> <h3><a name=  &#8221;Algos&#8221; ></a> Algorithms  </h3>   <span 
215class="cmtt-10">BONMIN</span>&#x00A0;implements six different algorithms for solving
216MINLPs:
217     <ul class="itemize1">
218     <li class="itemize"><span 
219class="cmtt-10">B-BB</span>: a simple branch-and-bound algorithm based on solving a continuous
220     nonlinear  program  at  each  node  of  the  search  tree  and  branching  on
221     variables  <a href=&#8221;bib.html#Gupta80Nonlinear&#8221; > [Gupta 1980]</a> ; we also allow the
222     possibility of SOS (Type 1) branching
223     </li>
224     <li class="itemize"><span 
225class="cmtt-10">B-OA</span>:  an  outer-approximation  based  decomposition  algorithm  [<a 
226href="../bib/index.html#DG" >Duran
227     Grossmann 1986</a>,<a 
228href="http://dx.doi.org/10.1007/BF01581153" >Fletcher Leyffer 1994</a>]
229     </li>
230     <li class="itemize"><span 
231class="cmtt-10">B-QG</span>: an outer-approximation based branch-and-cut algorithm  <a 
232href="http://dx.doi.org/10.1016/0098-1354(92)80028-8" >[Quesada
233     Grossmann 1994]</a>
234     </li>
235     <li class="itemize"><span 
236class="cmtt-10">B-Hyb</span>:  a  hybrid  outer-approximation/nonlinear  programming  based
237     branch-and-cut algorithm  <a 
238href="http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/fdb4630e33bd2876852570b20062af37?OpenDocument" >[Bonami et al. 2008]</a>
239     </li>
240     <li class="itemize"><span 
241class="cmtt-10">B-Ecp</span>: another outer-approximation based branch-and-cut inspired by the
242     settings described in  <a 
243href="http://wiki.mcs.anl.gov/leyffer/index.php/Sven_Leyffer's_Publications" >[Abhishek Leyffer Linderoth 2006]</a>
244
245     </li>
246     <li class="itemize"><span 
247class="cmtt-10">B-iFP</span>: an iterated feasibility pump algorithm  <a 
248href="http://dx.doi.org/10.1007/s10107-008-0212-2" >[Bonami Cornuéjols Lodi
249     Margot 2009]</a>  .</li></ul>
250<!--l. 122--><p class="indent" >   In this manual, we will not go into a further description of these algorithms.
251Mathematical details of these algorithms and some details of their implementations
252can be found in  <a 
253href="http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/fdb4630e33bd2876852570b20062af37?OpenDocument" >[Bonami et al. 2008]</a>   and  <a 
254href="http://hal.archives-ouvertes.fr/hal-00423416/en/" >[Bonami K<img 
255src="cmr10-10.png" alt="i" class="10x-x-10" />ln<img 
256src="cmr10-10.png" alt="i" class="10x-x-10" />c Linderoth 2009]</a>
257.
258<!--l. 126--><p class="indent" >   Whether or not you are interested in the details of the algorithms, you certainly
259want to know which one of these six algorithms you should choose to solve your
260particular problem. For convex MINLPs, experiments we have made on a reasonably
261large test set of problems point in favor of using <span 
262class="cmtt-10">B-Hyb </span>(it solved the most of the
263problems in our test set in 3 hours of computing time). Nevertheless, there are cases
264where <span 
265class="cmtt-10">B-OA </span>is much faster than <span 
266class="cmtt-10">B-Hyb </span>and others where <span 
267class="cmtt-10">B-BB </span>is interesting. <span 
268class="cmtt-10">B-QG </span>and
269<span 
270class="cmtt-10">B-ECP </span>correspond mainly to a specific parameter setting of <span 
271class="cmtt-10">B-Hyb </span>but they
272can be faster in some case. <span 
273class="cmtt-10">B-iFP </span>is more tailored at finding quickly good
274solutions to very hard convex MINLP. For nonconvex MINLPs, we strongly
275recommend using <span 
276class="cmtt-10">B-BB </span>(the outer-approximation algorithms have not been tailored
277to treat nonconvex problems at this point). Although even <span 
278class="cmtt-10">B-BB </span>is only
279a heuristic for such problems, we have added several options to try and
280improve the quality of the solutions it provides (see <a 
281href="../options_set/index.html#sec:non_convex" >non convex options</a>).
282Because it is appliable to more classes problem <span 
283class="cmtt-10">B-BB </span>is the default algorithm in
284<span 
285class="cmtt-10">BONMIN</span>.
286<!--l. 139--><p class="indent" >    </div> <div class="story"> <h3><a name=  &#8221;ThirdP&#8221; ></a> Required third party code  </h3>   In order to run <span 
287class="cmtt-10">BONMIN</span>, you have to
288download other external libraries (and pay attention to their licenses!):
289     <ul class="itemize1">
290     <li class="itemize"><a 
291href="http://www.netlib.org/lapack/" >Lapack</a> (Linear Algebra PACKage)
292     </li>
293     <li class="itemize"><a 
294href="http://www.netlib.org/blas/" >Blas</a> (Basic Linear Algebra Subroutines)
295     </li>
296     <li class="itemize">a sparse linear solver that is supported by Ipopt, e.g., MA27 from the <a 
297href="http://www.cse.clrc.ac.uk/nag/hsl/contents.shtml" >HSL</a>
298     (Harwell Subroutine Library), MUMPS, or Pardiso.</li></ul>
299<!--l. 152--><p class="indent" >   Note that Lapack and the Blas are free for commercial use from the <a 
300href="http://www.netlib.org" >Netlib
301Repository</a>, but they are not OSI Certified Open Source Software. The linear solver
302MA27 is freely available for noncommercial use.
303<!--l. 157--><p class="indent" >   The above software is sufficient to run <span 
304class="cmtt-10">BONMIN</span>&#x00A0;as a stand-alone C++ code, but it
305does not provide a modeling language. For functionality from a modeling language,
306<span 
307class="cmtt-10">BONMIN</span>&#x00A0;can be invoked from <a 
308href="http://www.ampl.com" ><span 
309class="cmtt-10">Ampl</span></a> (no extra installation is required provided that you
310have a licensed copy of <span 
311class="cmtt-10">Ampl </span>installed), though you need the <span 
312class="cmtt-10">ASL </span>(Ampl Solver
313Library) which is obtainable from the Netlib.
314<!--l. 164--><p class="indent" >   <span 
315class="cmtt-10">BONMIN</span>&#x00A0;can use FilterSQP  <a 
316href="http://www.mcs.anl.gov/~leyffer/solvers.html" >[FletcherLeyffer1998]</a>   as an alternative to <a 
317href="https://projects.coin-or.org/Ipopt" ><span 
318class="cmtt-10">Ipopt</span></a>&#x00A0;for
319solving NLPs.
320<!--l. 166--><p class="indent" >   Also, in the outer approximation methods <span 
321class="cmtt-10">B-OA </span>and <span 
322class="cmtt-10">B-iFP</span>, some MILP problems
323
324are solved. By default <span 
325class="cmtt-10">BONMIN</span>&#x00A0;uses <a 
326href="https://projects.coin-or.org/Cbc" ><span 
327class="cmtt-10">Cbc</span></a>&#x00A0;to solve them, but it can also be set up to
328use the commercial solver <a 
329href="http://www.ilog.com/products/cplex/product/mip.cfm" ><a 
330href="http://www.ilog.com/products/cplex/product/mip.cfm" ><span 
331class="cmtt-10">Cplex</span></a></a>.
332<!--l. 170--><p class="indent" >    </div> <div class="story"> <h3><a name=  &#8221;Support&#8221; ></a> Tested platforms  </h3>   <span 
333class="cmtt-10">BONMIN</span>&#x00A0;has been installed on the following
334systems:
335     <ul class="itemize1">
336     <li class="itemize">Linux using g++ version 3.* and 4.* until 4.3 and Intel 9.* and 10.*
337     </li>
338     <li class="itemize">Windows using version Cygwin 1.5.18
339     </li>
340     <li class="itemize">Mac OS X using gcc 3.* and 4.* until 4.3 and Intel 9.* and 10.*
341     </li>
342     <li class="itemize">SunOS 5 using gcc 4.3</li></ul>
343   
344</body></html> 
345
346
347
Note: See TracBrowser for help on using the repository browser.