Seminar Details:

LANS Informal Seminar
"Heuristics to find feasible solutions of Mixed Integer Nonlinear Problems"

DATE: June 29, 2011

TIME: 15:00:00 - 16:00:00
SPEAKER: Pietro Belotti, Dept. of Mathematical Sciences, Clemson University
LOCATION: Building 240, Conference Center 1404-1405, Argonne National Laboratory

[related website]

Description:
Mixed Integer Nonlinear Programming (MINLP) problems consist of minimizing a nonlinear function subject to nonlinear constraints and the integrality of a subset of variables. These problems can be solved by branch-and-bound algorithms equipped with procedures that reduce the solution space and allow to find good lower bounds on the optimal solution.

Finding good feasible solutions is equally important and just as difficult, as one deals with two types of nonconvexity: nonlinear constraints and integrality of some variables. Inspired by a technique that proved successful in Mixed Integer Linear problems, we have developed a variant of the Feasibility Pump for MINLPs.

Unlike some previous extensions of the Feasibility Pump to MINLP, our version uses a valid relaxation of the MINLP problem provided by Couenne, an Open-Source solver for MINLPs available from the COIN-OR initiative. We present results on mid-size and large MINLP instances available from well-known instance libraries.

(Joint work with Timo Berthold, Zuse Institute Berlin)


 

Please send questions or suggestions to Krishna: snarayan at mcs.anl.gov.