A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs

DOI10.1145/2851492zbMath1365.90252OpenAlexW2333163996MaRDI QIDQ5266610

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

zbMATH Keywords

column generationpacking problembranch-price-and-cut

Mathematics Subject Classification ID

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

Related Items (1)

A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs

Uses Software

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

Cites Work

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

This page was built for publication: A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs