A strong formulation for the graph partition problem

Sunil Chopra, Sangho Shim*

*Corresponding author for this work

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)183-202
Number of pages20
JournalNetworks
Volume75
Issue number2
DOIs
StatePublished - Mar 1 2020

    Fingerprint

Keywords

  • combinatorial optimization
  • extended formulation
  • extended graph formulation
  • graph partition problem
  • integer programming
  • network clustering
  • primal dual construction

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this