Normalizations in Lift-and-Project Methods. A view from Convex Analysis

Claudia Sagastizábal | Rey, Pablo A.

Keywords: Lift-and-Project | disjunctive cuts | Branch-and-Cut | cutting planes | 0-1 integer programming.

Branch-and-Cut algorithms for general 0-1 mixed integer programs can be successfully implemented by using Lift-and-Project (L\&P) methods to gene rate cuts. L\&P cuts are drawn from a cone of valid inequalities that is unbounded and, thus, needs to be truncated, or ``normalized''. We consider general normalizations defined {\bf by} arbitrary closed convex sets and derive dual problems for generating L\&P cuts. This unified theoretical framework generalizes and covers a wide group of already known normalizations. We also give conditions for proving finite convergence of the cutting-plane procedure that results from using such general L\&P cuts. \

Anexos:

• claudia-pablo-anor.ps