Skip to Main content Skip to Navigation
Journal articles

Improved convergent heuristics for the 0-1 multidimensional knapsack problem

Abstract : At the end of the seventies, Soyster et al. (Eur. J. Oper. Res. 2:195-201, 1978) proposed a convergent algorithm that solves a series of small sub-problems generated by exploiting information obtained through a series of linear programming relaxations. This process is suitable for the 0-1 mixed integer programming problems when the number of constraints is relatively smaller when compared to the number of variables. In this paper, we first revisit this algorithm, once again presenting it and some of its properties, including new proofs of finite convergence. This algorithm can, in practice, be used as a heuristic if the number of iterations is limited. We propose some improvements in which dominance properties are emphasized in order to reduce the number of sub problems to be solved optimally. We also add constraints to these sub-problems to speed up the process and integrate adaptive memory. Our results show the efficiency of the proposed improvements for the 0-1 multidimensional knapsack problem.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03723743
Contributor : Christophe Wilbaut Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 10:41:23 AM
Last modification on : Thursday, July 21, 2022 - 3:54:55 AM

File

Hanafi et Wilbaut - 2011 - Imp...
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Saïd Hanafi, Christophe Wilbaut. Improved convergent heuristics for the 0-1 multidimensional knapsack problem. Annals of Operations Research, Springer Verlag, 2009, 183, pp.125 - 142. ⟨10.1007/s10479-009-0546-z⟩. ⟨hal-03723743⟩

Share

Metrics

Record views

1

Files downloads

2