Perspective cuts for a class of convex 0-1 mixed integer programs
Perspective cuts for a class of convex 0-1 mixed integer programs
复制标题
DOI：
10.1007/s10107-005-0594-3
复制
发表时间：
2006-06-01
影响因子：
2.7
通讯作者：
Gentile, C
中科院分区：
文献类型：
--
作者：
Frangioni, A;Gentile, C
我们证明，具有特定结构的混合整数规划问题的目标函数的凸包络是目标函数连续部分的透视函数。使用透视函数次微分的表征，我们推导出“透视切割”，这是该问题的一系列有效的不等式。透视切割可以被证明属于析取切割的一般族，但它们不需要将潜在昂贵的非线性规划问题的解分开。使用透视切割可以显着提高至少两个模型的分支与切割方法的性能，这些模型“自然”地或在适当的重新公式化之后具有所需的结构：电力生产中的单位承诺问题和投资组合优化中的均值方差问题。
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.