Solving Multiple Knapsack Problems by Cutting Planes

Journal article

Publication Details

Author(s): E. Ferreira C, Martin A, Weismantel R
Journal: SIAM Journal on Optimization
Publication year: 1996
Volume: 6
Pages range: 858 - 877
ISSN: 1052-6234
Language: English


In this paper we consider the multiple knapsack problem, which is defined as follows: given a set N of items with weights $f_i ,i \in N$, a set M of knapsacks with capacities $F_k ,k \in M$, and a profit function $c_{ik} ,i \in N,k \in M$, find an assignment of a subset of the set of items to the set of knapsacks that yields minimum cost. We consider the multiple knapsack problem from a polyhedral point of view. The inequalities that we describe here serve as the theoretical basis for a cutting plane algorithm. We present some of the implementation details of this algorithm, including a discussion and evaluation of different separation and primal heuristics. Our algorithm is applied to practical problem instances arising in the design of main frame computers, in the layout of electronic circuits, and in sugar cane alcohol production.

Read More:

FAU Authors / FAU Editors

Martin, Alexander Prof. Dr.
Economics - Discrete Optimization - Mathematics (EDOM)

External institutions with authors

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)
University of São Paulo / Universidade de São Paulo (USP)

How to cite

E. Ferreira, C., Martin, A., & Weismantel, R. (1996). Solving Multiple Knapsack Problems by Cutting Planes. SIAM Journal on Optimization, 6, 858 - 877.

E. Ferreira, Carlos, Alexander Martin, and Robert Weismantel. "Solving Multiple Knapsack Problems by Cutting Planes." SIAM Journal on Optimization 6 (1996): 858 - 877.


Last updated on 2018-08-08 at 02:10