A branch-and-price algorithm for capacitated hypergraph vertex separation
From MaRDI portal
Publication:2175443
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
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
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.