28532 articles – 22057 Notices  [english version]

hal-00445839, version 1

A dynamic programming based procedure for the multidimensional 0-1 knapsack problem

Stefan Balev () 1, Nicola Yanev () 2, Arnaud Fréville, Rumen Andonov () 2

European Journal of Operational Research 186, 1 (2008) 63-76

Résumé : This paper presents a preprocessing procedure for the 0–1 multidimensional knapsack problem. First, a non-increasing sequence of upper bounds is generated by solving LP-relaxations. Then, a non-decreasing sequence of lower bounds is built using dynamic programming. The comparison of the two sequences allows either to prove that the best feasible solution obtained is optimal, or to fix a subset of variables to their optimal values. In addition, a heuristic solution is obtained. Computational experiments with a set of large-scale instances show the efficiency of our reduction scheme. Particularly, it is shown that our approach allows to reduce the CPU time of a leading commercial software.

  • 1 :  Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS)
  • Institut National des Sciences Appliquées (INSA) - Rouen – Université du Havre – Université de Rouen : EA4108
  • 2 :  SYMBIOSE (INRIA - IRISA)
  • CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
  • Domaine : Informatique/Recherche opérationnelle
 
  • hal-00445839, version 1
  • http://hal.archives-ouvertes.fr/hal-00445839
  • oai:hal.archives-ouvertes.fr:hal-00445839
  • Contributeur : Stefan Balev <>
  • Soumis le : Lundi 11 Janvier 2010, 14:33:27
  • Dernière modification le : Lundi 11 Janvier 2010, 14:33:27