Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering

The 0-1 cubic knapsack problem (CKP), a generalization of the classical 0-1 quadratic knapsack problem, is an extremely challenging NP-hard combinatorial optimization problem. An effective exact solution strategy for the CKP is to reformulate the nonlinear problem into an equivalent linear form that can then be solved using a standard mixed-integer programming solver. We consider a classical linearization method and propose a variant of a more recent technique for linearizing 0-1 cubic programs applied to the CKP. Using a variable reordering strategy, we show how to improve the strength of the linear programming relaxation of our proposed reformulation, which ultimately leads to reduced overall solution times. In addition, we develop a simple heuristic method for obtaining good-quality CKP solutions that can be used to provide a warm start to the solver. Computational tests demonstrate the effectiveness of both our variable reordering strategy and heuristic method.