Optimization Online


Covering Linear Programming with Violations

Feng Qiu(fqiu***at***gatech.edu)
Shabbir Ahmed(sahmed***at***isye.gatech.edu)
Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Laurence Wolsey(laurence.wolsey***at***uclouvain.be)

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. In order to improve the performance of mixed-integer programming (MIP) 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 MIP solver. In particular, we observe that the proposed schemes can cut down solution times from as much as six days to under four hours in some instances.

Keywords: Integer Programming, Probabilistic Constraints, Branch-and-Bound

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Submitted for publication (2012)

Download: [PDF]

Entry Submitted: 05/08/2012
Entry Accepted: 05/08/2012
Entry Last Modified: 05/08/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society