2022 journal article

Set covering problem with conflict constraints


By: S. Saffari* & Y. Fathi n‚ÄČ

author keywords: Set covering; Stable set; Integer programming; Valid inequalities; Pre-processing
UN Sustainable Development Goal Categories
10. Reduced Inequalities (OpenAlex)
Source: Web Of Science
Added: May 23, 2022

In this article, we consider the set covering problem with conflict constraints, i.e., from each conflicting pair of columns at most one column can appear in the feasible solution. For this problem, we propose appropriate pre-processing techniques and several families of Valid Inequalities (VIs) for the corresponding integer programming model that result from the simultaneous presence of the set covering constraints and the stable set (conflict) constraints. We then carry out a computational experiment to demonstrate the effectiveness of the proposed methods.