Article Preview
TopGiven a set N = {1,…,n} of items with profit pj and weight wjfor 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 xj, j ∈ N, is used.
We reasonably restrict the parameters: pj > 0 and
wj > 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):