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 stable set and clique partitioning problems.

Keywords: branch-and-cut; gadgets; 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: Working paper, Department of Management Science, Lancaster University, December 2017.

Download: [PDF]

Entry Submitted: 01/06/2018
Entry Accepted: 01/23/2018
Entry Last Modified: 01/06/2018

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