Facets from gadgets
成果类型：
Article
署名作者：
Letchford, Adam N.; Vu, Anh N.
署名单位：
Lancaster University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01430-y
发表日期：
2021
页码：
297-314
关键词：
摘要：
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.