Qiu, Feng
[Georgia Institute of Technology]
Ahmed, Shabbir
[Georgia Institute of Technology]
Dey, Santanu S.
[Georgia Institute of Technology]
Wolsey, Laurence
[UCL]
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.
Bibliographic reference |
Qiu, Feng ; Ahmed, Shabbir ; Dey, Santanu S. ; Wolsey, Laurence. Covering linear programming with violations. In: INFORMS Journal on Computing, Vol. 26, no.3, p. 531-546 (2014) |
Permanent URL |
http://hdl.handle.net/2078.1/151837 |