|
|||||
|
|
A branch and cut approach to the cardinality constrained circuit problem |
|
| Authors: | P Bauer JT Linderoth MWP Savelsbergh |
| Institution: | (1) Siemens AG, Corporate Research and Development, ZT SE 4, 81730 Munich, Germany e-mail: Petra.Bauer@mchp.siemens.de, DE;(2) Axioma, Inc., 501-F Johnson Ferry Road, Marietta, GA 30068, USA e-mail: jlinderoth@axiomainc.com, US;(3) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA, e-mail: mwps@isye.gatech.edu, US |
| 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. Received: April 1998 / Accepted: October 2000?Published online October 26, 2001 |
| Keywords: | : cardinality constrained circuit problem – circuit polytope – branch and cut |
| 本文献已被 SpringerLink 等数据库收录！ | |