General cut-generating procedures for the stable set polytope
From MaRDI portal
Abstract: We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Camp^{e}lo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.
Recommendations
- A strengthened general cut-generating procedure for the stable set polytope
- Lifting and separation procedures for the cut polytope
- A new facet generating procedure for the stable set polytope
- A branch and cut solver for the maximum stable set problem
- Strong lift-and-project cutting planes for the stable set problem
Cites work
- A branch and cut solver for the maximum stable set problem
- A branch-and-cut algorithm for the maximum cardinality stable set problem
- A computational study of conflict graphs and aggressive cut separation in integer programming
- A new facet generating procedure for the stable set polytope
- A review on algorithms for maximum clique problems
- A tutorial on branch and cut algorithms for the maximum stable set problem
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- An exact bit-parallel algorithm for the maximum clique problem
- COIN-OR
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Conflict graphs in solving integer programming problems
- Critical facets of the stable set polytope
- scientific article; zbMATH DE number 6118217 (Why is no real title available?)
- scientific article; zbMATH DE number 1786225 (Why is no real title available?)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Matching theory
- Maximum-weight stable sets and safe lower bounds for graph coloring
- On the asymmetric representatives formulation for the vertex coloring problem
- Reductions for the stable set problem
- Relaxed approximate coloring in exact maximum clique search
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Set Partitioning: A survey
- Strong lift-and-project cutting planes for the stable set problem
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Valid inequalities for mixed integer linear programs
Cited in
(12)- Local cuts revisited
- A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
- On the combinatorics of the 2-class classification problem
- Coordinated cutting plane generation via multi-objective separation
- The stable set problem: clique and nodal inequalities revisited
- Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques
- scientific article; zbMATH DE number 1594513 (Why is no real title available?)
- A new facet generating procedure for the stable set polytope
- A strengthened general cut-generating procedure for the stable set polytope
- Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
- A survey of some operations research and data sciences applications developed in the last 20 years at argentinian and chilean universities
- Application of the Lovász-Schrijver operator to compact stable set integer programs
This page was built for publication: General cut-generating procedures for the stable set polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752480)
