Reducing the 0-1 knapsack problem with a single continuous variable to the standard 0-1 knapsack problem

Arbeitspapier

The 0-1 knapsack problem with a single continuous variable (KPC) is a natural extension of the binary knapsack problem (KP), where the capacity is not any longer fixed but can be extended which is expressed by a continuous variable. This variable might be unbounded or restricted by a lower or upper bound, respectively. This paper concerns techniques in order to reduce several variants of KPC to KP which enables us to employ approaches for KP. We propose both, an equivalent reformulation and a heuristic one bringing along less computational effort. We show that the heuristic reformulation can be customized in order to provide solutions having an objective value arbitrarily close to the one of the original problem.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 629

Klassifikation und Themen

• Klassifikation: Management
• Thema: 0-1 knapsack problem with a single continuous variable ; binary knapsack problem ; mixed integer programming ; reformulation ; lower bound ; binary representation ; Ganzzahlige Optimierung ; Branch-and-Bound ; Theorie

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Büther, Marcel ; Briskorn, Dirk
• Ereignis: Veröffentlichung
• (wer): Universität Kiel, Institut für Betriebswirtschaftslehre ; ZBW – Leibniz Information Centre for Economics
• (wo): Kiel
• (wann): 2007

Weitere Informationen

• Handle: http://hdl.handle.net/10419/147682
• Letzte Aktualisierung: 10.03.2025, 11:42 MEZ