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)
A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem. (English) Zbl 1244.90163
Summary: We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data.
MSC:
90C09Boolean programming
90C27Combinatorial optimization
90C10Integer programming
90C59Approximation methods and heuristics
Software:
MOTGA
References:
[1]Alves, M. J.; Almeida, M.: MOTGA: A multiobjective tchebycheff based genetic algorithm for the multidimensional knapsack problem, Computers & operations research 34, No. 11, 3458-3470 (2007) · Zbl 1127.90059 · doi:10.1016/j.cor.2006.02.008
[2]Bagchi, A.; Bhattacharyya, N.; Chakravarti, N.: LP relaxation of the two dimensional knapsack problem with box and GUB constraints, European journal of operational research 89, No. 3, 609-617 (1996) · Zbl 0915.90211 · doi:10.1016/0377-2217(94)00285-1
[3]Balev, S.; Yanev, N.; Fréville, A.; Andonov, R.: A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem, European journal of operational research 186, No. 1, 63-76 (2008) · Zbl 1138.90015 · doi:10.1016/j.ejor.2006.02.058
[4]Beasley, J. E.: A Lagrangean heuristic for set-covering problems, Naval research logistics 37, No. 1, 151-164 (1990) · Zbl 0684.90063 · doi:10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2
[5]Beasley, J. E.: OR-library: distributing test problems by electronic mail, Journal of the operational research society 41, No. 11, 1069-1072 (1990)
[6]Beasley, J. E.: Obtaining test problems via Internet, Journal of global optimization 8, No. 4, 429-433 (1996) · Zbl 0848.90126 · doi:10.1007/BF02404002
[7]Bektas, T.; Oguz, O.: On separating cover inequalities for the multidimensional knapsack problem, Computers & operations research 34, No. 6, 1771-1776 (2007) · Zbl 1159.90460 · doi:10.1016/j.cor.2005.05.032
[8]Bellmore, M.; Greenberg, H. J.; Jarvis, J. J.: Generalized penalty function concepts in mathematical optimization, Operations research 18, No. 2, 229-252 (1970) · Zbl 0279.90034 · doi:10.1287/opre.18.2.229
[9]Boussier, S.; Vasquez, M.; Vimont, Y.; Hanafi, S.; Michelon, P.: A multi-level search strategy for the 0-1 multidimensional knapsack problem, Discrete applied mathematics 158, No. 2, 97-109 (2010) · Zbl 1185.90170 · doi:10.1016/j.dam.2009.08.007
[10]Boyer, V.; Elkihel, M.; Baz, D. E.: Heuristics for the 0-1 multidimensional knapsack problem, European journal of operational research 199, No. 3, 658-664 (2009) · Zbl 1176.90657 · doi:10.1016/j.ejor.2007.06.068
[11]Brooks, R.; Geoffrion, A.: Finding everett’s Lagrange multipliers by linear programming, Operations research 14, No. 6, 1149-1153 (1966)
[12]Campello, R. E.; Maculan, N.: An O(n3) worst case bounded special LP knapsack (0-1) with two constraints. RAIRO, Recherche opérationnelle 22, No. 1, 27-32 (1988) · Zbl 0662.90052
[13]Caprara, A.; Kellerer, H.; Pferschy, U.; Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints, European journal of operational research 123, No. 2, 333-345 (2000) · Zbl 0961.90131 · doi:10.1016/S0377-2217(99)00261-1
[14]Chang, Y.-J., Wah, B.W., 1995. Lagrangian techniques for solving a class of zero-one integer linear programs. In: Proceedings of the 19th International Computer Software and Applications Conference, pp. 156 – 161.
[15]Chekuri, C., Khanna, S., 2000. A PTAS for the multiple knapsack problem. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 213 – 222. · Zbl 0952.90020
[16]Chu, P. C.; Beasley, J. E.: A genetic algorithm for the multidimensional knapsack problem, Journal of heuristics 4, No. 1, 63-86 (1998) · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[17]Cotta, C.; Troya, J. M.: A hybrid genetic algorithm for the 0-1 multiple knapsack problem, Artificial neural networks and genetic algorithms 3, 251-255 (1997)
[18]Crama, Y.; Mazzola, J. B.: On the strength of relaxations of multidimensional knapsack problems, Infor 32, No. 4, 219-225 (1994) · Zbl 0823.90093
[19]Iii, H. Everett: Generalized Lagrange multiplier method for solving problems of optimum allocation of resources, Operations research 11, No. 3, 399-417 (1963) · Zbl 0113.14202 · doi:10.1287/opre.11.3.399
[20]Fisher, M. L.: The Lagrangian relaxation method for solving integer programming problems, Management science 27, No. 1, 1-18 (1981) · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[21]Fleszar, K.; Hindi, K. S.: Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem, Computers & operations research 36, No. 5, 1602-1607 (2009)
[22]Fréville, A.: The multidimensional 0-1 knapsack problem: an overview, European journal of operational research 155, No. 1, 1-21 (2004) · Zbl 1045.90050 · doi:10.1016/S0377-2217(03)00274-1
[23]Fréville, A.; Hanafi, S.: The multidimensional 0-1 knapsack problem – bounds and computational aspects, Annals of operations research 139, No. 1, 195-227 (2005) · Zbl 1091.90042 · doi:10.1007/s10479-005-3448-8
[24]Fréville, A., Lorena, L.A.N., Plateau, G., 1990. Efficient subgradient algorithms for the 0-1 multiknapsack Lagrangean and surrogate duals. Tech. Rep. Research Report LIPN, University of Paris 13.
[25]Fréville, A.; Plateau, G.: An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem, European journal of operational research 68, No. 3, 413-421 (1993) · Zbl 0782.90069 · doi:10.1016/0377-2217(93)90197-U
[26]Fréville, A.; Plateau, G.: An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Discrete applied mathematics 49, No. 1 – 3, 189-212 (1994) · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[27]Fréville, A.; Plateau, G.: The 0-1 bidimensional knapsack problem: toward an efficient high-level primitive tool, Journal of heuristics 2, No. 2, 147-167 (1996) · Zbl 0870.90084 · doi:10.1007/BF00247210
[28]Frieze, A. M.; Clarke, M. R. B.: Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European journal of operational research 15, No. 1, 100-109 (1984) · Zbl 0532.90075 · doi:10.1016/0377-2217(84)90053-5
[29]Garey, M.; Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness, (1979)
[30]Gavish, B.: On obtaining the ’best’ multipliers for a Lagrangean relaxation for integer programming, Computers & operations research 5, No. 1, 55-71 (1978)
[31]Gavish, B.; Pirkul, H.: Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Mathematical programming 31, No. 1, 78-105 (1985) · Zbl 0571.90065 · doi:10.1007/BF02591863
[32]Geoffrion, A. M.: Lagrangian relaxation for integer programming, Mathematical programming study 2, 82-114 (1974) · Zbl 0395.90056
[33]Glover, F.: A multiphase-dual algorithm for the zero-one integer programming problem, Operations research 13, No. 6, 879-919 (1965) · Zbl 0163.41301 · doi:10.1287/opre.13.6.879
[34]Glover, F.: Surrogate constraints, Operations research 16, No. 4, 741-749 (1968) · Zbl 0165.22602 · doi:10.1287/opre.16.4.741
[35]Glover, F.: Tabu search – part I, ORSA journal on computing 1, No. 3, 190-206 (1989) · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[36]Glover, F.; Kochenberger, G.: Critical event tabu search for multidimensional knapsack problems, , 407-427 (1996) · Zbl 0877.90055
[37]Goldberg, D.: Genetic algorithms in search, optimization, and machine learning, (1989) · Zbl 0721.68056
[38]Gould, F. J.: Extensions of Lagrange multipliers in nonlinear programming, SIAM journal on applied mathematics 17, No. 6, 1280-1297 (1969) · Zbl 0191.49001 · doi:10.1137/0117120
[39]Greenberg, H. J.; Pierskalla, W. P.: Surrogate mathematical programming, Operations research 18, No. 5, 924-939 (1970) · Zbl 0232.90059 · doi:10.1287/opre.18.5.924
[40]Hanafi, S.; Fréville, A.: An efficient tabu search approach for the 0-1 multidimensional knapsack problem, European journal of operational research 106, No. 2 – 3, 659-675 (1998) · Zbl 0991.90089 · doi:10.1016/S0377-2217(97)00296-8
[41]Hanafi, S.; Wilbaut, C.: Scatter search for the 0-1 multidimensional knapsack problem, Journal of mathematical modelling and algorithms 7, No. 2, 143-159 (2008) · Zbl 1140.68063 · doi:10.1007/s10852-008-9078-9
[42]Hanafi, S.; Wilbaut, C.: Improved convergent heuristic for the 0-1 multidimensional knapsack problem, Annals of operations research 183, No. 1, 125-142 (2011) · Zbl 1215.90045 · doi:10.1007/s10479-009-0546-z
[43]Hill, R. R.; Cho, Y. K.; Moore, J. T.: Problem reduction heuristic for the 0-1 multidimensional knapsack problem, Computers & operations research 39, No. 1, 19-26 (2012)
[44]Kaparis, K.; Letchford, A. N.: Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, European journal of operational research 186, No. 1, 91-103 (2008) · Zbl 1138.90016 · doi:10.1016/j.ejor.2007.01.032
[45]Karwan, M. H.; Rardin, R. L.: Some relationships between Lagrangian and surrogate duality in integer programming, Mathematical programming 17, No. 1, 320-334 (1979) · Zbl 0421.90056 · doi:10.1007/BF01588253
[46]Karwan, M. H.; Rardin, R. L.: Searchability of the composite and multiple surrogate dual functions, Operations research 28, No. 5, 1251-1257 (1980) · Zbl 0449.90068 · doi:10.1287/opre.28.5.1251
[47]Kellerer, H., Pferschy, U., 1998. A new fully polynomial approximation scheme for the knapsack problem. In: Proceedings of the First International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 123 – 134. · Zbl 0908.90190
[48]Kellerer, H.; Pferschy, U.; Pisinger, D.: Knapsack problems, (2004)
[49]Kong, M.; Tian, P.; Kao, Y.: A new ant colony optimization algorithm for the multidimensional knapsack problem, Computers & operations research 35, No. 8, 2672-2683 (2008) · Zbl 1169.90435 · doi:10.1016/j.cor.2006.12.029
[50]Lawler, E.L., 1977. Fast approximation algorithms for knapsack problems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 206 – 213.
[51]Li, V. C.: Tight oscillations tabu search for multidimensional knapsack problems with generalized upper bound constraints, Computers & operations research 32, No. 11, 2843-2852 (2005) · Zbl 1071.90051 · doi:10.1016/j.cor.2004.04.020
[52]Li, V. C.; Curry, G. L.: Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search, Computers & operations research 32, No. 4, 825-848 (2005) · Zbl 1071.90050 · doi:10.1016/j.cor.2003.08.021
[53]Løkketangen, A.; Glover, F.: Probabilistic move selection in tabu search for zero-one mixed integer programming problems, , 467-487 (1996) · Zbl 0877.90058
[54]Luenberger, D. G.: Optimization by vector space methods, (1969) · Zbl 0176.12701
[55]Magazine, M. J.; Oguz, O.: A heuristic algorithm for the multidimensional zero-one knapsack problem, European journal of operational research 16, No. 3, 319-326 (1984) · Zbl 0532.90070 · doi:10.1016/0377-2217(84)90286-8
[56]Martello, S.; Toth, P.: Knapsack problems: algorithms and computer implementations, (1990) · Zbl 0708.68002
[57]Martello, S.; Toth, P.: An exact algorithm for the two-constraint 0-1 knapsack problem, Operations research 51, No. 5, 826-835 (2003) · Zbl 1165.90575 · doi:10.1287/opre.51.5.826.16757
[58]Martin, R. K.: Large scale linear and integer optimization: A unified approach, (1999)
[59]Nemhauser, G. L.; Wolsey, L. A.: Integer and combinatorial optimization, (1999)
[60]Osorio, M. A.; Glover, F.; Hammer, P.: Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Annals of operations research 117, No. 1 – 4, 71-93 (2002) · Zbl 1028.90042 · doi:10.1023/A:1021513321301
[61]Pirkul, H.: A heuristic solution procedure for the multiconstraint 0-1 knapsack problem, Naval research logistics 34, No. 2, 161-172 (1987) · Zbl 0609.90092 · doi:10.1002/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A
[62]Raidl, G.R., 1998. An improved genetic algorithm for the multiconstrained 0-1 knapsack problem. In: Proceedings of the IEEE International Conference on Evolutionary Computation. pp. 207 – 211.
[63]Raidl, G.R., 1999. Weight-codings in a genetic algorithm for the multiconstraint knapsack problem. In: Proceedings of the Congress on Evolutionary Computation. vol. 1, pp. 596 – 603.
[64]Sahni, S.: Approximate algorithms for the 0/1 knapsack problem, Journal of the ACM 22, No. 1, 115-124 (1975)
[65]Schuurmans, D., Southey, F., Holte, R.C., 2001. The exponentiated subgradient algorithm for heuristic boolean programming. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence. vol. 1, pp. 334 – 341.
[66]Shapiro, J. F.: A survey of Lagrangian techniques for discrete optimization, Annals of discrete mathematics 5, 113-138 (1979) · Zbl 0411.90054
[67]Shih, W.: A branch and bound method for the multiconstraint zero-one knapsack problem, Journal of the operational research society 30, No. 4, 369-378 (1979) · Zbl 0411.90050 · doi:10.2307/3009639
[68]Thiel, J.; Voss, S.: Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms, Infor 32, No. 4, 226-242 (1994) · Zbl 0823.90092
[69]Thiongane, B.; Nagih, A.; Plateau, G.: Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem, Discrete applied mathematics 154, No. 15, 2200-2211 (2006) · Zbl 1111.90096 · doi:10.1016/j.dam.2005.04.013
[70]Vasquez, M., Hao, J.-K., 2001. A hybrid approach for the 0-1 multidimensional knapsack problem. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence. vol. 1, pp. 328 – 333.
[71]Vasquez, M.; Vimont, Y.: Improved results on the 0-1 multidimensional knapsack problem, European journal of operational research 165, No. 1, 70-81 (2005) · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[72]Vimont, Y.; Boussier, S.; Vasquez, M.: Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem, Journal of combinatorial optimization 15, No. 2, 165-178 (2008) · Zbl 1138.90014 · doi:10.1007/s10878-007-9074-4
[73]Wah, B. W.; Shang, Y.: A discrete Lagrangian-based global-search method for solving satisfiability problems, , 365-392 (1997) · Zbl 0891.68027
[74]Wah, B.W., Wu, Z., 1999. The theory of discrete Lagrange multipliers for nonlinear discrete optimization. In: Principles and Practice of Constraint Programming, pp. 28 – 42. · Zbl 0965.90051
[75]Weingartner, H. M.; Ness, D. N.: Methods for the solution of the multidimensional 0/1 knapsack problem, Operations research 15, No. 1, 83-103 (1967)
[76]Wilbaut, C.; Hanafi, S.: New convergent heuristics for 0-1 mixed integer programming, European journal of operational research 195, No. 1, 62-74 (2009) · Zbl 1161.90448 · doi:10.1016/j.ejor.2008.01.044
[77]Wilbaut, C.; Salhi, S.; Hanafi, S.: An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem, European journal of operational research 199, No. 2, 339-348 (2009) · Zbl 1176.90669 · doi:10.1016/j.ejor.2008.11.036
[78]Wolsey, L. A.: Integer programming, (1998) · Zbl 0930.90072
[79]Yoon, Y., Kim, Y.-H., Moon, B.-R., 2005. An evolutionary Lagrangian method for the 0/1 multiple knapsack problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 629 – 635.
[80]Yu, G., 1990. Algorithms for optimizing piecewise linear functions and for degree constrained minimum spanning tree problems. Ph.D. Thesis, University of Pennsylvania.