A surrogate relaxation based algorithm for a general quadratic multi- dimensional knapsack problem. (English) Zbl 0654.90058
An algorithm for a quadratic multidimensional knapsack problem is described in the paper. It is based on surrogate relaxation and new efficient procedures for finding surrogate multipliers and a good lower bound. Enumeration criteria are developed.
Reviewer: J.Mitev
References:
| [1] | Bazaraa, S. M.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (1979), Wiley: Wiley New York · Zbl 0476.90035 |
| [2] | Glover, F., Surrogate constraints, Operations Research, 16, 741-749 (1968) · Zbl 0165.22602 |
| [3] | Greenberg, H.; Hegerich, R., A branch and search algorithm for the knapsack problem, Management Science, 16, 327-332 (1970) · Zbl 0191.48401 |
| [4] | Loulou, R.; Michaelides, E., New greedy-like heuristics for the multi-dimensional 0-1 knapsack problem, Operations Researvh, 27, 1101-1114 (1979) · Zbl 0442.90058 |
| [5] | Markowitz, H. M., Portfolio Selection: Efficient Diversification of Investments (1959), Wiley: Wiley New York |
| [6] | Mathur, K.; Salkin, H. M.; Morito, S., A branch and search algorithm for a class of nonlinear knapsack problem, Operations Research Letters, 2, 4, 155-160 (1983) · Zbl 0526.90066 |
| [7] | K. Mathur, M. Djerdjour and H.M. Salkin, “A surrogate relaxation based branch and search algorithm for General Quadratic Multi-dimensional Knapsack Problem”, Technical Memorandum, Department of Operations Research, Case Western Reserve University, Cleveland, Ohio 44106.; K. Mathur, M. Djerdjour and H.M. Salkin, “A surrogate relaxation based branch and search algorithm for General Quadratic Multi-dimensional Knapsack Problem”, Technical Memorandum, Department of Operations Research, Case Western Reserve University, Cleveland, Ohio 44106. · Zbl 0654.90058 |
| [8] | Ravindran, A.; Klee, H. K., Computer experiments on quadratic programming algorithms, European Journal of Operational Research, 8, 166-174 (1981) · Zbl 0464.90064 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
