Home > Research > Publications & Outputs > Facets from gadgets

Associated organisational unit

Electronic data

  • gadgets

    Rights statement: 12M

    Accepted author manuscript, 339 KB, PDF document

    Embargo ends: 14/09/20

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Facets from gadgets

Research output: Contribution to journalJournal article

E-pub ahead of print
<mark>Journal publication date</mark>14/09/2019
<mark>Journal</mark>Mathematical Programming
Publication statusE-pub ahead of print
Early online date14/09/19
Original languageEnglish

Abstract

We present a new tool for generating cutting planes for NP-hard combinatorial optimisation problems. It is based on the concept of gadgets — small subproblems that are “glued” together to form hard problems — which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families of strong (and sometimes facet-defining) cutting
planes, accompanied by efficient separation algorithms. We illustrate the power of this approach on the asymmetric traveling salesman, stable set and clique partitioning problems.