ECCO 2024
Abstract Submission

79. A 3-space dynamic programming heuristic journey for the cubic knapsack problem

Invited abstract in session TD-1: Data structures, stream Data structures.

Thursday, 14:30 - 16:00
Room: L226

Authors (first author is the speaker)

1. Franklin Djeumou Fomeni
AOTI, University of Quebec in Montreal
2. Ibrahim Dan Dije
AOTI, UQAM
3. Leandro Coelho
Operations and Decision Systems, Université Laval

Abstract

The 0-1 cubic knapsack problem (CKP) is a combinatorial optimization problem, which can be seen as a generalization of both the 0-1 quadratic knapsack problem (QKP) and the linear knapsack problem (KP). This problem is by definition strongly NP-hard. Its mathematical formulation has a cubic objective function of binary decision variables and one single linear knapsack constraint. Some applications of the CKP include the satisfiability problem Max 3-SAT, facility location problem, network alignment problem as well as screening and treating sexually transmitted diseases. Unlike its quadratic and linear counterparts, the CKP has not received much attention in the literature. Only one research article can, so far, be found in the literature proposing solution methods for the CKP. Their work presents a greedy heuristic algorithm, which provides an initial solution for a commercial solver that uses a linearized formulation of CKP. Results are reported for CKP instances with up to 60 decision variables.


In our work, we propose a deterministic heuristic solution approach for the CKP based on dynamic programming with the particularity of implementing it through a journey in three spaces. Namely, the space of linear, quadratic as well as of cubic variables. Indeed, a well known approach for linearizing 0-1 polynomial optimization problems is to introduce new binary decision variables in order to replace the individual monomials and to use McCormick-like inequalities to avoid the nonlinearity in the constraints set. The newly introduced decision variables are often referred to as the lifted-space variables. The space of lifted variables has widely been explored and studied for the derivation of cutting planes to strengthen the linear relaxation of the original 0-1 polynomial optimization problem. In this presentation, we aim to show that the space of lifted variables can also be explored to derive efficient heuristic methods for such problems using dynamic programming. We particularly study the case of the cubic knapsack problem. Our algorithm runs in O(n^4c) times, with n and c being the number of items and knapsack capacity, respectively. The computational results show that the algorithm can yield solutions within 0.01% of optimality. Moreover, some comparison with an existing heuristic from the literature shows that our algorithm can dominate in terms of the quality of the solution obtained.

Keywords

Status: accepted

Back to the list of papers