Home > Research > Publications & Outputs > Facets from gadgets

Associated organisational unit

Electronic data

  • gadgets

    Rights statement: 12M

    Accepted author manuscript, 339 KB, PDF document

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


Text available via DOI:

View graph of relations

Facets from gadgets

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>1/01/2021
<mark>Journal</mark>Mathematical Programming
Issue number1-2
Number of pages18
Pages (from-to)297-314
Publication StatusPublished
Early online date14/09/19
<mark>Original language</mark>English


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.