A branch-price-and-cut algorithm for packing cuts in undirected graphs

DOI10.1145/2851492MaRDI QIDQ5266610zbMATH OpenOpenAlexFDO

Authors Martin Bergner, Marco E. Lübbecke, Jonas T. Witt

Publication date 16 June 2017

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2851492

zbMATH Keywords

column generationpacking problembranch-price-and-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Packing cuts in undirected graphs
• scientific article; zbMATH DE number 1875440
• Publication:4938789
• A branch-and-cut algorithm for the equicut problem
• Packing Steiner trees: A cutting plane algorithm and computational results

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A Minimax Theorem for Directed Graphs
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• A branch and cut solver for the maximum stable set problem
• A branch-price-and-cut algorithm for packing cuts in undirected graphs
• A simple min-cut algorithm
• An Integer Programming Approach to the Vehicle Scheduling Problem
• Blocking and anti-blocking pairs of polyhedra
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Data reduction, exact, and heuristic algorithms for clique cover
• Edge-packings of graphs and network reliability
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph Partitioning and Graph Clustering
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• P-Complete Approximation Problems
• Packing cuts in undirected graphs
• Packing cycles in undirected graphs
• Parametrized complexity theory.
• SCIP: solving constraint integer programs

Cited in

(6)

• The multi-terminal vertex separator problem: branch-and-cut-and-price
• A branch-price-and-cut algorithm for packing cuts in undirected graphs
• A branch‐and‐cut algorithm for the irregular strip packing problem with uncertain demands
• Directed cut transversal packing for source-sink connected graphs
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Packing cuts in undirected graphs

Describes a project that uses

Uses Software

• Randgraph
• Rudy
• GCG
• DIMACS
• BHOSLIB
• SCIP
• NetworkX

This page was built for publication: A branch-price-and-cut algorithm for packing cuts in undirected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266610)