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 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.
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|