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.

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.

DOI

10.1007/s10878-021-00840-z

Full text currently unavailable.

COinS