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.