Global Optimization and Multi Knapsack : a Percolation Algorithm

Abstract : Since the standard multi knapsack problem $\max\spc \dprodc{x} \mbox{ s.t. } Ax \leq b,x\in {0,1}^n$, may be rewritten as a reverse convex problem, we present a global optimization approach. It is known from solving high dimensional nonconvex problems that pure cutting plane methods may fail and Branch&Bound is impractical, due to a large duality gap. On the other hand, a sufficient optimality condition-based strategy does not help much because it requires generating all level set points, an intractable problem. Therefore, we propose to combine both a cutting plane method and a sufficient optimality condition together with a random generation of level set points where the number of points is limited by a tabu list to prevent re-examination of the same level set area. Experiments show that we end up with a small duality gap permitting a subsequent Branch&Bound for reasonable sized instances.
Type de document :
[Research Report] RR-3912, INRIA. 2000
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:46:45
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:20:30



  • HAL Id : inria-00072741, version 1



Dominique Fortin, Ider Tsevendorj. Global Optimization and Multi Knapsack : a Percolation Algorithm. [Research Report] RR-3912, INRIA. 2000. 〈inria-00072741〉



Consultations de la notice


Téléchargements de fichiers