Branching and bounds tightening techniques for non-connvex MINLP. (English) Zbl 1179.90237

Belotti, Pietro; Lee, Jon; Liberti, Leo; Margot, François; Wächter, Andreas

Optim. Methods Softw. 24, No. 4-5, 597-634 (2009).

Summary: Many industrial problems can be naturally formulated using mixed integer non-linear programming (MINLP) models and can be solved by spatial Branch& Bound (sBB) techniques. We study the impact of two important parts of sBB methods: bounds tightening (BT) and branching strategies. We extend a branching technique originally developed for MILP, reliability branching, to the MINLP case. Motivated by the demand for open-source solvers for real-world MINLP problems, we have developed an sBB software package named couenne (Convex Over- and Under-ENvelopes for Non-linear Estimation) and used it for extensive tests on several combinations of BT and branching techniques on a set of publicly available and real-world MINLP instances. We also compare the performance of couenne with a state-of-the-art MINLP solver.

MSC:

90C11	Mixed integer programming
90C26	Nonconvex programming, global optimization
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

mixed-integer non-linear programming; Couenne; branching rules; bounds tightening

Software:

Couenne