Valid inequalities for the multi-dimensional multiple-choice 0–1 knapsack problem

• Derives valid inequalities for the minimizing form of the multiple-choice 0–1 knapsack problem.
• Derives and establishes αα-covers and αα-cover inequalities.
• Presents sequential and sequence-independent lifting procedures.
• Computational tests assess the strength of resulting inequalities.
• Tests inequalities in application to the multi-dimensional, multiple-choice 0–1 knapsack problem.

This paper presents a study of the polytope defined by the minimizing form of the binary knapsack inequality, which is a greater-than-or-equal-to   constraint, augmented by disjoint generalized upper bound constraints. A set of valid inequalities, called αα-cover inequalities, is characterized and dominance relationships among them are established. Both sequential and sequence-independent lifting procedures are presented to tighten an αα-cover inequality that is not facet defining. Computational results aimed at evaluating the strength of the non-dominated, sequentially, and sequence-independent lifted αα-cover inequalities are provided.