Global Optimization and Multi Knapsack : a Percolation Algorithm - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2000

Global Optimization and Multi Knapsack : a Percolation Algorithm


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.
Fichier principal
Vignette du fichier
RR-3912.pdf (308 Ko) Télécharger le fichier

Dates and versions

inria-00072741 , version 1 (24-05-2006)


  • 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⟩
143 View
191 Download


Gmail Facebook Twitter LinkedIn More