We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly NP-hard. To improve the performance of mixed-integer programming-based schemes for these problems, we introduce and analyze a coefficient strengthening scheme, adapt and analyze an existing cutting plane technique, and present a branching technique. Through computational experiments, we empirically verify that these techniques are significantly effective in improving solution times over the CPLEX mixed-integer programming solver. In particular, we observe that the proposed schemes can cut down solution times from as much as six days to under four hours.
['Feng Qiu', 'Shabbir Ahmed', 'Santanu S. Dey', 'Laurence A. Wolsey']
Covering linear programming with violations