Abstract | ||
---|---|---|
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 & 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. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/s10107-005-0594-3 | Math. Program. |
Keywords | DocType | Volume |
portfolio optimi- zation,mixed integer program,mixed-integer programs,unit commitment problem,mean-variance problem,objective function,mixed-integer programming problem,perspective cut,costly nonlinear programming problem,specific structure,perspective function,general family,required structure,valid inequalities,portfolio optimization,nonlinear programming,electric power | Journal | 106 |
Issue | ISSN | Citations |
2 | 1436-4646 | 62 |
PageRank | References | Authors |
2.92 | 10 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
A. Frangioni | 1 | 110 | 7.54 |
C. Gentile | 2 | 104 | 7.94 |