Optimization Online


Facets from Gadgets

Adam N. Letchford (A.N.Letchford***at***lancaster.ac.uk)
Anh N. Vu (a.vu***at***lancaster.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
Entry Accepted: 01/23/2018
Entry Last Modified: 02/18/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society