Target Cuts from Relaxed Decision Diagrams

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, th...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2019-03, Vol.31 (2), p.285-301
Main Authors: Tjandraatmadja, Christian, van Hoeve, Willem-Jan
Format: Article
Language:English
Subjects:
Algorithms
Computational geometry
Convexity
cutting planes
decision diagrams
Decision theory
Hulls
Integer programming
Linear programming
Methods
Polarity
Set theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. The online appendices are available at https://doi.org/10.1287/ijoc.2018.0830 .
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.2018.0830