Exact methods for the knapsack problem and its generalizations (Q1083032)

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.