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

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

Marcel Büther, Dirk Briskorn
DOI: 10.4018/joris.2012010101
(Individual Articles)
No Current Special Offers


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.
Article Preview

2. Model Formulation And First Insights

Given a set N = {1,…,n} of items with profit pj and weight wjfor each item jN, the objective is to maximize the profit sum of the chosen items regarding the capacity b, b > 0, of the knapsack. To this end, binary decision variable xj, jN, is used.

We reasonably restrict the parameters: pj > 0 and

wj > 0, jN. Moreover, in order to avoid trivial cases we assume joris.2012010101.m02. According to the KPC the original capacity b, can be adjusted. Continuous variable s represents the amount of capacity which is added (s > 0) or removed (s < 0), respectively. The value per unit of flexible capacity is c, c > 0. Now, the problem can be stated mathematically as an extension of the classical formulation of KP, see, e.g., Pisinger (2005):

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 14: 1 Issue (2023)
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing