Rights statement: 12M
Accepted author manuscript, 339 KB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Facets from gadgets
AU - Letchford, Adam
AU - Vu, Anh
PY - 2021/1/1
Y1 - 2021/1/1
N2 - 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) cuttingplanes, accompanied by efficient separation algorithms. We illustrate the power of this approach on the asymmetric traveling salesman, stable set and clique partitioning problems.
AB - 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) cuttingplanes, accompanied by efficient separation algorithms. We illustrate the power of this approach on the asymmetric traveling salesman, stable set and clique partitioning problems.
KW - Branch-and-cut
KW - Gadgets
KW - Traveling salesman problem
KW - Stable set problem
KW - Clique partitioning problem
U2 - 10.1007/s10107-019-01430-y
DO - 10.1007/s10107-019-01430-y
M3 - Journal article
VL - 185
SP - 297
EP - 314
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1-2
ER -