You are here

Global Constraint for the Set Covering Problem

TitleGlobal Constraint for the Set Covering Problem
Publication TypeConference Paper
Year of Publication2007
AuthorsMouthuy, Sébastien, Deville Yves, and Dooms Grégoire
Conference NameTroisième Journées Francophones de Programmation par Contraintes (JFPC'07)
Date Publishedjun
Abstract

This paper proposes a constraint programming approach to solve the set covering problem. This combinatorial optimisation problem is very useful to formulate a lot of real-life applications (crew assignment, scheduling, construction of optimal logical circuits) and a lot of other well-known combinatorial optimisation problem (vertex cover, dominating set, independent set). The set covering problem is NP-Complete. This paper proposes a constraint SC for the set covering problem and a propagator using a lower bound based on an IP relaxation. We also present an incremental algorithm for computing this lower bound whose internal data structure can be updated very quickly for small changes in the problem, making it particularly well-suited for search-tree schemes. Our approach will be compared with two other propagators based on the linear relaxation and on a greedy approach.