Take Action

Home | Faculty & Research Overview | Research

Research Details

An Extended Formulation for the A-Cut Problem, Mathematical Programming

Abstract

Let G=(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.

Type

Article

Author(s)

Sunil Chopra, Jonathan H. Owen

Date Published

1996

Citations

Chopra, Sunil, and Jonathan H. Owen. 1996. An Extended Formulation for the A-Cut Problem. Mathematical Programming. 73(1): 7-30.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action