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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R. K., Ergun, O., Orlin, J. B., & Punnen, A. P. (2002). Survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123, 75–102.
Balas, E., & Jeroslow, R. (1972). Canonical cuts on the unit hypercube. SIAM Journal on Applied Mathematics, 23, 61–69.
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072.
Danna, E., Rothberg, E., & Le Pape, C. (2005). Exploring relaxations induced neighborhoods to improve MIP solutions. Mathematical Programming, 102, 71–90.
Fischetti, M., & Lodi, A. (2003). Local Branching. Mathematical Programming, 98, 23–47.
Fréville, A. (2004). The multidimensional 0-1 knapsack problem: an overview. European Journal of Operational Research, 155, 1–21.
Fréville, A., & Hanafi, S. (2005). The multidimensional 0-1 knapsack problem – Bounds and computational aspects. Annals of Operations Research, 139, 195–227. M. Guignard and K. Spielberg (Eds.).
Fréville, A., & Plateau, G. (1993). Sac-à-dos multidimensionnel en variables 0-1: encadrement de la somme des variables à l’optimum. RAIRO Operations Research, 27, 169–187.
Fréville, A., & Plateau, G. (1994). An efficient preprocessing procedure for the multidimensional knapsack problem. Discrete Applied Mathematics, 49, 189–212.
Glover, F. (1965). A multiphase-dual algorithm for the zero-one integer programming problem. Operations Research, 13, 879–919.
Glover, F. (1975). Surrogate constraints duality in mathematical programming. Operations Research, 23, 434–451.
Glover, F. (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences, 8, 156–166.
Glover, F. (2005). Adaptive memory projection methods for integer programming. In C. Rego & B. Alidaee (Eds.), Metaheuristic optimization via memory and evolution (pp. 425–440). Boston: Kluwer.
Glover, F., & Kochenberger, G. (1996). Critical event tabu search for multidimensional knapsack problems. In I. H. Osman & J. P. Kelly (Eds.), Meta heuristics: theory and applications (pp. 407–427). Boston: Kluwer.
Glover, F., & Laguna, M. (1997). Tabu search, (pp. 1–412). Boston: Kluwer.
Guignard, M., & Spielberg, K. (2003). Double contraction, double probing, short starts and BB-probing cuts for mixed (0,1) programming. Technical Report, Wharton School.
Hanafi, S., & Fréville, A. (1998). An efficient tabu search approach for the 0-1 multidimensional knapsack problem. European Journal of Operational Research, 106, 659–675.
Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449–467.
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems (pp. 1–572). Berlin: Springer.
Lichtenberger, D. (2005). An extended local branching framework and its application to the multidimensional knapsack problem. Master Thesis, Vienna University of Technology, Institute of Computer Graphics and Algorithms.
Martello, S., & Toth, P. (1990). Knapsack problems: algorithms and computer implementations (pp. 1–308). New York: Wiley.
Nemhauser, G. L., & Wolsey, L. A. (1999). Integer and combinatorial optimization (pp. 1–784). New York: Willey.
Pisinger, D. (1995). An expanding-core algorithm for the exact 0-1 knapsack problem. European Journal of Operational Research, 87, 175–187.
Puchinger, J., Raidl, G., & Pferschy, U. (2006). The core concept for the multidimensional knapsack problem. In Proceedings of evolutionary computation in combinatorial optimization, 6th European conference (pp. 195–208). EvoCOP 2006.
Rardin, R., & Karwan, M. H. (1984). Surrogate dual multiplier search procedures in integer programming. Operations Research, 32, 52–69.
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In The 4th international conference on principles and practice of constraint programming. Lecture Notes in Computer Science, vol. 1520 (pp. 417–431).
Soyster, A. L., Lev, B., & Slivka, W. (1978). Zero-one programming with many variables and few constraints. European Journal of Operational Research, 2, 195–201.
Spielberg, K., & Guignard, M. (2000). A sequential (quasi) hot start method for BB (0,1) mixed integer programming. Mathematical Programming Symposium, Atlanta.
Vasquez, M., & Hao, J. K. (2001). Une approche hybride pour le sac à dos multidimensionnel en variables 0-1. RAIRO Operations Research, 35, 415–438.
Vasquez, M., & Vimont, Y. (2005). Improved results on the 0-1 multidimensional knapsack problem. European Journal of Operational Research, 165, 70–81.
Wilbaut, C., & Hanafi, S. (2009). New convergent heuristics for 0-1 mixed integer programming. European Journal of Operational Research, 195, 62–74.
Wilbaut, C., Hanafi, S., Fréville, A., & Balev, S. (2006). Tabu search: global intensification using dynamic programming. Control and Cybernetic, 35, 579–598.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hanafi, S., Wilbaut, C. Improved convergent heuristics for the 0-1 multidimensional knapsack problem. Ann Oper Res 183, 125–142 (2011). https://doi.org/10.1007/s10479-009-0546-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-009-0546-z