Richard Forrester is a professor of Mathematics and Data Analytics at Dickinson College.

For more information on the published version, visit Springer's Website. https://link.springer.com/article/10.1007/s10878-021-00840-z To access a view-only full text published version of this article click here: https://rdcu.be/cGmJk Online access to this article has been shared by the author(s) via Springer Nature SharedIt content-sharing initiative.

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.

Forrester, Richard J., and Lucas A. Waddell. Strengthening a Linear Reformulation of the 0-1 Cubic Knapsack Problem via Variable Reordering. Journal of Combinatorial Optimization 44 (2022): 498–517. https://link.springer.com/article/10.1007/s10878-021-00840-z

Citation