Campuses:

Branching strategies and heurisitcs in a<br/><br/>branch-and-bound for convex MINLPs<br/><br/>

Monday, November 17, 2008 - 10:30am - 11:15am
EE/CS 3-180
Pierre Bonami (Centre National de la Recherche Scientifique (CNRS))
Different variants of the branch-and-bound algorithm exist for solving exactly convex MINLPs. These variants differ mainly in the relaxation solved at the nodes of the tree. There are mainly two variants: one that solves a nonlinear programming relaxation at each node and one that solves a linear programming relaxation. In recent year the linear programming based branch-and-bounds have shown to be more effective on large sets of problems. In this talk, we study techniques to make the nonlinear programming based branch-and-bound more competitive. In particular, we study branching strategies and heuristics. The techniques have been implemented in the open-source solver Bonmin We present computational results to assess the effectiveness of the proposed strategies and compare the resulting algorithm with a linear programming (outer approximation based) branch-and-cut.

This talk is based on joint works with Joao Goncalves, Jon Lee and Andreas Waechter.
MSC Code: 
90C57
Keywords: