| Popis: |
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. 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. |
Full Text from ScienceDirect