Bi-Criteria Set Covering Problem with Conflict Constraints

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, and we seek to identify (select) a subset of columns so as to achieve two distinct objectives. The first objective is to maximize the number of rows covered by the selected subset of columns, and the second objective is to minimize the number of selected columns. In this context, we present a bi-criteria integer programming (IP) model and two corresponding epsilon-constraint methods to find the non-dominated frontier for this bi-criteria optimization problem. We then propose several families of valid inequalities for the corresponding IP models. Finally, through computational experiments, we demonstrate the effectiveness of the proposed methods