Presentation on YouTube.

Given a ground-set of elements and a family of subsets, the set covering problem consists in choosing a minimum number of elements such that each subset contains at least one of the chosen elements. In this work, we study the set-covering polyhedron which is the convex hull of integer solutions of the set-covering problem. In particular, we link the study of the facets of the set-covering polyhedron to the theory of inequality tilting. This theory, introduced by Chvatal et al. (2013), studies how inequalities can be rotated around their contact points with a polyhedron in order to obtain new inequalities that induce faces of higher dimension. To that end, we introduce the \textit{tilting vectors} which characterize the degrees of freedom of the possible rotations of a valid inequality. We will present the following contributions. We study how tilting vectors characterize facet-defining inequalities. We show that tilting vectors can be used to tilt inequalities similarly to the procedure proposed by Chvatal et al. (2013). We present how the number of computations required to tilt an inequality can be reduced when the inequality has a lot of zero coefficients. Finally, we use the tilting vectors to extend several necessary and/or sufficient conditions for facets of the set-covering polyhedron presented by Cornuéjols and Sassano (1989), Sassano (1989) and Balas and Ng (1989).

Bio: Francois Lamothe is post-doctoral intern at UQAM and Cirrelt working in collaboration with Claudio Contardo and Matthieu Gruson. He finished a PhD at ISAE-Supaero in France where his main topics were flow problems - especially unsplittable flow problems - and decomposition methods. However, his research interests more broadly lie in anything related to Mixed Integer Linear Programming and he is now working on the structure of set covering polytopes.