Optimization Online


A Branch-and-Price Algorithm for Capacitated Hypergraph Vertex Separation

Michael Bastubbe(bastubbe***at***or.rwth-aachen.de)
Marco E. Lübbecke(luebbecke***at***or.rwth-aachen.de)

Abstract: We exactly solve the NP-hard combinatorial optimization problem of finding a minimum cardinality vertex separator with k (or arbitrarily many) capacitated shores in a hypergraph. We present an exponential size integer programming formulation which we solve by branch-and-price. The pricing problem, an interesting optimization problem on its own, has a decomposable structure that we exploit in preprocessing. We perform an extensive computational study, in particular on hypergraphs coming from the application of re-arranging a matrix into single-bordered block-diagonal form. Our experimental results show that our proposal complements the previous exact approaches in terms of applicability for larger k, and significantly outperforms them in the case of arbitrary k.

Keywords: hypergraph; balanced vertex separator; matrix decomposition; integer programming

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization

Citation: report 2017-040, RWTH Aachen University, November 2017

Download: [PDF]

Entry Submitted: 11/21/2017
Entry Accepted: 11/21/2017
Entry Last Modified: 11/21/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society