Exact methods for the knapsack problem and its generalizations |
| |
| Affiliation: | 1. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, Pisa 56127, Italy;2. DEI “Guglielmo Marconi”, Università di Bologna, Viale Risorgimento 2, Bologna 40136, Italy;1. IE University, Maria de Molina 31B, Madrid 28006, Spain;2. Institute of Information Systems, University of Hamburg, Von-Melle-Park 5, Hamburg D-20146, Germany;3. Escuela de Ingenierá Industrial, Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile |
| |
| Abstract: | A unified approach and a summary of the most important results concerned with exact methods for solving the (binary) knapsack problem and its generalizations are given. We stress the importance of dual methods for solving linear programming relaxations of the considered problems. Two ways of generalization of the knapsack problem are described. If the special ordered sets are added, then the multiple-choice knapsack problem is obtained. If the constraints have the nested structure, then we get the nested knapsack problem. Also the multiple-choice nested knapsack problem is discussed. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
