Exact methods for the knapsack problem and its generalizations (Q1083032)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exact methods for the knapsack problem and its generalizations |
scientific article |
Statements
Exact methods for the knapsack problem and its generalizations (English)
0 references
1987
0 references
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.
0 references
binary knapsack problem
0 references
Lagrangean relaxation
0 references
reduction
0 references
branch-and- bound
0 references
exact methods
0 references
dual methods
0 references
linear programming relaxations
0 references
multiple-choice knapsack
0 references
nested knapsack
0 references
