A branch-and-price algorithm for capacitated hypergraph vertex separation
DOI10.1007/S12532-019-00171-5zbMATH Open1437.90133OpenAlexW2972535982WikidataQ127283819 ScholiaQ127283819MaRDI QIDQ2175443FDOQ2175443
Authors: Michael Bastubbe, Marco E. Lübbecke 
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
Recommendations
- An exact algorithm for solving the vertex separator problem
- The vertex separator problem: a polyhedral investigation
- The multi-terminal vertex separator problem: branch-and-cut-and-price
- The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
- The vertex separator problem: algorithms and computations
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10) Hypergraphs (05C65) Decomposition methods (49M27) Boolean programming (90C09)
Cites Work
- Benchmarking optimization software with performance profiles.
- A Linear Programming Approach to the Cutting-Stock Problem
- Selected Topics in Column Generation
- Finding good approximate vertex and edge partitions is NP-hard
- Integer Rounding for Polymatroid and Branching Optimization Problems
- The vertex separator problem: a polyhedral investigation
- Decomposing Matrices into Blocks
- Complementary column generation and bounding approaches for set partitioning formulations
- The vertex separator problem: algorithms and computations
- An instance of the cutting stock problem for which the rounding property does not hold
- Minimal proper non-IRUP instances of the one-dimensional cutting stock problem
- Dual-Optimal Inequalities for Stabilized Column Generation
- Plant location with minimum inventory
- Disconnecting graphs by removing vertices: a polyhedral approach
- Permuting Sparse Rectangular Matrices into Block-Diagonal Form
- Covering edges by cliques with regard to keyword conflicts and intersection graphs
- Parametric power supply networks
- Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
- Automatic Dantzig-Wolfe reformulation of mixed integer programs
- The vertex \(k\)-cut problem
Cited In (6)
- The multi-terminal vertex separator problem: branch-and-cut-and-price
- A data driven Dantzig-Wolfe decomposition framework
- Critical node/edge detection problems on trees
- On integer and bilevel formulations for the \(k\)-vertex cut problem
- Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
- Political districting to minimize cut edges
Uses Software
This page was built for publication: A branch-and-price algorithm for capacitated hypergraph vertex separation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175443)
