A Cutting Plane Based Algorithm for the Multiple Knapsack Problem.
Please always quote using this URN: urn:nbn:de:0297-zib-1031
- In this paper we describe a cutting plane based algorithm for the multiple knapsack problem. We use our algorithm to solve some practical problem instances arising in the layout of electronic circuits and in the design of main frame computers, and we report on our computational experience. This includes a discussion and evaluation of separation algorithms, an LP-based primal heuristic and some implementation details. The paper is based on the polyhedral theory for the multiple knapsack polytope developed in our companion paper SC 93-04 and meant to turn this theory into an algorithmic tool for the solution of practical problems.
Download full text files
Additional Services
| Author: | Robert Weismantel, Carlos E. Ferreira, Alexander Martin |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1993/03/11 |
| Series (Serial Number): | ZIB-Report (SC-93-07) |
| ZIB-Reportnumber: | SC-93-07 |
| Published in: | SC 93-07 and SC 93-04 appeared under the title: Solving Multiple Knapsack Problems by Cutting Planes in: SIAM J. Optimization 6 (1996) pp. 858-877 |
