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

DOI10.1007/s12532-019-00171-5zbMath1437.90133OpenAlexW2972535982WikidataQ127283819 ScholiaQ127283819MaRDI QIDQ2175443

Marco E. Lübbecke, Michael Bastubbe

Publication date: 29 April 2020

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-019-00171-5

zbMATH Keywords

hypergraphinteger programmingmatrix decompositionbalanced vertex separator

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Hypergraphs (05C65) Combinatorial optimization (90C27) Boolean programming (90C09) Decomposition methods (49M27)

Related Items

Critical node/edge detection problems on trees, Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem, A data driven Dantzig-Wolfe decomposition framework, On integer and bilevel formulations for the \(k\)-vertex cut problem, Political districting to minimize cut edges

Uses Software

• MIPLIB

Cites Work

• Complementary column generation and bounding approaches for set partitioning formulations
• An instance of the cutting stock problem for which the rounding property does not hold
• Finding good approximate vertex and edge partitions is NP-hard
• Plant location with minimum inventory
• Minimal proper non-IRUP instances of the one-dimensional cutting stock problem
• Parametric power supply networks
• The vertex \(k\)-cut problem
• The vertex separator problem: algorithms and computations
• The vertex separator problem: a polyhedral investigation
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• Partitioning Hypergraphs in Scientific Computing Applications through Vertex Separators on Graphs
• A Linear Programming Approach to the Cutting-Stock Problem
• Dual-Optimal Inequalities for Stabilized Column Generation
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Decomposing Matrices into Blocks
• Permuting Sparse Rectangular Matrices into Block-Diagonal Form
• Selected Topics in Column Generation
• Disconnecting graphs by removing vertices: a polyhedral approach
• Benchmarking optimization software with performance profiles.