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

DOI10.1145/2851492zbMATH Open1365.90252OpenAlexW2333163996MaRDI QIDQ5266610FDOQ5266610

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

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

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

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)

Cites Work

• SCIP: solving constraint integer programs
• Graph Partitioning and Graph Clustering
• Parametrized complexity theory.
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• P-Complete Approximation Problems
• Blocking and anti-blocking pairs of polyhedra
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• A Minimax Theorem for Directed Graphs
• Edge-packings of graphs and network reliability
• Title not available (Why is that?)
• A branch and cut solver for the maximum stable set problem
• An Integer Programming Approach to the Vehicle Scheduling Problem
• A simple min-cut algorithm
• Packing cycles in undirected graphs
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
• A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs
• Packing cuts in undirected graphs

Cited In (6)

• The multi-terminal vertex separator problem: branch-and-cut-and-price
• 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
• A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs

Uses Software

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

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)