A Note on the Max-Min 0-1 Knapsack Problem |
| |
Authors: | Hiroshi Iida |
| |
Institution: | (1) Dept. of Information and Management Science, Otaru University of Commerce, 5-21 Midori 3-Chome Otaru, Hokkaido, 047-8501, Japan |
| |
Abstract: | In this paper we propose new lower and upper bounds for the max-min 0-1 knapsack problem, employing a mixture of two relaxations. In addition, in order to expose whether the bounds are practical or not, we implement a method incorporating the bounds to achieve an optimal solution of the problem. |
| |
Keywords: | knapsack problem surrogate relaxation linear programming relaxation branch-and-bound |
本文献已被 SpringerLink 等数据库收录! |
|