Solving Multiple Knapsack Problems by Cutting Planes

E. Ferreira C, Martin A, Weismantel R (1996)

Publication Language: English

Publication Type: Journal article

Publication year: 1996

Journal

SIAM Journal on Optimization Society for Industrial and Applied Mathematics

Book Volume: 6

Pages Range: 858 - 877

Abstract

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: http://epubs.siam.org/doi/abs/10.1137/S1052623493254455

Authors with CRIS profile

Alexander Martin Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

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

How to cite

APA:

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

MLA:

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

BibTeX: Download