Covering linear programming with violations

Qiu, Feng;Ahmed, Shabbir;Dey, Santanu S.;Wolsey, Laurence
(2014) INFORMS Journal on Computing — Vol. 26, n° 3, p. 531-546 (2014)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 379.53 KB
Request a copy

Details

Authors
  • Qiu, FengGeorgia Institute of Technology
    Author
  • Ahmed, ShabbirGeorgia Institute of Technology
    Author
  • Dey, Santanu S.Georgia Institute of Technology
    Author
  • Wolsey, LaurenceUCLouvain
    Author
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Qiu, F., Ahmed, S., Dey, S. S., & Wolsey, L. (2014). Covering linear programming with violations. INFORMS Journal on Computing, 26(3), 531-546. https://doi.org/10.1287/ijoc.2013.0582 (Original work published 2014)