A branch-and-price algorithm for capacitated hypergraph vertex separation

  • 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 k=∞.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Michael BastubbeORCiD, Marco E. LübbeckeORCiD
DOI:https://doi.org/10.1007/s12532-019-00171-5
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2019
Tag:Software; Theoretical Computer Science
Volume:12
Issue:1
Page Number:30
First Page:39
Last Page:68
Mathematical Programming Computation :MPC 2020 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.