We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have a number of interesting properties. First, they generalize the well-known (1,k)-configuration inequalities. Second, they are not aggregation cuts. Third, they cannot be generated as a rank-1 Chv{\'a}tal-Gomory cut from the inequality system consisting of the knapsack constraints and all their minimal covers. Finally, we provide conditions under which the inequalities are facets of the totally-ordered knapsack set.
Article
View Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets: Theory and Computation