BONMIN Users' Manual

Introduction | Download | Install | Use | Setting Options | Options List | Bibliography |

• Bonmin
• Wiki
• NEOS
• IBM-CMU OCR
• IBM MINLP



• COIN-OR Home
• Projects
• FAQs
• Download
• Mailing Lists
• Get Involved
• Related Resources
• 
  
  COIN-OR Foundation
• Events
• Members

Introduction

Types of problems solved / Algorithms / Required third party code / Supported platforms /

References

1 An algorithmic framework for convex MINLP. Bonami et.al.

2 An outer-approximation algorithm for a class of MINLP. M. Duran and I.E. Grossmann. Mathematical Programming

3 Branch and bound experiments in convex nonlinear integer programming. O.K. Gupta and V. Ravindran.

4 Solving MINLP by outer approximation. R. Fletcher and S. Leyffer. Mathematical Programming.

5 An LP/NLP based branched and bound algorithm for convex MINLP optimization problems. I. Quesada and I.E. Grossmann. Computers and Chemical Engineering.

BONMIN

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 COIN-OR under the CPL (Common Public License). The CPL is a license approved by the OSI, (Open Source Initiative), thus BONMIN is OSI Certified Open Source Software.

There are several algorithmic choices that can be selected with BONMIN. B-BB is a NLP-based branch-and-bound algorithm, B-OA is an outer-approximation decomposition algorithm, B-QG is an implementation of Quesada and Grossmann's branch-and-cut algorithm, and B-Hyb is a hybrid outer-approximation 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, 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 Bonmin wiki.

Types of problems solved

BONMIN solves MINLPs of the form

$$\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,$$

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 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 global optimizer).

Algorithms

BONMIN implements four different algorithms for solving MINLPs:

• 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 [Gupta80]; we also allow the possibility of SOS (Type 1) branching
• B-OA: an outer-approximation based decomposition algorithm [Duran1986,Leyffer1994]
• B-QG: an outer-approximation based branch-and-bound algorithm [Quesada1994]

• B-Hyb: a hybrid outer-approximation/nonlinear programming based branch-and-cut algorithm [Bonami2006]

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 [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 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 B-OA is much faster than B-Hyb and others where B-BB is interesting. B-QG corresponds mainly to a specific parameter setting of B-Hyb where some features are disabled. For nonconvex MINLPs, we strongly recommend using B-BB (the outer-approximation algorithms have not been tailored to treat nonconvex problems at this point). Although even 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 non convex options).

Required third party code

In order to run BONMIN, you have to download other external libraries (and pay attention to their licenses!):

• Lapack (Linear Algebra PACKage)
• Blas (Basic Linear Algebra Subroutines)
• the sparse linear solver MA27 from the HSL (Harwell Subroutine Library)

Note that Lapack and the Blas are free for commercial use from the 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 Ampl (no extra installation is required provided that you have a licensed copy of Ampl installed), though you need the ASL (Ampl Solver Library) which is obtainable from the Netlib.

Also, in the outer approximation decomposition method 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 Cplex.

Tested platforms

BONMIN has been installed on the following systems:

• Linux using g++ version 3.* and 4.*
• Windows using version Cygwin 1.5.18
• Mac OS X using gcc 3.* and 4.*

About Us | Contact Us | ©2006 Carnegie Mellon University, IBM