We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational experiments on fixed charge transportation problems, a well-known class of NP-hard problems, which help improve their lower bounds by more than 9% on average. This helps save CPU time by around 77% to 94% when used in the absence of CPLEX-generated cuts, depending on the problem parameters. This also reduces the CPU time by around 28% to 16% when used in conjunction with CPLEX-generated cuts.
Article
View Facets of the knapsack polytope from non-minimal covers