Retour au site du LAAS-CNRS

Abstract

Two heuristics for the 01 multidimensional knapsack problem (MKP) are presented. The first one uses surrogate relaxation, and the relaxed problem is solved via a modified dynamic-programming algorithm. The heuristics provides a feasible solution for (MKP). The second one combines a limited-branch-and-cut-procedure with the previous approach, and tries to improve the bound obtained by exploring some nodes that have been rejected by the modified dynamic-programming algorithm. Computational experiences show that our approaches give better results than the existing heuristics, and thus permit one to obtain a smaller gap between the solution provided and an optimal solution.

Mots-Clés / Keywords

Multidimensional knapsack problem; Dynamic programming; branch and cut; Surrogate relaxation; Heuristics;

Abstract

In this paper, we propose an original method to solve exactly the knapsack sharing problem (KSP) by using a dynamic programming with dominance technique. The original problem (KSP) is decomposed in a set of knapsack problems. Our method is tested on uncorrelated and correlated instances from the literature. Computational experiences show that our method is able to find an optimal solution of large instances within reasonable computing time.

Mots-Clés / Keywords

Max-min programming; Knapsack sharing problem; Dynamic programming; Combinatorial optimization;

Mots-Clés / Keywords

Multidimensional knapsack problem; Dynamic programming; Branch-and-Bound method; Surrogate relaxation; Cooperative methods;

Mots-Clés / Keywords

Problème du sac à dos; Relaxation Lagrangienne; Transformée en Z;

Résumé

Le problème du sac à dos à plusieurs contraintes est un problème classique de l'optimisation appartenant à la classe des problèmes NP-difficiles. On le retrouve notamment sous la forme de sous-problème de nombreux problèmes d'optimisation combinatoire. Les méthodes classiques de résolution exacte telles que la programmation dynamique ou le branch-and-bound ont été traitées abondamment dans la littérature. Elles présentent n´eanmoins des faiblesses si elles sont utilisées telles quelles, d'où l'idée de faire coopérer ces méthodes en tirant profit de leurs spécificités afin de proposer soit des méthodes heuristiques performantes, soit des méthodes exactes plus efficaces. Les approches heuristiques que nous proposons sont comparées à d'autres heuristiques de la littérature. Notre méthode coopérative est, quant à elle, comparée à un algorithme de branchand- bound. L'ensemble de ces tests numériques ont été menés pour diverses instances plus ou moins difficiles de la littérature ainsi que sur des instances engendrées aléatoirement. Enfin, nous proposons deux techniques pour engendrer des problèmes difficiles. Ces dernières sont basées sur des problèmes en contraintes égalités et sur l'analyse de la transformée en Z du sac à dos.

Abstract

The Multi-Knapsack Problem is a traditional problem of optimization belonging to the class of the NP-hard problems. This problem occurs in particular as a subproblem of many combinatorial optimization problems. Traditional methods, such as dynamic programming or branch-andbound, used for the exact solution have been treated abundantly in the literature. They have nevertheless weaknesses if they are used alone. The cooperative methods permit one to benefits from their specificities and to propose powerful heuristics or efficient exact methods. Heuristics approaches are proposed and compared with other heuristics from the literature. A cooperative method is compared with a branch-and-bound algorithm. Numerical tests were carried out on various difficult problems from the literature and on randomly generated problems. At last, we consider in particular two techniques in order to generate difficult problems. They are based on problems with equality constraints and the analysis of the Z transform of the knapsack problem.

Mots-Clés / Keywords

Optimisation combinatoire; Problème du sac à dos multidimensionnel; Méthodes coopératives; Heuristiques; Combinatorial optimization; Multi-knapsack problem; Cooperative methods; Heuristics;