2022 journal article
Set covering problem with conflict constraints
COMPUTERS & OPERATIONS RESEARCH, 143.
author keywords: Set covering; Stable set; Integer programming; Valid inequalities; Pre-processing
open access via www.lib.ncsu.edu (repository)
UN Sustainable Development Goal Categories
10. Reduced Inequalities
(OpenAlex)
11. Sustainable Cities and Communities
(Web of Science)
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.