期刊
INFORMS JOURNAL ON COMPUTING
卷 31, 期 2, 页码 285-301出版社
INFORMS
DOI: 10.1287/ijoc.2018.0830
关键词
integer programming; cutting planes; decision diagrams
资金
- Office of Naval Research [N00014-18-1-2129]
The most common approach to generate cuts in integer programming is to derive them from the linear programming relaxation. We study an alternative approach that extracts cuts from discrete relaxations known as relaxed decision diagrams. Through a connection between decision diagrams and polarity, the algorithm generates cuts that are facet defining for the convex hull of a decision diagram relaxation. As proof of concept, we provide computational evidence that this algorithm generates strong cuts for the maximum independent set problem and the minimum set covering problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据