Solving Multiple Knapsack Problems by Cutting Planes

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autorinnen und Autoren: E. Ferreira C, Martin A, Weismantel R
Zeitschrift: SIAM Journal on Optimization
Jahr der Veröffentlichung: 1996
Band: 6
Seitenbereich: 858 - 877
ISSN: 1052-6234
Sprache: Englisch


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-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

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


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.


Zuletzt aktualisiert 2019-21-07 um 07:56