Cover Inequalities for Binary-Integer Knapsack Constraints

Lejeune Miguel (mlejeuneandromeda.rutgers.edu)
Ruszczynski Andrzej (ruszrutcor.rutgers.edu)

Abstract: We consider knapsack constraints involving one general integer and many binary variables. We introduce the concept of a cover for such a constraint and we construct a new family of valid inequalities based on this concept. We generalize this idea to extended covers, and we propose a specialized lifting procedure for cover inequalities. Finally, we illustrate the efficiency of our approach on a large-scale real world supply chain optimization problem.

Keywords: Cover inequality, general integer variables, extended cover, lifting, supply chain management

Category 1: Integer Programming

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

Citation: Submitted, Rutgers Technical Report.

Download: [Postscript]

Entry Submitted: 02/24/2004
Entry Accepted: 02/25/2004
Entry Last Modified: 02/24/2004

Modify/Update this entry