Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 7 von 37
Zurück zur Trefferliste

Facets for the Multiple Knapsack Problem.

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-1007
  • 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 maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper SC 93-07.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Carlos E. Ferreira, Alexander Martin, Robert Weismantel
Dokumentart:ZIB-Report
Datum der Erstveröffentlichung:12.02.1993
Schriftenreihe (Bandnummer):ZIB-Report (SC-93-04)
ZIB-Reportnummer:SC-93-04
Verlagspublikation:SC 93-04 and SC 93-07 appeared under the title: Solving Multiple Knapsack Problems by Cutting Planes in: SIAM J. Optimization 6 (1996) pp. 858-877
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.