-

 

 

 




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: Accepted for publication in Mathematical Programming.

Download:

Entry Submitted: 01/06/2018
Entry Accepted: 01/23/2018
Entry Last Modified: 04/30/2020

Modify/Update this entry


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

 

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