A Concise Characterization of Strong Knapsack Facets

For the integer knapsack problem, the 1/k-facets with k dividing 6 or 8 were shown to be very strong and efficiently separated (Chopra et al., 2015; Shim et al., 2017). We give a concise characterization of the 1/k-facets for each k dividing 6, 8 in terms of a concise description of the coefficients. This allows these inequalities to be separated efficiently. We develop a reduced linear programming formulation to speed up identification of the facets hit during the shooting experiment, and confirm the strength of the 1/k-facets with k dividing 6 or 8 in higher dimensional problems.