A strong formulation for the graph partition problem

Journal Article

Abstract We develop a polynomial size extended graph formulation of the graph partition problem which dominates the formulation introduced by Chopra and Rao's study, and show that the extended graph formulation is tight on a tree. We introduce exponentially many valid inequalities to the Chopra‐Rao formulation, which we call generalized arc inequalities (GAI), and develop a linear time algorithm to separate the most violated generalized arc inequality. We show that the polynomial size extended graph formulation is equivalent to the Chopra‐Rao formulation augmented by the exponentially many GAI.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.