source: html/Intro.html @ 1590

Last change on this file since 1590 was 1590, checked in by pbonami, 9 years ago

some accents

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