Reducing the 0-1 Knapsack Problem with a Single Continuous Variable to the Standard 0-1 Knapsack Problem

Marcel Büther and Dirk Briskorn
Additional contact information
Marcel Büther: Christian-Albrechts-Universität zu Kiel, Germany
Dirk Briskorn: Universität zu Köln, Germany

International Journal of Operations Research and Information Systems (IJORIS), 2012, vol. 3, issue 1, 1-12

Abstract: 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 the authors to employ approaches for KP. The authors propose both, an equivalent reformulation and a heuristic one bringing along less computational effort. The authors 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.

Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/joris.2012010101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:joris0:v:3:y:2012:i:1:p:1-12

Access Statistics for this article

International Journal of Operations Research and Information Systems (IJORIS) is currently edited by John Wang

More articles in International Journal of Operations Research and Information Systems (IJORIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().