A tutorial on branch and cut algorithms for the maximum stable set problem

DOI10.1111/J.1475-3995.2011.00805.XzbMath1270.90092OpenAlexW2051450977MaRDI QIDQ4918254

Steffen Rebennack, Gerhard Reinelt, Panos M. Pardalos

Publication date: 24 April 2013

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2011.00805.x

zbMATH Keywords

stable setstable set polytopebranch and cutcutting planecliqueseparation

Mathematics Subject Classification ID

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

Related Items (21)

A review on algorithms for maximum clique problems ⋮ Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ Set covering problem with conflict constraints ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ A clique covering MIP model for the irregular strip packing problem ⋮ An Integer Programming Formulation for the Maximum k-Subset Intersection Problem ⋮ Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ Optimization Bounds from Binary Decision Diagrams ⋮ Fixed cardinality stable sets ⋮ General cut-generating procedures for the stable set polytope ⋮ Polylithic modeling and solution approaches using algebraic modeling systems ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Branch-and-cut-and-price algorithm for the constrained-routing and spectrum assignment problem ⋮ Indirect unstructured hex-dominant mesh generation using tetrahedra recombination ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ A note on computational approaches for the antibandwidth problem ⋮ The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope ⋮ Worst-case analysis of clique MIPs

Uses Software

• QUALEX
• Concorde
• PORTA
• DIMACS
• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch and cut solver for the maximum stable set problem
• The strong perfect graph theorem
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• An exact algorithm for the maximum clique problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Matrices with the Edmonds-Johnson property
• Weakly bipartite graphs and the max-cut problem
• Test case generators and computational results for the maximum clique problem
• Wheel inequalities for stable set polytopes
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the separation of maximally violated mod-\(k\) cuts
• A new trust region technique for the maximum weight clique problem
• Exploring the relationship between max-cut and stable set relaxations
• Recognizing Berge graphs
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem
• Finding a Maximum Clique in an Arbitrary Graph
• A global optimization approach for solving the maximum clique problem
• Set Partitioning: A survey
• Using cutting planes to solve the symmetric Travelling Salesman problem
• Continuous Characterizations of the Maximum Clique Problem
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• A branch-and-price approach for the maximum weight independent set problem
• A branch and bound algorithm for the maximum clique problem
• A branch-and-cut algorithm for the maximum cardinality stable set problem

This page was built for publication: A tutorial on branch and cut algorithms for the maximum stable set problem