Extended formulations for the A-cut problem |
| |
Authors: | Sunil Chopra Jonathan H Owen |
| |
Institution: | (1) Department of Managerial Economics and Decision Sciences, J.L. Kellogg Graduate School of Management, Northwestern University, 2001 Sheridan Road, 50208-2001 Evanston, IL, USA;(2) Department of Industrial Engineering and Management Sciences Robert R. McCormick School of Engineering, Northwestern University, 60208 Evanston, IL, USA |
| |
Abstract: | LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been
considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations
are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added).
This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation
of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations.
Computational results using the extended formulations are performed. |
| |
Keywords: | A-cut Polyhedron Facets |
本文献已被 SpringerLink 等数据库收录! |
|