Facets of The Cardinality Constrained Circuit Polytope

Petra Bauer (Petra.Bauermchp.siemens.de)
Jeff Linderoth (jlinderothaxiomainc.com)
Martin Savelsbergh (mwpsisye.gatech.edu)

Abstract: The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most $k$ edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits.

Keywords:

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Polyhedra )

Citation:

Download: [Postscript]

Entry Submitted: 07/05/2001
Entry Accepted: 07/06/2001
Entry Last Modified: 07/05/2001

Modify/Update this entry