Extended formulations for the A-cut problem

Sunil Chopra*, Jonathan H. Owen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Let G = (V, E) be an undirected graph and A ⊆ V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes in A. 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.

Original languageEnglish (US)
Pages (from-to)7-30
Number of pages24
JournalMathematical Programming, Series B
Volume73
Issue number1
DOIs
StatePublished - Apr 30 1996

Keywords

  • A-cut
  • Facets
  • Polyhedron

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Extended formulations for the A-cut problem'. Together they form a unique fingerprint.

Cite this