zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Improved convergent heuristics for the 0-1 multidimensional knapsack problem. (English) Zbl 1215.90045
Summary: At the end of the 1970s, A. L. Soyster, B. Lev and W. Slivka [Eur. J. Oper. Res. 2, 195–201 (1978; Zbl 0381.90076)] 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 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.
MSC:
90C27Combinatorial optimization
90C09Boolean programming
90C59Approximation methods and heuristics
Keywords:
relaxation
References:
[1]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. · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9
[2]Balas, E., & Jeroslow, R. (1972). Canonical cuts on the unit hypercube. SIAM Journal on Applied Mathematics, 23, 61–69. · Zbl 0237.52004 · doi:10.1137/0123007
[3]Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072.
[4]Danna, E., Rothberg, E., & Le Pape, C. (2005). Exploring relaxations induced neighborhoods to improve MIP solutions. Mathematical Programming, 102, 71–90. · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7
[5]Fischetti, M., & Lodi, A. (2003). Local Branching. Mathematical Programming, 98, 23–47. · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[6]Fréville, A. (2004). The multidimensional 0-1 knapsack problem: an overview. European Journal of Operational Research, 155, 1–21. · Zbl 1045.90050 · doi:10.1016/S0377-2217(03)00274-1
[7]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.). · Zbl 1091.90042 · doi:10.1007/s10479-005-3448-8
[8]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.
[9]Fréville, A., & Plateau, G. (1994). An efficient preprocessing procedure for the multidimensional knapsack problem. Discrete Applied Mathematics, 49, 189–212. · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[10]Glover, F. (1965). A multiphase-dual algorithm for the zero-one integer programming problem. Operations Research, 13, 879–919. · Zbl 0163.41301 · doi:10.1287/opre.13.6.879
[11]Glover, F. (1975). Surrogate constraints duality in mathematical programming. Operations Research, 23, 434–451. · Zbl 0314.90093 · doi:10.1287/opre.23.3.434
[12]Glover, F. (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences, 8, 156–166. · doi:10.1111/j.1540-5915.1977.tb01074.x
[13]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.
[14]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.
[15]Glover, F., & Laguna, M. (1997). Tabu search, (pp. 1–412). Boston: Kluwer.
[16]Guignard, M., & Spielberg, K. (2003). Double contraction, double probing, short starts and BB-probing cuts for mixed (0,1) programming. Technical Report, Wharton School.
[17]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. · Zbl 0991.90089 · doi:10.1016/S0377-2217(97)00296-8
[18]Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449–467. · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[19]Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems (pp. 1–572). Berlin: Springer.
[20]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.
[21]Martello, S., & Toth, P. (1990). Knapsack problems: algorithms and computer implementations (pp. 1–308). New York: Wiley.
[22]Nemhauser, G. L., & Wolsey, L. A. (1999). Integer and combinatorial optimization (pp. 1–784). New York: Willey.
[23]Pisinger, D. (1995). An expanding-core algorithm for the exact 0-1 knapsack problem. European Journal of Operational Research, 87, 175–187. · Zbl 0914.90199 · doi:10.1016/0377-2217(94)00013-3
[24]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.
[25]Rardin, R., & Karwan, M. H. (1984). Surrogate dual multiplier search procedures in integer programming. Operations Research, 32, 52–69. · Zbl 0538.90060 · doi:10.1287/opre.32.1.52
[26]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).
[27]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. · Zbl 0381.90076 · doi:10.1016/0377-2217(78)90093-0
[28]Spielberg, K., & Guignard, M. (2000). A sequential (quasi) hot start method for BB (0,1) mixed integer programming. Mathematical Programming Symposium, Atlanta.
[29]Vasquez, M., & Hao, J. K. (2001). Une approche hybride pour le sac à dos multidimensionnel en variables 0-1. RAIRO Operations Research, 35, 415–438. · Zbl 1015.90056 · doi:10.1051/ro:2001123
[30]Vasquez, M., & Vimont, Y. (2005). Improved results on the 0-1 multidimensional knapsack problem. European Journal of Operational Research, 165, 70–81. · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[31]Wilbaut, C., & Hanafi, S. (2009). New convergent heuristics for 0-1 mixed integer programming. European Journal of Operational Research, 195, 62–74. · Zbl 1161.90448 · doi:10.1016/j.ejor.2008.01.044
[32]Wilbaut, C., Hanafi, S., Fréville, A., & Balev, S. (2006). Tabu search: global intensification using dynamic programming. Control and Cybernetic, 35, 579–598.