A Study of the Set-Covering Polyhedron Through Tilting Vectors

Explore a 22-minute DS4DM Coffee Talk by François Lamothe from Université du Québec à Montréal, delving into the set-covering polyhedron through tilting vectors. Examine the connection between facets of the set-covering polyhedron and inequality tilting theory, introduced by Chvatal et al. (2013). Learn about tilting vectors and their role in characterizing facet-defining inequalities and rotating valid inequalities. Discover how to reduce computations when tilting inequalities with numerous zero coefficients. Investigate the extension of necessary and sufficient conditions for facets of the set-covering polyhedron, building upon work by Cornuéjols and Sassano (1989), Sassano (1989), and Balas and Ng (1989). Follow the presentation's structure, covering the set covering problem, cover hypograph, inequalities, contact points, sub hypograph, tilting vector creation, and a simple algorithm for tilting inequalities.