Ideal clutters Original Research Article

The Operations Research model known as the Set Covering Problem has a wide range of applications. See for example the survey by Ceria, Nobili and Sassano and edited by DellʹAmico, Maffioli and Martello (Annotated Bibliographies in Combinatorial Optimization, Wiley, New York, 1997). Sometimes, due to the special structure of the constraint matrix, the natural linear programming relaxation yields an optimal solution that is integer, thus solving the problem. Under which conditions do such integrality properties hold? This question is of both theoretical and practical interest. On the theoretical side, polyhedral combinatorics and graph theory come together in this rich area of discrete mathematics. In this tutorial, we present the state of the art and open problems on this question.