36documents trouvés
Heuristics for the 0-1 multidimensional knapsack problem
V.BOYER, M.ELKIHEL, D.EL BAZ
CDA
Revue Scientifique : European Journal of Operational Research, Vol.199, N°3, pp.658-664, Décembre 2009 , N° 06539
Diffusable
Plus d'informations
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;
A dynamic programming method with dominance technique for the knapsack sharing problem
V.BOYER, D.EL BAZ, M.ELKIHEL
CDA
Manifestation avec acte : 39th International Conference on Computers & Industrial Engineering (CIE39), Troyes (France), 6-8 Juillet 2009, pp.348-353 , N° 09017
Diffusable
Plus d'informations
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;
Improved time and space complexity for Kianfar's inequality rotation algorithm
D.EL BAZ, M.ELKIHEL, L.GELY, G.PLATEAU
CDA, LIPN, IMB
Revue Scientifique : European Journal of Industrial Engineering, Vol.3, N°1, pp.90-98, Janvier 2009 , N° 06834
Diffusable
Plus d'informations
Mots-Clés / Keywords
Knapsack problem; Constraint rotation techniques; Lifting; Dynamic programming;
An exact cooperative method for solving the 0-1 multidimensional knapsack problem
V.BOYER, D.EL BAZ, M.ELKIHEL
CDA
Manifestation avec acte : 7ème Conférence Internationale de Modélisation et Simulation (MOSIM'08), Paris (France), 31 Mars - 2 Avril 2008, 7p. , N° 08392
Diffusable
Plus d'informations
Mots-Clés / Keywords
Multidimensional knapsack problem; Dynamic programming; Branch-and-Bound method; Surrogate relaxation; Cooperative methods;
Générateur d'instances difficiles pour le sac à dos multi-dimensionnels à variables 0-1
V.BOYER, D.EL BAZ, M.ELKIHEL, J.B.LASSERRE
CDA, MAC
Manifestation avec acte : 9ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'08), Clermont Ferrand (France), 25-27 Février 2008, pp.33-44 , N° 08078
Diffusable
Plus d'informations
Mots-Clés / Keywords
Problème du sac à dos; Relaxation Lagrangienne; Transformée en Z;
A cooperative method for the 0-1 multidimensional knapsack problem
V.BOYER, M.ELKIHEL, D.EL BAZ
MAC, EN-INSTANCE
Manifestation avec acte : 8ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'2007), Grenoble (France), 20-23 Février 2007 (Résumé) , N° 06606
Diffusable
109261Improved time and space complexity for Kianfar's inequality rotation algorithm
D.EL BAZ, M.ELKIHEL, L.GELY, G.PLATEAU
CDA, LIPN, IMB
Manifestation sans acte : Workshop Métaheuristiques : de la théorie aux applications (META'2006), Hammamet (Tunisie), 2-4 Novembre 2006, 2p. , N° 06834
Diffusable
Plus d'informations
Mots-Clés / Keywords
Knapsack problem; Constraint rotation techniques; Lifting; Dynamic programming;
Load balancing in a parallel dynamic programming multi-method applied to the 0-1 knapsack problem
M.ELKIHEL, D.EL BAZ
MAC, EN-INSTANCE
Manifestation avec acte : 14th Euromicro Conference on Parallel, Distributed and Network-based Processing (PDP'2006), Montbéliard-Sochaux (France), 15-17 Février 2006, pp.127-132 , N° 04554
Diffusable
105857Efficient heuristic for the 0-1 multidimensional knapsack problem
V.BOYER, M.ELKIHEL, D.EL BAZ
RST, MAC
Manifestation avec acte : 7ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'06), Lille (France), 6-8 Février 2006, pp.95-106 , N° 05533
Diffusable
105859A new heuristic for the multidimensional knapsack problem
M.ELKIHEL, D.EL BAZ, V.BOYER
MAC, RST
Manifestations avec acte à diffusion limitée : 2nd International Workshop on Combinatorial Scientific Computing (CSC'05), Toulouse (France), 21-23 Juin 2005, 2p. (Résumé) , N° 05157
Diffusable
104628