Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut

DOI10.1051/ro:2006010zbMath1146.90090OpenAlexW2168539132MaRDI QIDQ3430946

Francisco Barahona, Laszlo Ladanyi

Publication date: 5 April 2007

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2006__40_1_53_0

zbMATH Keywords

Steiner treeVolume algorithmMax-Cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Partial Lasserre relaxation for sparse Max-Cut, Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods, Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem, A hybrid Lagrangian metaheuristic for the cross-docking flow shop scheduling problem, On embedding the volume algorithm in a variable target value method., Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, Non delayed relax-and-cut algorithms

Uses Software

• SteinLib
• COIN-OR
• CLP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Experiments in quadratic 0-1 programming
• On the solution of traveling salesman problems
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• On some difficult linear programs coming from set partitioning
• The volume algorithm revisited: relation with bundle methods
• Solving Steiner tree problems in graphs with Lagrangian relaxation
• The volume algorithm: Producing primal solutions with a subgradient method
• Exact ground states of two-dimensional \(\pm J\) Ising spin glasses
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An integer linear programming approach to the steiner problem in graphs
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• A branch and cut algorithm for the Steiner problem in graphs
• Computational Experience with an Interior Point Cutting Plane Algorithm
• Solving Steiner tree problems in graphs to optimality
• On the cut polytope
• Validation of subgradient optimization
• Preprocessing Steiner problems from VLSI layout
• A catalog of steiner tree formulations
• Optimum branchings
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Integer Programming and Combinatorial Optimization
• Improved algorithms for the Steiner problem in networks