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

DOI10.1007/S12532-019-00171-5MaRDI QIDQ2175443zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

integer programminghypergraphmatrix decompositionbalanced vertex separator

Mathematics Subject Classification ID

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)

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

Cites work

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

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

Describes a project that uses

Uses Software

• MIPLIB

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)