Covering Linear Programming with Violations

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 𝒩𝒫-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.