Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: http://hdl.handle.net/10419/147682
Autoren: 
Büther, Marcel
Briskorn, Dirk
Datum: 
2007
Schriftenreihe/Nr.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 629
Zusammenfassung: 
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.
Schlagwörter: 
0-1 knapsack problem with a single continuous variable
binary knapsack problem
mixed integer programming
reformulation
lower bound
binary representation
Dokumentart: 
Working Paper
Dokumentversion: 
Digitized Version

Datei(en):
Datei
Größe
658.97 kB





Publikationen in EconStor sind urheberrechtlich geschützt.