Title
Strengthening a Linear Reformulation of the 0-1 Cubic Knapsack Problem via Variable Reordering
Document Type
Article
Publication Date
1-21-2022
Department
Mathematics
Language
English
Publication Title
Journal of Combinatorial Optimization
Abstract
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.
DOI
10.1007/s10878-021-00840-z
Recommended Citation
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 (Article published online January 21, 2022). https://link.springer.com/article/10.1007/s10878-021-00840-z
Comments
For more information on the published version, visit Springer's Website.
To access a view-only full text published version of this article click here.
Online access to this article has been shared by the author(s) via Springer Nature SharedIt content-sharing initiative.