A branch and cut approach to the cardinality constrained circuit problem

A branch and cut approach to the cardinality constrained circuit problem

0.00 Avg rating0 Votes
Article ID: iaor2003738
Country: Germany
Volume: 91
Issue: 2
Start Page Number: 307
End Page Number: 348
Publication Date: Jan 2002
Journal: Mathematical Programming
Authors: , ,
Keywords: networks
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, and a branch-and-cut solution approach using these inequalities.

Reviews

Required fields are marked *. Your email address will not be published.