Scope
Global solver for nonconvex problems.
Availability
BMIBNB is shipped with YALMIP.
YALMIP
BMIBNB is invoked with sdpsettings('solver','bmibnb').
Available options
sdpsettings('bmibnb.roottight',[0|1]) |
Improve variable bounds at root-node by performing bound strengthening based on the full relaxed model (Can be very expensive, but lead to improved branching) |
sdpsettings('bmibnb.lpreduce',[0|1]) |
Improve variable bounds in all nodes by performing bound strengthening using only the scalar constraints (including scalar cut constraints) in the model (Can be very expensive, but lead to improved branching, in particular for semidefinite problems) |
sdpsettings('bmibnb.lowersolver', solvertag) |
Solver for relaxed problems. |
sdpsettings('bmibnb.uppersolver', solvertag) |
Local solver for computing upper bounds. |
sdpsettings('bmibnb.lpsolver', solvertag) |
LP solver for bound strengthening
(only used if bmibnb.lpreduce is set to 1) |
sdpsettings('bmibnb.numglobal', [int]) |
A major computational burden along the branching process is to
solver the upper bound problems using a local nonlinear solver. By
setting this value to a finite value, the local solver will no
longer be used when the upper bound has been improved numglobal times.
This option is useful if you believe your local solver quickly gives
globally optimal solutions. It can also be useful if you have a
feasible solution and just want to compute a gap. In this case, use
the usex0 option and set numglobal to 0. |
Comments
BMIBNB is an implementation of a standard branch & bound algorithm for nonconvex problems, based on linear programming relaxations and convex envelope approximations.
Polynomial problems are automatically converted to bilinear problems, but note that this easily leads to very large problems.
The solver relies on external linear and quadratic programming solvers for solving the lower bounding relaxation problems, and nonlinear solvers for the upper bound computations (currently only PENBMI, SNOPT and fmincon).
Do not expect too much. Global solutions are extremely hard to compute, and this is a fairly simple implementation. Problems with more than 10 variables is often beyond the capabilities of this solver, although you might be lucky.