| Article ID: | iaor1989705 |
| Country: | Netherlands |
| Volume: | 8 |
| Issue: | 2 |
| Start Page Number: | 95 |
| End Page Number: | 100 |
| Publication Date: | Apr 1989 |
| Journal: | Operations Research Letters |
| Authors: | Karwan Mark H., Sarin Sasnjiv |
| Keywords: | knapsack problem |
The multiple choice knapsack problem is defined as a knapsack problem with additional mutually exclusive multiple choice constraints. The authors present an algorithm for solving the linear programming relaxation of the multiple choice knapsack problem. The method is based on systematically perturbing the right-hand side of the knapsack constraint and the application of a dual-simplex based strategy. Computational experience with the method is also presented.