M/511

One of the foremost difficulties in solving Mixed Integer Nonlinear Programs (MINLP), either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex MINLPs. Feasibility pumps are successive projection algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems; such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex MINLPs. Both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex MINLP such a property does not hold and the main innovations in this paper are tailored algorithmic methods to overcome such a difficulty. In this talk, we review the Feasibility Pump evolution from the original one proposed by Fischetti, Glover, and Lodi (2005) to the one addressed to nonconvex Mixed Integer Nonlinear Programming problems, one of the first effective heuristics proposed for general MINLPs.

Claudia D`Ambrosio

LIX, École Polytechnique