We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive "perspective cuts", a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly nonlinear programming problem to be separated. Using perspective cuts substantially improves the performance of Branch-and-Cut approaches for at least two models that, either "naturally" or after a proper reformulation, have the required structure: the Unit Commitment problem in electrical power production and the Mean-Variance problem in portfolio optimization.
|Autori:||FRANGIONI A; C. GENTILE|
|Titolo:||Perspective cuts for a class of convex 0–1 mixed integer programs|
|Anno del prodotto:||2006|
|Digital Object Identifier (DOI):||10.1007/s10107-005-0594-3|
|Appare nelle tipologie:||1.1 Articolo in rivista|