# Networks

## 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.

View all

View all