Facets from Gadgets
Adam N. Letchford (A.N.Letchfordlancaster.ac.uk)
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.
Keywords: branch-and-cut; gadgets; traveling salesman problem; stable set problem; clique partitioning problem
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Combinatorial Optimization (Branch and Cut Algorithms )
Category 3: Integer Programming (Cutting Plane Approaches )
Citation: Eventually published as: A.N. Letchford & A.N. Vu (2021) Facets from gadgets. Math. Program., 185(1-2), 297-314.
Entry Submitted: 01/06/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|