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

2. Model Formulation And First Insights

Given a set N = {1,…,n} of items with profit p_j and weight w_jfor each item j ∈ N, 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 x_j, j ∈ N, is used.

We reasonably restrict the parameters: p_j > 0 and

w_j > 0, j ∈ N. 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):