Bonmin: Convex MINLP Solver

Bonmin (Basic Open-source Nonlinear Mixed INteger programming) solves convex mixed-integer nonlinear programs. It implements multiple algorithms that combine integer programming techniques with continuous NLP solvers.

Layer 3 | 35 annotated files | Convex MINLP

Problem Class

Bonmin solves problems of the form:

$$\min_{x,y} \quad f(x, y)$$

Subject to: $$g(x, y) \leq 0$$ $$x \in \mathbb{R}^n, \quad y \in {0,1}^m$$

Where $f$ and $g$ are convex functions.

Algorithm Selection

Bonmin implements six algorithms, selectable via the algorithm option:

Algorithm Details

B-BB (NLP Branch-and-Bound):

• Solves full NLP relaxation at every node
• Uses Ipopt for continuous subproblems
• Most reliable but computationally expensive

B-OA (Outer Approximation):

• Alternates between MILP master and NLP subproblems
• MILP provides lower bound, NLP provides feasible points
• Generates linearization cuts from NLP solutions

B-QG (Quesada-Grossmann):

• Single B&B tree with OA cuts generated during search
• Adds cuts at integer-feasible nodes
• Often faster than pure OA

B-Hyb (Hybrid - Default):

• Combines OA cuts with occasional NLP solves
• Solves NLP at "important" nodes (root, promising candidates)
• Typically best performance across problem classes

Outer Approximation Cuts

For a convex constraint $g(x) \leq 0$ at solution point $x^*$:

$$g(x^) + \nabla g(x^)^T (x - x^*) \leq 0$$

This linear outer approximation is valid because $g$ is convex. Collecting cuts from multiple NLP solutions progressively tightens the approximation.

                    True feasible region (convex)
                   /
     ─────────────●─────────────  ← OA cut from x₁*
                 ╱ ╲
     ──────────●───●────────────  ← OA cuts tighten
              ╱     ╲
     ────────●───────●──────────  ← More cuts → better approximation
            (MILP feasible region shrinks toward true region)

Key Components

Solver Interfaces

Heuristics

Cut Generators

Feasibility Pump

The Feasibility Pump finds integer-feasible solutions by alternating:

1. Round: $\tilde{y} = \text{round}(y^*)$ for integer variables
2. Project: Solve NLP to minimize distance to $\tilde{y}$

$$\min_{x,y} \quad |y - \tilde{y}|_p \quad \text{s.t.} \quad g(x,y) \leq 0$$

3. Check: If $y^* = \tilde{y}$, found feasible solution
4. Repeat: Otherwise, iterate with cycle detection

Branching Strategies

Strong Branching

Solve NLP subproblems for candidate variables to estimate bound improvement:

class QpBranchingSolver {
    // Solve QP approximation for fast strong branching
    // Much faster than full NLP strong branching
};

Pseudocost Branching

Track historical bound changes per variable:

• BonPseudoCosts: Maintain pseudocost statistics
• Blend with strong branching via reliability branching

Usage Example

#include "BonBonminSetup.hpp"
#include "BonCbc.hpp"

// Define your MINLP problem (inherit from TMINLP)
class MyMINLP : public Bonmin::TMINLP {
    // ... implement eval_f, eval_g, eval_grad_f, etc.
};

int main() {
    Bonmin::BonminSetup bonmin;
    bonmin.initializeOptionsAndJournalist();

    // Set algorithm (default is B-Hyb)
    bonmin.options()->SetStringValue("algorithm", "B-Hyb");

    // Initialize with your problem
    SmartPtr<MyMINLP> tminlp = new MyMINLP();
    bonmin.initialize(tminlp);

    // Solve
    Bonmin::Bab bb;
    bb(bonmin);

    // Get solution
    if (bb.bestSolution()) {
        // Access optimal values
    }
}

Source Files

Core Setup

Algorithms

Heuristics

Dependencies

• Cbc: Branch-and-cut MILP solver for master problems
• Ipopt: Interior point NLP solver for continuous subproblems
• CoinUtils: Sparse matrix infrastructure
• Osi: Solver interface abstraction

References

• Bonami, P., et al. (2008). "An algorithmic framework for convex mixed integer nonlinear programs", Discrete Optimization 5(2):186-204
• Duran, M.A., Grossmann, I.E. (1986). "An outer-approximation algorithm for a class of mixed-integer nonlinear programs", Mathematical Programming 36:307-339
• Quesada, I., Grossmann, I.E. (1992). "An LP/NLP based branch and bound algorithm for convex MINLP optimization problems", Computers & Chemical Engineering 16:937-947