Solving nonconvex MINLP by quadratic approximation<br/><br/>

Friday, November 21, 2008 - 11:15am - 12:00pm
EE/CS 3-180
Stefan Vigerske (Humboldt-Universität)
We present the extended Branch and Cut algorithm implemented in the software package LaGO for the solution of block-separable nonconvex mixed-integer nonlinear programs.

The algorithm reformulates every function into a block-separable form and computes convex underestimators for each term separately. For that purpose, nonquadratic functions are first replaced by quadratic underestimators using a powerful heuristic. Nonconvex quadratic functions are then replaced by exakt convex underestimators.

Finally, a linear outer approximation is constructed by linearization of the convex relaxation and the generation of mixed-integer rounding cuts and linearized interval gradient cuts.

The efficiency of the method is improved by the application of a simple constraint propagation technique based on interval arithmetic.
MSC Code: