This paper generates a new class of cuts for the multiple knapsack equality problem. By viewing the multiple knapsack equality problem as both a demand and a knapsack problem, lifted covers and anticovers can be compared. When their coefficients are equal, a lifted equality cut is created. An equality cut differs from a standard cut because every feasible integer point satisfies the equality. Thus, an equality cut is an improper cut as it defines the entire space. However, an equality cut can reduce the dimension of the linear relaxation space. A polynomial time algorithm is presented that finds lifted valid equalities. A small computational study generated millions of equality cuts in a branch and cut environment and reduced the solution time by an average of 15%.
展开▼
