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 (Christian-Albrechts-Universität zu Kiel, Germany) and Dirk Briskorn (Universität zu Köln, Germany)
DOI: 10.4018/joris.2012010101
OnDemand PDF Download:
$30.00
List Price: $37.50

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.
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 . 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:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2018): 1 Released, 3 Forthcoming
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