Target Cuts from Relaxed Decision Diagrams

Christian Tjandraatmadja () and Willem-Jan van Hoeve ()
Additional contact information
Christian Tjandraatmadja: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Willem-Jan van Hoeve: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 285-301

Abstract: 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.

Keywords: integer programming; cutting planes; decision diagrams (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0830 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:2:p:285-301

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().