A. Letchford, P. Ventura
The stable set polytope is a fundamental object in combinatorial optimisation. Among the many valid inequalities that are known for it, the clique-family inequalities play an important role. Pecher and Wagler showed that the clique-family inequalities can be strengthened under certain conditions. We show that they can be strengthened even further, using a surprisingly simple mixed-integer rounding argument. Examples are given of new facet-defining inequalities that can be derived in this way.
Keywords: stable set problem, cutting planes, polyhedral combinatorics
Scheduled
TC2 Integer Optimization
June 10, 2021 12:30 PM
2 - LV Kantorovich
