arXiv:1702.04211v1 [cs.DS] 14 Feb 2017

Dynamic programming algorithms, efficient solution of
the LP-relaxation and approximation schemes for the
Penalized Knapsack Problem
Federico Della Crocea,b , Ulrich Pferschyc , Rosario Scatamacchiaa,∗
a Dipartimento

di Automatica e Informatica, Politecnico di Torino,
Corso Duca degli Abruzzi 24, 10129 Torino, Italy,
{federico.dellacroce, rosario.scatamacchia}@polito.it
b
CNR, IEIIT, Torino, Italy
c
Department of Statistics and Operations Research, University of Graz,
Universitaetsstrasse 15, 8010 Graz, Austria,
pferschy@uni-graz.at

Abstract
We consider the 0–1 Penalized Knapsack Problem (PKP). Each item has a
profit, a weight and a penalty and the goal is to maximize the sum of the profits
minus the greatest penalty value of the items included in a solution. We propose
an exact approach relying on a procedure which narrows the relevant range of
penalties, on the identification of a core problem and on dynamic programming.
The proposed approach turns out to be very effective in solving hard instances
of PKP and compares favorably both to commercial solver CPLEX 12.5 applied to the ILP formulation of the problem and to the best available exact
algorithm in the literature. Then we present a general inapproximability result
and investigate several relevant special cases which permit fully polynomial time
approximation schemes (FPTASs).
Keywords: Penalized Knapsack problem, Exact algorithm, Dynamic
Programming, Approximation Schemes

1. Introduction
We consider the 0–1 Penalized Knapsack Problem (PKP), as introduced in
[1]. PKP is a generalization of the classical 0–1 Knapsack Problem (KP) ([7],
[5], [3]), where each item has a profit, a weight and a penalty. The problem
calls for maximizing the sum of the profits minus the greatest penalty value of
the items included in a solution.
∗ Corresponding

author: Rosario Scatamacchia

PKP has applications in resource allocation problems with a bi–objective
function involving the maximization of the sum of profits against the minimization of the maximum value of a feature of interest. As an example, applications
arise in batch production systems where the processing time/cost of batches of
products depends on the maximum processing time of each product. PKP also
occurs as sub–problem within algorithmic frameworks designed for more complex problems. For instance, PKP arises as a pricing sub–problem in branch–
and–price algorithms for the two–dimensional level strip packing problem in
[4].
PKP is N P–hard in the weak sense since it contains the standard KP as
special case, namely when the penalties of the items are equal to zero, and it can
solved by a pseudo–polynomial algorithm. In [1], it is mentioned that a dynamic
programming approach with time complexity O(n2 c) can be easily determined,
with n and c being the number of items and the capacity of the knapsack
respectively. Also, an exact algorithm is presented and successfully tested on
instances with 1000 variables while running into difficulties on instances with
10000 variables.
In this work we propose an exact approach that relies on a procedure
narrowing the relevant range of penalties and on dynamic programming.
First, a straightforward pseudo–polynomial algorithm running with complexity
O(max{n log n, nc}) is lined out. Then, as our major contribution, we devise a
dynamic programming algorithm based on a core problem and the algorithmic
framework proposed in [8]. We investigate the effectiveness of our approach on a
large set of instances generated according to the literature and involving different types of correlations between profits, weights and penalties. The proposed
approach turns out to be very effective in solving hard instances and compares
favorably to both solver CPLEX 12.5 and the exact algorithm in [1], successfully
solving all instances with up to 10000 items.
Finally, we provide additional theoretical insights into the problem, in particular about upper bounds. We derive a surprising negative approximation
result, but also investigate several relevant special cases which still permit fully
polynomial time approximation schemes (FPTAS).
The paper is organized as follows. In Section 2, the linear programming formulation of the problem is introduced. In Section 3, we provide some insights
on structure and properties of PKP. We outline the proposed exact solution
approach in Section 4 and discuss the computational results in Section 5. Approximation results are presented in Section 6. Section 7 concludes the paper
with some remarks. Note that this report is a slightly extended version of a
journal paper.
2. Notation and problem formulation
In PKP a set of n items is given together with a knapsack with capacity
c. Each item j has a weight wj , a profit pj and a penalty πj . We will assume
that all data are non–negative integer values. Note that [1] assume only the
integrality of weights. Similar to their work, all our algorithmic contributions do
2

not require integral profits or penalties. However, the theoretical approximation
results of Section 6 partially rely on integral values. We will assume that items
are sorted in decreasing order of penalties, i.e.
π1 ≥ π2 ≥ . . . ≥ πn .

(1)

The problem calls for maximizing the total profit minus the greatest penalty
value of the selected items without exceeding the knapsack capacity c. In order
to derive an ILP-formulation, we associate with each item j a binary variable xj
such that xj = 1 iff item j is placed into the knapsack. Also, we associate a real
variable Π with the decrease in the objective produced by the highest penalty
value of the items placed in the knapsack. The problem can be formulated as
follows:
n
X
pj xj − Π
(2)
(PKP)
maximize
subject to

j=1
n
X

wj xj ≤ c

(3)

j=1

πj xj ≤ Π
xj ∈ {0, 1}
Π∈R

j = 1, . . . , n
j = 1, . . . , n

(4)
(5)
(6)

(3) is the standard capacity constraint. Constraints (4) ensure that Π will carry
the highest penalty value in any feasible solution of PKP; variable Π can be
defined in (6) as real and will always attain one of the values πj in an optimal
solution. The objective function (2) maximizes the sum of the profits minus
the greatest penalty value of the selected items. Its optimal function value will
be denoted by z ∗ . For any considered sub–problem P P the optimal objective
function value will be written as z(P P ). The item yielding the optimal penalty
will be called the leading item and is denoted by j ∗ .
For further analysis, we will consider the penalty value Π as a fixed parameter and define P KP (Π) as an instance of PKP where the penalty value in
the objective function is fixed to Π. This simply means that all items j with
πj > Π are eliminated from consideration and the remaining problem reduces
to a standard 0–1 knapsack problem. Obviously, P KP (Π) only needs to be
considered for the n relevant choices Π ∈ {π1 , . . . , πn }. This implies that PKP
can be solved to optimality by solving at most n KP instances of type P KP (Π)
and taking the maximum objective function value.
3. Generalities and algorithmic insights
We discuss here structure and properties of PKP. We provide a characterization of the linear relaxation of PKP and propose an improved variant of the
procedure proposed in [1] for computing upper bounds on the sub–problems
induced by the selection of the leading item. Then, we outline a basic dynamic
programming algorithm with running time O(max{n log n, nc}).

3

3.1. Computing upper bounds
A natural upper bound on PKP is given by the optimal solution value of
the linear relaxation of the problem, denoted as P KP LP , where constraints
(5) are replaced by xj ∈ [0, 1], i.e. items can be split and only a fractional
part is packed. In this case a proportional part of the penalty applies. The
optimal objective function value will be denoted by z LP . The LP-relaxation
parametrically depending on Π will be denoted as P KP LP (Π) with optimal
solution value z LP (Π). In the LP-relaxation for a given value Π, each variable xj
is upper bounded by the following expression, since items with penalty exceeding
Π are reduced by scaling:
xj ≤ min{1, Π/πj }.

(7)

After imposing this bound the problem reduces again to an instance of KP
(for fixed Π) for which the LP-relaxation is trivial. We can give the following
characterization for P KP LP (Π).
Theorem 1. z LP (Π) is a piecewise-linear concave function in Π consisting of
at most 2n linear segments.
Proof. Consider an arbitrary value of Π and the corresponding solution xLP (Π).
Let S denote the set of items j with xLP
j (Π) = Π/πj , i.e. all items whose values
are currently bounded by the considered penalty value Π. The current split
item will be denoted as s.
We analyze the slope on the left-hand side of (Π, z LP (Π)) by considering the
change of the function implied by a decrease of the penalty bound from Π to
Π − ε for some small ε > 0. Formally, this change δ(Π) is given as follows:
X ε
ps X ε
δ(Π) = z LP (Π) − z LP (Π − ε) = − ε +
pj
wj
−
πj
ws
πj
j∈S
j∈S
| {z }
|
{z
}
reduction of items in S
increase of split item




X wj  pj
ps 


−
= ε −1 +

πj wj
ws 

j∈S
{z
}
|

(8)

≥0

This expression can be positive or negative, but it shows that δ(Π) is proportional to ε. Thus, in a neighborhood of (Π, z LP (Π)) the function consists of a
linear piece which will end in one of the following three cases:
1. Π − ε = πk for some k 6∈ S. This means that lowering Π, a new item is
found for inclusion in S. Plugging in the extended set S in (8) will clearly
increase the change δ(Π).
2. xs reaches 1. This means that the split item becomes integral and item
ps+1
s + 1 becomes the new split item. Thus, we replace wpss by w
in (8)
s+1
again implying an increase of δ(Π).
4

3. xs reaches (Π − ε)/πs . This means that the increase of the split item
reaches the lowered penalty bound. In this case, s is included in S and
s + 1 becomes the new split item. Again, δ(Π) is increased by combining
both of the above arguments.
Summarizing, we have shown that starting with an arbitrary value of Π and
decreasing Π, z LP (Π) consists of a linear piece which ends with some Π′ ≤ Π
in one of three possible configurations. The slope of this linear piece is given by
δ(Π)
LP
(Π′ ) will have an increased change
ε . The preceding linear segment of z
′
′
δ(Π ) if Π is further decreased. This means that the previous linear segment at
z LP (Π′ ) has a larger slope than z LP (Π). Thus, the slope of z LP (Π) is decreasing
with increasing Π which proves the concavity of z LP (Π).
Starting the above procedure with Π = maxnj=1 πj and reducing Π iteratively
until Π = 0, it is clear that each item may cause the end of a linear segment
of z LP (Π) at most twice: Once, by becoming a new split item and once by
being included in set S. Each such event can occur at most once for each item.
Therefore, there can be at most 2n linear pieces.
Exploiting this characterization one can easily construct a solution algorithm
based on binary search over the penalty space with O(n log π1 ) time.
Some more effort is necessary to reach a binary search only over the n relevant
penalty values, which yields the following proposition.
Proposition 2. P KP LP can be solved in O(n log n) time.
Proof. Algorithmically, one can easily exploit the structure established in Theorem 1 by performing a binary search over Π to determine a maximum1 of
the concave function z LP (Π). For each query value Π, one can compute the
split item in linear time and also assemble the corresponding set S in one pass
through the set of items. Thus, for each query value Π the sign of the slope can
be calculated from (8) in linear time.
Applying the binary search over all possible penalty values would yield a total running time of O(n log π1 ) which is polynomial in the size of the (binary)
encoded input, i.e. weakly polynomial. To obtain a strongly polynomial time
algorithm whose running time depends only on the number of input values,
we can first perform a binary search over all n values πj and thus compute in
O(n log n) time the interval of two consecutive penalties [πk , πk−1 ] for some k
(with πk−1 ≥ πk according to (1)) which will include the optimal penalty value
ΠLP .
Let us denote the optimal split item by sLP and the split items associated with
penalties πk−1 and πk by sk−1 and sk respectively. If we consider the item
p
sorted by decreasing wjj , item sk−1 will precede item sk in the ordering.
If πk−1 = πk , clearly we have sLP = sk−1 = sk and ΠLP = πk−1 = πk . Otherwise, we have to find sLP in the interval [sk−1 , sk ] and related ΠLP in the interval
1 Note that the maximum is not necessarily unique, since there may exist a linear segment
of z LP (Π) with slope 0.

5

[πk , πk−1 ].
Let us consider a generic item s as candidate for the split item. The best penalty
Π associated with it can be calculated as follows. Given the interval [πk , πk−1 ],
we set xj = 1 (j = 1, . . . , s − 1) if πj ≤ πk , xj = πΠj otherwise. This implies that
the weight and profit sums of the items preceding s are linear functions of Π in
the form
s−1
X
wj xj = γ1 Π + γ2 ,
(9)
j=1

s−1
X

pj xj = θ1 Π + θ2 ,

(10)

j=1

with non-negative coefficients γ1 , γ2 , θ1 , θ2 determined P
according to the above
s−1
xj setting. Item s can be the split item if and only if j=1 wj xj < c and its
c−

Ps−1

wj xj

j=1
value xs fulfills the capacity (i.e. xs =
) while satisfying the bound
ws
(7). Correspondingly, the feasible interval of Π, denoted as Is (Π), which allows
s to be the split item is defined by the following system of inequalities:


πk ≤ Π ≤ πk−1



γ Π + γ ≤ c − ε
1
2
(
Is (Π) :=

1 if πs ≤ πk ;

c−γ
Π−γ
1
2

≤ β with β = Π

ws
πs otherwise

(11)

Item s̄ is a relevant candidate for the split item only if the corresponding interval
Is (Π) is non-empty. In such a case, the overall profit given by s as split item is
Ps (Π) =

s−1
X

pj xj + ps xs − Π = (θ1 −

j=1

ps
ps
γ1 − 1)Π + θ2 +
(c − γ2 )
ws
ws

(12)

and will be maximized by choosing either the left extreme of Is (Π) if the term
(θ1 − wpss γ1 − 1) < 0 or the right extreme otherwise.
Summarizing, the best penalty value associated with a candidate item can be
computed in constant time if coefficients γ1 , γ2 , θ1 , θ2 are given. Hence, we may
first consider item sk−1 as candidate for sLP and compute related coefficients in
(9)–(10) and penalty value. Then, we iteratively move to the next item after
updating coefficients γ1 , γ2 , θ1 , θ2 in one pass due the inclusion of the previous
candidate item among items j = 1, . . . , s − 1. After the evaluation of item sk ,
the optimal split item sLP and penalty ΠLP are returned. Since the execution
time of this part is bounded by O(n), the overall complexity for solving the LP
relaxation is O(n log n).
In fact, we can do even better by interleaving a median search for the optimal
penalty value with a median search for the split item.
Proposition 3. P KP LP can be solved in O(n log log n) time.
6

Proof. We describe an algorithm performing an iterative median search for ΠLP .
In each step of the algorithm we are given a feasible interval for ΠLP denoted as
[η ℓ , η u ]. Then we determine the median η m among all penalty values πj in this
interval. This value η m is considered as a candidate for ΠLP . For the resulting
solution it is easy to determine the slope of z LP (η m ) and decide accordingly
whether η m is set as new upper or lower bound of the search interval.
To find the split item more efficiently in each iteration we will avoid sorting
the items by efficiency but instead employ a linear time algorithm as described
in [3, ch. 3.1]. It is based on iterated bisection of the item set into sets of items
with higher resp. lower efficiency than a current target value ei . We will keep a
sorted list E consisting of all target values ei (in decreasing order of efficiencies)
considered so far during the search for a split item over the different penalty
candidate values.
Then we introduce the following data structures. Set Si contains all items
with a penalty value in the current search interval and efficiency value between
ei and the next larger efficiency target value ei−1 in E. Formally,
Si := {j ∈ N | η ℓ ≤ πj ≤ η u , ei−1 > ej ≥ ei }.
P
For each set Si we also define the canonical weight sum W (Si ) := j∈Si wj .
For the currently considered interval bounds η we use the following auxiliary
weight arrays for each ei ∈ E:
X
wj over all j with ej > ei and πj ≤ η
(13)
Wi (η) :=
j

Ri (η)

:=

X

wj over all j with ej > ei and πj > η

(14)

j

These arrays allow an easy evaluation of each target value ei ∈ E since the total
weight of all items with efficiency higher than ei and reduced to the current
penalty bound η is given by Wi (η) + Ri (η). Taking also the weight of the item
with efficiency ei into account, one can easily determine in constant time for a
give target ei whether the split item is found or a higher resp. lower target value
for the efficiency should be considered.
It remains to explain the update of the auxiliary data structures. Whenever
a new efficiency target value ek is generated for some item k with ei−1 ≥ ek ≥ ei
and inserted into E, the current set Si is partitioned into two sets, namely Sk
and (a new set) Si with the obvious definition. Also the array entries Wk (η)
resp. Rk (η) are generated from Wi−1 (η) resp. Ri−1 (η), while Wi (η) resp. Ri (η)
remain unchanged. These update operations can be done trivially by considering
all items of the original set Si explicitly.
In each main iteration, a new penalty search value η m is considered.
Therefore, all sets Si are bipartitioned into two disjoint sets Siℓ and Siu with
Siℓ ∪ Siu = Si and πj ≤ η m for j ∈ Siℓ , resp. πj > η m for j ∈ Siu . After deciding
on the new search interval one of these two sets will replace Si . Furthermore,

7

the auxiliary array entries are generated for η m . This can be done by setting
X
Wi (η m ) := Wi (η ℓ ) +
W (Skℓ ),
(15)
k≤i

Ri (η m ) :=

Ri (η u ) +

X

k≤i
j∈S u
k

wj

ηm
.
πj

(16)

Concerning the running time, the binary search over all n penality values,
i.e. over all candidates η m , requires O(log n) iterations. In each iteration we
consider explicitly each item with a penalty value in the current interval [η ℓ , η u ]
to determine the median η m and to update the auxiliary arrays in (15) and
(16). (Note that these array entries also have to be generated if no item in the
current interval is involved. However, since |E| ≤ log2 n there can be at most
log3 n such entries.) Since the search interval is bisected in each iteration, this
sums up to O(n) time.
The effort for finding the split items (and thus the solution of the linear
relaxation of the KP implied by the current penalty bound η) depends on the
sequence of efficiency target values considered in each iteration. Here, we will
exploit the fact that evaluating a target value can be done in constant time
employing (13) and (14). If the target value was already considered in an earlier
iteration for a previous penalty search value, then it is included in E and no
additional effort is required. Note that at most O(log2 n) such evaluations take
place during the execution of the algorithm. If the target value, say ek , is
considered for the first time, the corresponding set Sk has to be generated as
described above from a previously existing set Si , which requires considering all
items in Si .
In the first iteration (for the median of all penalty values), searching for the
split item starts with O(n) time for the first median (over all efficiencies), then
another O(n/2) time for the second target value (i.e. the median of the upper
or lower half of efficiency values), and so on. Searching for t-th target value
will require O(n/2t−1 ) time. This includes also going through all items of the
associated set Si which is of cardinality n/2t−1 .
The same holds for the second iteration, except for the first target value, since
the median of all efficiencies was for sure considered in the first iteration. The
second target value may or may not have been considered in the first iteration.
Thus, we have to take the corresponding effort of O(n/2) time into account.
In the third iteration, the effort for the second target value is only relevant,
if it was not considered in the second iteration. Generalizing this argument over
all iterations and taking – for the time being – only the first t efficiency target
values into account, it turns out that the effort for deciding the t-th target
values in total over all log n iterations can be at most O(n). This results from
considering each of the subsets of n/2t−1 items at most once. The total effort
of this part is O(n · t).
Continuing the analysis for target values numbered by t + 1, t + 2, . . . , log n

8

we can bound the effort for each iteration over one penalty value by
n/2t + n/2t+1 + . . . + 1 ≈ n/2t−1 .
This effort arises for all log n iterations over all penalty search values. Thus, we
can summarize the total running time associated to the solutions of the linear
relaxations as:
n
n · t + log n t−1
2
Plugging in t = log log n yields O(n log log n + n).
We may compute more involved upper bounds on PKP as follows. As pointed
out above, the optimal solution of PKP is determined by a penalty value Π
and a subset of items j with πj ≤ Π. Therefore, we consider sub–problem
P KPj := P KP (πj ) for j = 1, . . . , n. Recalling (1) each P KPj is an instance of
KP with item set {j, j + 1, . . . , n} and capacity c where πj is subtracted from
the final solution value.
Fixing Π = πj for some j is only relevant for the final solution if item j is
actually included in the solution. Hence, as in [1], we also consider sub–problem
P KPj+ , where item j is packed, a fixed penalty of Π = πj is subtracted from
the objective function, and for the reminder of the solution a KP is solved with
capacity c − wj and item set {j + 1, . . . , n}.
For both P KPj resp. P KPj+ we consider the LP-relaxation as upper bound
denoted by P KPjLP resp. P KPj+LP . It is easy to see that
z(P KPj+ ) ≤ z(P KPj )

(17)

∗

z = max z(P KPj ) ≤ max
j=1,...,n

j=1,...,n

z(P KPjLP )

=: U Bsub

+
z ∗ = max z(P KPj+ ) ≤ max z(P KPj+LP ) =: U Bsub
j=1,...,n

j=1,...,n

(18)
(19)

+
The following dominance relations exist for the upper bounds U Bsub , U Bsub
LP
and z .

Proposition 4. For any PKP instance, we have that
+
U Bsub
≤ U Bsub ≤ z LP

(20)

and there are instances where the inequalities are strict.
+
Proof. Clearly, the restricted feasible domain of U Bsub
cannot lead to a greater
+
value than U Bsub and thus U Bsub ≤ U Bsub . Let us denote by j ′ the item
yielding U Bsub , i.e. U Bsub = z(P KPjLP
). Computing P KP LP (Π) with Π =
′
πj ′ gives a feasible solution for the LP relaxation whose value is less than (or
equal to) the optimal value z LP but at least as large as U Bsub . The latter
holds because all items are involved (and bounded according to (7)) in the
computation while only items i with πi ≤ πj ′ are considered for solving P KPjLP
.
′
LP
This implies that U Bsub ≤ z .

9

To show that inequalities in (20) can be strict, consider the following PKP
instance with n = 2 items, capacity c = 7 and the entries:
p1 = 10, w1 = 5, π1 = 1;

p2 = 6, w2 = 4, π2 = 2

For this instance we have z LP = 12, z(P KP1LP ) = −1 + 10 = 9, z(P KP2LP ) =
−2 + 10 + 42 6 = 11, z(P KP1+LP ) = −1 + 10 = 9, z(P KP2+LP ) = −2 + 6 + 35 10 =
10. Thus, we have:
+
U Bsub
= 10 < U Bsub = 11 < z LP = 12

Although the three bounds can be computed efficiently and can be expected
to be reasonably close to the optimal value in practice, we show a negative result
on their deviation from the optimum.
+
Proposition 5. There are instances of PKP where the differences (U Bsub
−z ∗ ),
∗
LP
∗
(U Bsub − z ) and (z − z ) are arbitrarily large.

Proof. Consider the following instance with n = 2 items, capacity c = M and
M
the following entries: pj = wj = M
2 + 1 and πj = 2 for j = 1, 2. In an optimal
solution only one item j is packed and, correspondingly, z ∗ = pj − πj = 1. Also,
+
it is easy to see that U Bsub
= M
2 , which, in combination with (20), shows the
claim.
Algorithmically, it is not difficult to see that all values z(P KPjLP ) for j =
1, . . . , n can be computed in O(n log n) time. Also from a practical point of view,
the effort hardly exceeds sorting. As a preprocessing step an auxiliary array is
constructed containing all items sorted in decreasing order of efficiencies pj /wj .
Then the problems P KPjLP are considered iteratively for j = 1, . . . , n, i.e., in
decreasing order of penalties πj . First, P KP1LP is solved in linear time and the
corresponding split item (i.e. the first item not fully packed into the knapsack)
is identified. We keep a pointer to this split item in the sorted array of items.
Moving to P KP2LP , we just remove item 1 from the solution and increase the
split item, or possibly move to a new split item by shifting the pointer towards
items with lower efficiency. All together, after sorting, all values z(P KPjLP )
can be determined in linear time by one pass through the sorted array of items.
In [1], the authors presented an O(n2 ) procedure to compute all values
z(P KPj+LP ) for j = 1, . . . , n. In the following, we show that in fact O(n log n)
time is sufficient to perform this task.
Proposition 6. All values z(P KPj+LP ) for j = 1, . . . , n can be computed in
O(n log n) time.
Proof. First, the items are sorted in decreasing order of efficiencies. Based on
this sequence we construct an auxiliary data structure consisting of a binary tree
as follows: Each item corresponds to a leaf node of the tree. These are nodes at
10

level 0. A parent node is associated with each pair of consecutive items (with
a singleton remaining at the end for n odd) thus yielding other ⌈ n2 ⌉ nodes in
the level 1 of the tree. This process is iterated recursively up the tree, which
trivially reaches a height of O(log n).
In each node v of the tree we store as W (v) (resp. P (v)) the sum of weights
(resp. profits) of all items corresponding to leaf nodes in the subtree rooted in
v. Clearly, such a tree and its additional information can be built in O(n) time.
For any given capacity c′ the corresponding split item and also the value
of the optimal LP-relaxation can be found in O(log n) time by starting at the
root node and going down towards a leaf node by applying the following rule in
every node v with left and right child nodes v L and v R :
If W (v L ) > c′ then set v := v L .
Otherwise set v := v R and c′ := c′ − W (v L ).
The item corresponding to the leaf node reached by this procedure is the split
item. The solution value can be reported by keeping track of the P (v) values
during the pass through the tree.
In the main iteration of the algorithm we compute z(P KPj+LP ) iteratively
for j = 1, . . . , n in decreasing order of penalties πj . First we remove item j
permanently from consideration.This means that the leaf node corresponding
to j is removed from the tree and all O(log n) labels W (v) (resp. P (v)) on the
unique path from this leaf to the root of the tree are updated by subtracting
wj (resp. pj ). Then we solve an LP-relaxation with capacity c′ := c − wj and
add pj − πj to the objective function. All together there are n iterations, each
of which requiring O(log n) time to find the solution of the LP-relaxation and
O(log n) time to update the labels of the binary tree.
Note that we might expect a considerable speed–up of the running time
O(n log n) in a practical implementation since the tree looses vertices in each
iteration and path contractions can be performed.
3.2. A basic dynamic programming algorithm
As recalled in [1], a straightforward pseudo–polynomial algorithm for PKP
consists of solving j standard knapsack problems P KPj+ by the classical dynamic programming by weights running in O(nc). The overall complexity is
thus O(n2 c). However, we can do much better by evaluating all n subproblems
in one run.
Theorem 7. PKP can be solved with complexity O(max{nc, n log n}).
Proof. It suffices to consider the items sorted by increasing penalty and to run
the dynamic program for KP only once. If we denote by Fj (d) the optimal
solution value of the sub–problem of KP consisting of items 1, . . . , j and capacity
d ≤ c, the optimal value of any PKP instance is simply given by
max

j=0,...,n−1

{Fj (c − wj+1 ) + pj+1 − πj+1 }

11

(21)

That is, we evaluate the choice of item j + 1 as leading item just by considering the maximum profit reachable with the previous items in a knapsack with
capacity c − wj+1 . The running time is O(nc) plus the effort for sorting.
4. An exact solution approach
4.1. Overview
The DP algorithm of Theorem 7, hereafter denoted as DP1 , may be appealing whenever the capacity c is of reasonably limited size. However, for KP it
is known that more effective than the iterative addition of items are algorithms
based on the core problem. Thus, our idea is to exploit the core concept for
PKP similarly to the framework of the Minknap algorithm [8]. We remark that
the presence of penalties compromises in PKP the structure of an optimal solution with respect to a standard KP. This difference would typically affect the
performance of an approach based on a core problem. Further, the presence of
penalties limits the effectiveness of the classical dominance rule in KP based on
the profits and the weights of the states. Anyhow, from a practical perspective
it is still beneficial to run a dynamic programming algorithm starting from the
split solution of KP and not from scratch. In addition, by narrowing the interval
of penalty values which can possibly lead to an optimal solution, the “noise”
added by the penalties can be further reduced.
We propose an exact approach involving two main steps. In the first step,
we effectively compute an initial feasible solution for the problem and identify
the relevant interval of penalties values possibly leading to an optimal solution.
In the second step, we run a dynamic programming algorithm with states based
on the core concept. In case the first step yields a reduced problem with a
reasonably limited input size, we could as well launch the DP1 algorithm. In
the following subsections we describe the steps of the approach whose pseudo
code is presented in Algorithm 1.
4.2. Step 1: Computing an initial feasible solution and the relevant interval of
penalty values
The approach takes as input four parameters T1 , T2 , T3 , α and starts by
solving the standard knapsack problem KP1 given by disregarding the penalties
of the items in PKP (lines 2-3 in Algorithm 1). This problem is solved as follows.
Denote the index of the first item in the optimal solution of KP1 (according
to the ordering (1)) by f . The corresponding first feasible solution of PKP has
objective value z(KP1 ) − πf . Similarly to Proposition 2 in [1], the following
proposition holds
Proposition 8. All items j = 1, . . . , f − 1 can be discarded without loss of
optimality.
Proof. Since z(KP1 ) is the optimal solution value, including any item j =
1, . . . , f − 1 leads to a solution with profits less than (or equal to) z(KP1 )
but induces a penalty greater than (or equal to) πf .
12

Algorithm 1 Exact solution approach
1: Input: PKP instance, parameters T1 , T2 , T3 , α.

⊲ Step 1
2: KP1 = PKP without penalties;
3: (z, j, f ) ← ModMinknap(KP1 );
4: Compute z(P KPj+LP ) for j = f + 1, . . . , n;
5: U B = max z(P KPj+LP );
j

6: if U B ≤ z then z ∗ = z, j ∗ = j; return (z ∗ , j ∗ ); end if
7: k = arg max z(P KPj+LP );
j

8: KP2 = KP1 ∩ (xj = 0 j = 1, . . . , k − 1);
9: (ẑ, ĵ, fˆ) ← ModMinknap(KP2 );
10: if ẑ > z then z = ẑ, j = ĵ; end if
11:
12:
13:
14:

l ← Apply (22);
r ← Apply (23);
Πmax = πl ;
Πmin = πr ;

15: if [Πmin , Πmax ] = ∅ then z ∗ = z, j ∗ = j; return (z ∗ , j ∗ ); end if
16: P KP ′ = PKP ∩ (xj = 0 j = 1, . . . , l − 1; Π ≥ Πmin );
17: n′ = n − l + 1;

⊲ Step 2
18: if n′ c ≤ T1 and (r − l + 1) ≥ T2 then
19:
(z ′ , j ′ ) ← DP1 (P KP ′ );
20:
if z ′ > z then z ∗ = z ′ , j ∗ = j ′ ; else z ∗ = z, j ∗ = j; end if
21: else
22:
(z ∗ , j ∗ ) ← DP2 (P KP ′ , z, j, T3 , α);
23: end if
24: return (z ∗ , j ∗ );

13

Thus, if there is more than one optimal solution of KP1 , we are interested
in the solution yielding the lowest penalty value for PKP, i.e. the largest index
f . This task is easily accomplished by considering a slight variant of Minknap,
hereafter denoted as ModMinknap, which keeps track of all optimal solutions of
KP1 and the corresponding penalty values in PKP. In addition, we can compute
PKP solutions during the iterations of ModMinknap just by tracking the largest
penalty associated to each feasible state. We then take the overall best solution
found for PKP. Denote by z its value and by j the index of the leading item.
We remark that ModMinknap is only a heuristic algorithm for PKP since
it does not explicitly consider the penalties of the items in the iterations. At
the same, it may “stumble” upon good quality solutions of PKP with just a
negligible increase of the computational effort required for solving a KP instance.
Then, we compute z(P KPj+LP ) for j = f +1, . . . , n. If the maximum of these
values is not superior to z, we have already certified an optimal solution for PKP
(lines 4–6 in Algorithm 1). Otherwise we greedily consider the index k yielding
the maximum z(P KPj+LP ) and solve KP1 without items j = 1, . . . , k − 1. We
update the values of z and j if an improving solution is found (lines 7–10 in
Algorithm 1).
Finally, we compare the values z(P KPj+LP ) with the incumbent solution
value z and narrow the range of possible penalty values that may lead to an
optimal solution of PKP. More precisely, we define indices l and r
l

:=

min {j : z(P KPj+LP ) > z};

(22)

r

:=

max {j : z(P KPj+LP ) > z}.

(23)

The relevant interval of penalties is thus [Πmin , Πmax ], with Πmin = πr and
Πmax = πl (line 11–14 in Algorithm 1). If this interval is empty, the current
PKP solution is also optimal and the algorithm terminates. Otherwise we get
a reduced PKP with only items j = l, . . . , n and the additional constraint on
the penalty value Π ≥ Πmin . Denote this problem by P KP ′ and its number of
items by n′ , i.e. n′ = n − l + 1 (lines 15–17 in Algorithm 1).
This first step is expected to be fast since it relies on solving two standard
knapsack problems at most and on effectively computing upper bounds for sub–
problems P KPj+ . We remark that this step is also sufficient to compute an
optimal solution for a large number of instances considered in the literature.
4.3. Step 2: A core–based dynamic programming algorithm
In this step we propose a core–based dynamic programming algorithm, hereafter denoted as DP2 , that constitutes a revisiting of Minknap algorithm. Notice
that, if the size of the reduced problem P KP ′ is reasonably small and the number of relevant penalties is large, we could otherwise solve P KP ′ by DP1 and
take the best solution between z(P KP ′ ) and z. The choice between the algorithms is made by comparing the quantities n′ c and (r −l+1) with the threshold
parameters T1 and T2 (lines 18–23 in Algorithm 1).
14

DP2 algorithm searches in P KP ′ for solutions better than z. Given the
p
sorting of the items j = 1, . . . , n′ by decreasing wjj , we define an expanding
core as the interval of items Ca,b = {a, . . . , b} with items a and b as variable
extremes. Correspondingly, we define the set of 0–1 partial vectors enumerated
within the core as
Xa,b = {xj ∈ {0, 1}, j ∈ Ca,b }.
(24)
Since in any iteration of the algorithm we will have the following situation
xj = 1
xj = 0
z
}|
{
}|
{
z
x1 , . . . , xa−1 , Ca,b , xb+1 , . . . , xn′

(25)

we associate each partial vector x̃ ∈ Xa,b with a state (ν̃, µ̃, π̃core , π̃tot ) where:
1. ν̃ =

a−1
P
j=1

2. µ̃ =

a−1
P
j=1

pj +

b
P

pj x̃j ;

j=a

wj +

b
P

wj x̃j ;

j=a

3. π̃core = max {πj : x̃j = 1};
j=a,...,b

4. π̃tot = max{π̃core ,

max

j=1,...,a−1

πj }.

ν̃ and µ̃ are the profits and weights of a solution with variables in the core and
all variables to the left of the core; π̃core represents the maximum penalty of the
items selected in the core while π̃tot is the overall maximum penalty of the state.
Each state with µ̃ ≤ c and π̃tot ≥ Πmin represents a feasible solution of P KP ′
with value ν̃ − π̃tot . We can now sketch the main steps of DP2 in the following
pseudo code. The algorithm takes as input P KP ′ , the current solution (z, j)
and parameters T3 , α.
p
We first sort the items of P KP ′ by decreasing wjj and find the split item s′
of the standard knapsack problem (KP ′ ) induced by disregarding the penalties
in P KP ′ . We then initialize the core with item s′ only (lines 1–4 of the pseudo
code). Then, we enlarge the core as in Minknap (while–loop in lines 6–23) by
alternately evaluating the removal of an item a from the left (lines 7–14) and
the insertion of an item b from the right (lines 15–22). The expansion of the
core is performed by a dynamic programming with states through a procedure,
denoted as Merge, which iteratively yields undominated states in the enlarged
set Xa,b = Xa+1,b + a or Xa,b = Xa,b−1 + b. We may update the current solution
(z, j) if an improved solution is found while enumerating the core (lines 11 and
19).
The dynamic programming with states is combined with an upper bound
test to reduce the number of states (lines 5, 12 and 20) and two upper bound
tests to limit the insertion of the variables in the core (lines 8–9 and 16–17). The
algorithm terminates whenever either the number of states is 0 or all variables
have been enumerated in the core. The ingredients of the algorithm are detailed
in the following.
15

Algorithm 2 DP2 (P KP ′ , z, j, T3 , α)
1: Sort items in P KP ′ by decreasing
′

pj
wj

;

′

2: KP = P KP without penalties;
3: Find the split item s′ of KP ′ ;
4: a = b = s′ , Ca,b = {s′ }; Xa,b = {(0), (1)};
5: Reduce set Xa,b ;
6: while Xa,b 6= ∅ and (b − a + 1 < n′ ) do
7:
a ← a − 1;
8:
if ua0 > z then
9:
if ũa > z then
10:
Xa,b ← M erge(a, Xa+1,b , Πmin , T3 , α);
11:
Update (z, j);
12:
Reduce set Xa,b ;
13:
end if
14:
end if
15:
16:
17:
18:
19:
20:
21:
22:

b ← b + 1;,
if ub1 > z then
if ũb > z then
Xa,b ← M erge(b, Xa,b−1 , Πmin , T3 , α);
Update (z, j);
Reduce set Xa,b ;
end if
end if

23: end while
24: return (z, j);

16

4.3.1. Dynamic programming with states
The Merge procedure performs the enumeration of the variables in the core
by resembling the procedure introduced in Minknap [8], which in turn corresponds to the recursions of the primal–dual dynamic programming algorithm in
[9]. The proposed procedure merges, in any iteration, the current set of states X
and X + d, where X + d is set X with profits, weights and penalties of the states
updated according to the removal/insertion of item d from/in the knapsack. In
the merging operation the states are kept ordered by increasing weights so as
to effectively apply a dominance rule for PKP.
The classical dominance rule in KP considers the weights and profits of the
states. For PKP, let us define the quantity ρ = ν − max{πcore , Πmin } which
represents the difference between the profit of a state and the minimum penalty
that the state must have for yielding an optimal solution. This penalty corresponds to the maximum between Πmin and πcore since, due to the enumeration
of the core, for any state πcore constitutes a minimum penalty value in all states
originating from it while Πmin is the minimum penalty required in any solution
with a value greater than z. We introduce the following dominance rule for two
generic states i and j.
Proposition 9. Given states i and j and their quantities fulfilling
µi ≤ µj ,

νi ≥ νj ,

ρi ≥ ρj .

(26)

Then state j is said to be dominated by state i and can be discarded in the search
for an optimal solution of PKP.
Proof. The first two conditions represent the dominance of state i in the standard KP. The condition ρi ≥ ρj implies that all successive states deriving from
state i and possibly optimal for P KP (i.e. with a penalty greater than Πmin )
would have a no worse solution value than those deriving from state j.
We remark that, given the presence of penalties, the ordering of states
increasing weights does not imply the ordering of the profits as in Minknap.
better detect situations of dominance, we apply the rule in Proposition 9
comparing each state with a number of states (with a lower weight) given
parameter α.

by
To
by
by

Whenever only the condition involving the penalties prevents the fathoming
of state j, we may combine the dominance rule with an upper bound on state j
j
depending on a penalty value π > max{πcore
, Πmin }.
j
This upper bound, denoted by U B(π) , is computed as follows. We first solve
the linear relaxation of the KP induced by packing the items selected in the core
for state j and by disregarding the items outside the core with a higher penalty
than π. From the optimal solution value of this problem we then subtract the
j
maximum value between πcore
and Πmin . The following proposition holds
Proposition 10. Given two states i and j and the quantities
µi ≤ µj ,

νi ≥ νj ,
17

ρi < ρj ,

(27)

consider the maximum penalty π̂ which would not induce the dominance of state
i according to (26), i.e. π̂ = max {π : ν j − π > ρi }. If U B(π̂)j ≤ z, then state
j can be discarded.
Proof. We analyze the solution values deriving from state j when the overall
maximum penalty is upper bounded by a quantity π ′ . For any π ′ ≤ π̂, since
U B(π̂)j ≤ z we can discard state j because all states deriving from state j
cannot reach a solution values greater than z. Likewise, we can as well discard
state j if π ′ > π̂ since this condition would induce a dominance of state i.
Computing U B(π) has complexity O(n) and would be time–consuming if the
number of states involved is sufficiently large. Thus, we calculate this bound
only if the number of states exceeds the threshold value T3 .
4.3.2. Reduction of the states
To further reduce the set of states, we also perform an upper bound test in
constant time for each state. In any iteration, we compute the following upper
bound for a state i associated with Xa,b :

 ρi + (c − µi ) wpb+1
if µi ≤ c
b+1
i
UB =
(28)
 ρi + (c − µi ) pa−1
if µi > c
wa−1

and discard state i if U B i ≤ z. These upper bounds are computed by replacing
the integrality constraint on xa−1 and xb+1 with xa−1 ≥ 0 and xb+1 ≥ 0 and by
disregarding the penalty values of the variables outside the core.
4.3.3. Upper bound tests on the variables outside the core
Since the insertion of variables in the core may be computationally expensive, we perform two upper bound tests whenever an item j is candidate to be
included in the core.
We first compute similar bounds to the ones proposed in [2] for KP. Let us
denote by uj0 an upper bound on P KP ′ without item j. Also, let us denote by
uj1 the upper bound when item j is packed. The following bounds are computed
in constant time for each item j:
ps′
ws′

uj0

=

p′ − pj − Πmin + (c − w′ + wj )

uj1

=

p′ + pj − max{πj , Πmin } + (c − w′ − wj )

Here w′ =

′
sP
−1

j=1

wj and p′ =

′
sP
−1

j = 1, . . . , s′ − 1

(29)

ps′
j = s′ + 1, . . . , n (30)
ws′

pj represent the weight and the profit of the

j=1

split solution of KP ′ . If uj0 (resp. uj1 ) ≤ z, we can fix variable xj = 1 (resp.
xj = 0).
In cascade, we may perform a second test by computing a stronger upper
bound in linear time with the number of states. As in Minknap, we evaluate
18

the impacts of removing (inserting) item j with j < s′ (j > s′ ) in all states
in the current set X, namely we derive states i ∈ X + j and compute upper
bounds (28) on these states. A valid upper bound for item j, denoted as ũj ,
is constituted by the maximum of these bounds. As pointed out in [8], ũj can
be seen as a generalization of the enumerative bound in [6]. If ũj ≤ z, then
variable xj is fixed to the value taken in the split solution.
After this second step, the optimal solution value z ∗ and the optimal leading
item j ∗ are returned. The optimal solution set of items can be determined by
solving the standard knapsack problem P KPj+∗ .
5. Computational results
All tests were performed on an Intel i7 CPU @ 2.4 GHz with 8 GB of RAM.
The code was implemented in the C++ programming language. We generated
the instances according to the generation scheme proposed in [1]. We considered
two types of weights: a1 and a2. In the former, the weights are randomly
distributed in [1, R], with R being an arbitrary parameter. In the latter, the
weights are equal to R2 + v, with v uniformly distributed in [0, R2 ]. Basically,
small weights are not considered in a2.
We generated 8 classes of penalties (π1, . . . , π8) and 7 classes of profits
(p1, . . . , p7) according to different correlations of penalties/profits with the
weights, as illustrated in Table 1. The first 6 correlations correspond to classical
correlations in KP instances. In class π7 penalties πj are equal to R − wj + 1
(constant perimeter correlation) while in class π8 we set πj = wRj (constant area
correlation). In class p7 we set pj = πj wj . Finally, three different values of the
ratio τ between the knapsack capacity and the sum of the weights of the items
are considered: 0.5, 0.1 and 0.01.
π type
π1
π2
π3
π4
π5
π6
π7
π8

Correlation
No correlation
Weak correlation
Strong correlation
Inverse strong correlation
Almost strong correlation
Subset-sum correlation
Constant perimeter
Constant area
Profit = area

p type
p1
p2
p3
p4
p5
p6

p7

Table 1: Correlation types from [1].

We first generated instances with 1000 items and R = 1000. Within each
category, five instances were tested for a total of 1680 instances. Similarly,
we generated 1680 instances with 10000 items and R = 10000. We compared
the solutions reached by the proposed exact approach, the algorithm in [1] and
CPLEX 12.5 running on model (PKP). After some preliminary test runs, we
19

chose the following parameter values for our approach: α = 15, T1 = 5 ∗ 109 ,
n
T2 = 10
, T3 = 3 ∗ 106 . The parameters of the ILP solver were set to their default
values.
The results are summarized in Tables 2 and 3 in terms of average, maximum
CPU time and number of optima obtained within a time limit of 100 seconds.
The average CPU times consider also the cases where the time limit is reached.
The results are aggregated by profit classes and weight types. Each entry in the
tables reports the results over 120 instances. Detailed results for all correlations
and capacity ratios are given at the end of this section.
n = 1000
Profit
class
p1
p2
p3
p4
p5
p6
p7

Weight
type
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2

CPLEX 12.5
Average
Max
time (s)
time (s)
0.18
0.25
0.19
0.48
0.39
1.69
1.12
6.32
3.90
100.00
6.83
100.00
59.56
100.00
66.97
100.00
4.13
100.00
14.97
100.00
2.67
90.38
2.97
13.57
27.58
100.00
38.24
100.00

#Opt
120
120
120
120
117
117
57
46
117
114
120
120
89
75

Algorithm in [1]
Average
Max
time (s)
time (s)
#Opt
0.00
0.01
120
0.00
0.01
120
0.00
0.01
120
0.00
0.01
120
0.04
0.89
120
0.50
8.02
120
0.10
1.38
120
0.28
7.75
120
0.03
0.89
120
0.41
4.50
120
0.00
0.06
120
0.01
0.15
120
0.00
0.01
120
0.01
0.06
120

Proposed exact approach
Average
Max
time (s)
time (s)
#Opt
0.00
0.00
120
0.00
0.03
120
0.00
0.10
120
0.01
0.27
120
0.01
0.40
120
0.02
0.29
120
0.02
0.18
120
0.04
0.26
120
0.02
0.20
120
0.07
1.40
120
0.00
0.03
120
0.01
0.08
120
0.00
0.02
120
0.01
0.07
120

Table 2: Summary results for instances with 1000 items and different correlations between
profits and weights: time (s) and number of optima over 120 instances.

n = 10000
Profit
class
p1
p2
p3
p4
p5
p6
p7

Weight
type
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2

CPLEX 12.5
Average
Max
time (s)
time (s)
0.95
2.68
4.19
100.00
5.41
33.84
12.43
100.00
44.61
100.00
74.13
100.00
91.60
100.00
94.69
100.00
25.45
100.00
65.99
100.00
83.08
100.00
81.05
100.00
51.00
100.00
40.12
100.00

#Opt
120
117
120
114
74
46
11
7
95
48
58
44
63
75

Algorithm in [1]
Average
Max
time (s)
time (s)
#Opt
0.01
0.02
120
0.01
0.04
120
0.01
0.02
120
0.01
0.07
120
25.59
100.00
96
48.26
100.00
74
17.68
100.00
106
26.34
100.00
106
10.70
100.00
113
23.74
100.00
101
0.67
40.17
120
3.62
100.00
119
0.17
0.94
120
0.54
3.94
120

Proposed exact approach
Average
Max
time (s)
time (s)
#Opt
0.01
0.03
120
0.01
0.03
120
0.02
0.13
120
0.04
0.73
120
2.59
58.46
120
5.53
29.00
120
2.81
18.88
120
7.82
80.02
120
2.66
70.71
120
7.04
58.60
120
0.22
5.38
120
1.95
16.65
120
0.42
2.50
120
1.41
11.46
120

Table 3: Summary results for instances with 10000 items and different correlations between
profits and weights: time (s) and number of optima over 120 instances.

From Tables 2 and 3 we see that, for the instances with 1000 items, both the
proposed exact approach and the algorithm in [1] outperform CPLEX 12.5 which
does not reach all the optima within the time limit. Although the performances
of the algorithms are similar, we note that our approach generally performs
slightly better and requires 1.4 seconds at most for solving to optimality all
instances.
In the largest instances with 10000 items, our algorithm strongly outperforms
both CPLEX 12.5 and the algorithm in [1]. Our approach is capable of reaching
all optima with limited CPU time (80 seconds at most for an instance in class
20

p4) while the solver and the competing algorithm run out of time for several
large instances. The largest differences in computational times involve instances
in classes p3, p4 and p5.
The most challenging instances for our algorithm turned out to be the ones
without small weights (a2). In general, the absence of small weights might increase the computational effort required for solving even standard KP instances
(as pointed out, e.g., in [1]) and this is presumably the reason of the increase in
CPU times of our algorithm as well.
In many instances, the first main step relying on solving standard KPs is
sufficient to certificate an optimal solution for PKP. Indeed, this constitutes
a remarkable strength of our procedures. In Tables 4 and 5 we report the
percentage of the optimal solutions already computed by the first step of the
procedure for the instances with 1000 and 10000 items respectively. Averaged
computational times (% of the total CPU time) of the two steps of our approach
are also reported. Finally, we report the average and maximum values (in
thousands) of the maximum number of states reached by DP2 algorithm in
each instance. We point out that DP1 algorithm is called a limited number of
times with respect to DP2 (5% of the cases) and mainly in the smallest instances
with 1000 items.
Proposed exact approach
(n = 1000)
Profit
class
p1
p2
p3
p4
p5
p6
p7

Weight
type
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2

Step 1
only
#Opt
(%)
72.5
60.0
43.3
49.2
69.2
52.5
48.3
57.5
22.5
24.2
82.5
27.5
59.2
58.3

Step 1
Step
Time
(%)
54.0
56.8
50.6
49.4
58.1
78.0
78.0
73.7
43.0
43.5
41.5
36.0
51.0
48.5

and
2
Time
(%)
46.0
43.2
49.4
50.6
41.9
22.0
22.0
26.3
57.0
56.5
58.5
64.0
49.0
51.5

Max number of states
in DP2
Average
Max
(x103 )
(x103 )
0.1
0.2
0.1
0.5
0.8
16.0
1.6
20.5
2.8
56.2
1.8
6.8
2.1
19.6
2.6
14.9
5.1
36.1
13.4
58.9
4.9
25.2
7.6
47.8
0.9
3.2
2.3
7.5

Table 4: Numerical insights of the proposed exact approach for instances with 1000 items.

The results in the tables illustrate the effectiveness of the first step in solving
PKP instances. Usually more than 50% of the instances are solved to optimality
within this step. When both steps are involved, the computational effort is on
average equally distributed. We note however an increase of the percentages of
the second step in classes p5 and p6. The number of states is in general reasonably limited allowing our algorithm to effectively solve all instances considered.
The largest values of the number of states (with a maximum of about 3 millions)
are reached in the instances with 10000 items.
In the following we also list detailed results for all correlations and capacity
ratios.

21

Proposed exact approach
(n = 10000)
Profit
class
p1
p2
p3
p4
p5
p6
p7

Weight
type
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2
a1
a2

Step 1
only
#Opt
(%)
85.0
69.2
50.0
52.5
77.5
56.7
73.3
79.2
27.5
25.0
83.3
33.3
55.0
63.3

Step 1
Step
Time
(%)
79.1
62.3
68.3
48.6
58.0
90.1
74.5
83.8
39.3
39.2
32.0
26.8
60.3
60.2

and
2
Time
(%)
20.9
37.7
31.7
51.4
42.0
9.9
25.5
16.2
60.7
60.8
68.0
73.2
39.7
39.8

Max number of states
in DP2
Average
Max
(x103 )
(x103 )
0.7
6.3
1.5
5.5
3.4
66.2
19.5
166.1
146.3
1115.8
45.8
247.4
119.9
713.0
139.8
885.8
164.5
1244.3
444.4
3088.3
187.5
700.5
321.6
1292.2
81.1
493.3
145.6
764.9

Table 5: Numerical insights of the proposed exact approach for instances with 10000 items.

n = 1000
Weight
type
a1

τ
0.5

0.1

0.01

a2

0.5

0.1

0.01

Profit
class
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7

CPLEX 12.5
Average
Max
time (s)
time (s)
0.19
0.25
0.32
0.92
10.59
100.00
62.27
100.00
11.08
100.00
2.29
18.94
36.28
100.00
0.20
0.25
0.49
1.13
0.54
1.44
74.13
100.00
0.93
10.24
4.23
90.38
28.61
100.00
0.14
0.18
0.35
1.69
0.58
8.34
42.27
100.00
0.38
3.65
1.48
4.05
17.87
100.00
0.18
0.32
0.47
3.19
10.66
100.00
53.29
100.00
23.32
100.00
4.65
13.57
17.76
100.00
0.22
0.33
1.52
6.32
3.40
41.67
87.51
100.00
10.75
100.00
1.91
5.30
35.62
100.00
0.18
0.48
1.38
4.26
6.43
18.53
60.12
100.00
10.84
60.54
2.36
6.48
61.34
100.00

#Opt
40
40
37
16
37
40
26
40
40
40
11
40
40
29
40
40
40
30
40
40
34
40
40
37
19
36
40
33
40
40
40
6
38
40
26
40
40
40
21
40
40
16

Algorithm in [1]
Average
Max
time (s)
time (s)
#Opt
0.00
0.00
40
0.00
0.01
40
0.10
0.89
40
0.14
1.34
40
0.09
0.89
40
0.00
0.00
40
0.00
0.01
40
0.00
0.01
40
0.00
0.00
40
0.02
0.11
40
0.12
1.38
40
0.01
0.06
40
0.00
0.01
40
0.00
0.01
40
0.00
0.01
40
0.00
0.00
40
0.00
0.03
40
0.04
0.20
40
0.00
0.01
40
0.00
0.06
40
0.00
0.01
40
0.00
0.00
40
0.00
0.01
40
0.89
8.02
40
0.50
7.75
40
0.65
4.50
40
0.00
0.01
40
0.00
0.01
40
0.00
0.00
40
0.00
0.01
40
0.41
2.17
40
0.31
7.30
40
0.38
1.63
40
0.00
0.08
40
0.01
0.03
40
0.00
0.01
40
0.00
0.01
40
0.20
1.17
40
0.04
0.14
40
0.19
0.84
40
0.03
0.15
40
0.01
0.06
40

Proposed exact approach
Average
Max
time (s)
time (s)
#Opt
0.00
0.00
40
0.00
0.10
40
0.03
0.40
40
0.02
0.05
40
0.04
0.20
40
0.00
0.02
40
0.00
0.01
40
0.00
0.00
40
0.00
0.05
40
0.01
0.04
40
0.02
0.18
40
0.01
0.05
40
0.00
0.03
40
0.01
0.02
40
0.00
0.00
40
0.00
0.01
40
0.00
0.01
40
0.01
0.03
40
0.00
0.01
40
0.00
0.01
40
0.00
0.02
40
0.00
0.00
40
0.00
0.00
40
0.03
0.11
40
0.04
0.11
40
0.12
1.40
40
0.02
0.08
40
0.01
0.03
40
0.00
0.00
40
0.01
0.27
40
0.03
0.29
40
0.04
0.26
40
0.07
0.38
40
0.01
0.04
40
0.01
0.07
40
0.00
0.03
40
0.00
0.01
40
0.02
0.03
40
0.03
0.05
40
0.02
0.04
40
0.01
0.07
40
0.02
0.06
40

Table 6: Computational results for instances with 1000 items and different correlations between profits and weights: time (s) and number of optima over 40 instances.

22

n = 10000
Weight
type
a1

τ
0.5

0.1

0.01

a2

0.5

0.1

0.01

Profit
class
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7
p1
p2
p3
p4
p5
p6
p7

CPLEX 12.5
Average
Max
time (s)
time (s)
1.00
2.28
3.73
9.40
62.62
100.00
82.03
100.00
53.44
100.00
90.65
100.00
21.31
100.00
1.12
2.68
11.05
33.84
55.29
100.00
95.24
100.00
20.70
100.00
77.25
100.00
64.61
100.00
0.73
1.28
1.45
2.74
15.92
100.00
97.53
100.00
2.22
6.56
81.35
100.00
67.09
100.00
1.93
11.22
3.86
11.72
70.77
100.00
86.05
100.00
60.26
100.00
86.29
100.00
14.30
100.00
1.27
2.19
10.99
29.04
66.31
100.00
98.01
100.00
54.25
100.00
82.95
100.00
51.33
100.00
9.37
100.00
22.45
100.00
85.32
100.00
100.00
100.00
83.47
100.00
73.90
100.00
54.74
100.00

#Opt
40
40
16
8
20
12
33
40
40
21
2
35
24
15
40
40
37
1
40
22
15
40
40
18
6
19
7
36
40
40
19
1
21
13
20
37
34
9
0
8
24
19

Algorithm in [1]
Average
Max
time (s)
time (s)
#Opt
0.01
0.02
40
0.01
0.02
40
45.29
100.00
23
17.43
100.00
34
24.99
100.00
33
0.01
0.06
40
0.09
0.33
40
0.01
0.01
40
0.01
0.02
40
26.62
100.00
33
16.64
100.00
37
6.24
78.90
40
0.09
1.97
40
0.27
0.94
40
0.00
0.01
40
0.00
0.02
40
4.86
59.95
40
18.97
100.00
35
0.86
7.79
40
1.91
40.17
40
0.14
0.56
40
0.01
0.02
40
0.01
0.02
40
53.23
100.00
23
24.86
100.00
35
24.30
100.00
32
0.08
0.95
40
0.31
2.23
40
0.01
0.02
40
0.01
0.02
40
50.95
100.00
24
34.25
100.00
35
27.97
100.00
35
0.29
1.47
40
0.77
3.94
40
0.01
0.04
40
0.01
0.07
40
40.59
100.00
27
19.92
100.00
36
18.96
100.00
34
10.50
100.00
39
0.55
3.47
40

Proposed exact approach
Average
Max
time (s)
time (s)
#Opt
0.02
0.03
40
0.02
0.03
40
6.65
58.46
40
2.79
10.73
40
7.16
70.71
40
0.23
2.56
40
0.15
0.51
40
0.01
0.02
40
0.02
0.13
40
1.02
8.73
40
3.54
18.88
40
0.76
6.13
40
0.33
5.38
40
0.57
2.26
40
0.00
0.01
40
0.01
0.02
40
0.12
1.00
40
2.10
14.20
40
0.07
0.56
40
0.11
1.69
40
0.54
2.50
40
0.02
0.02
40
0.02
0.03
40
8.09
25.55
40
8.72
26.06
40
9.93
58.60
40
2.62
16.65
40
0.48
3.34
40
0.01
0.02
40
0.04
0.66
40
4.33
14.29
40
11.28
80.02
40
5.97
40.59
40
2.28
7.87
40
1.83
11.46
40
0.01
0.03
40
0.06
0.73
40
4.18
29.00
40
3.46
15.36
40
5.22
20.51
40
0.96
3.90
40
1.92
8.74
40

Table 7: Computational results for instances with 10000 items and different correlations
between profits and weights: time (s) and number of optima over 40 instances.

23

n = 1000
Weight
type
a1

τ
0.5

0.1

0.01

a2

0.5

0.1

0.01

Penalty
class
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8

CPLEX 12.5
Average
Max
time (s)
time (s)
6.65
100.00
16.33
100.00
19.56
100.00
21.98
100.00
22.95
100.00
25.89
100.00
15.49
100.00
11.73
100.00
7.53
100.00
15.01
100.00
29.18
100.00
17.96
100.00
18.44
100.00
12.68
100.00
17.93
100.00
5.98
100.00
0.70
3.83
7.19
100.00
7.52
100.00
20.09
100.00
16.57
100.00
3.37
30.16
15.94
100.00
0.70
8.34
10.77
100.00
16.60
100.00
22.18
100.00
19.38
100.00
21.57
100.00
11.32
100.00
9.68
100.00
14.59
100.00
14.78
100.00
21.28
100.00
18.82
100.00
30.67
100.00
25.16
100.00
28.61
100.00
10.08
100.00
11.68
100.00
1.60
12.74
28.11
100.00
26.29
100.00
19.68
100.00
33.97
100.00
24.26
100.00
17.34
100.00
11.77
100.00

#Opt
33
30
29
28
28
27
30
31
33
30
25
29
29
31
30
33
35
33
34
30
32
35
30
35
32
31
29
30
29
32
32
30
32
28
29
25
27
26
32
31
35
28
28
31
25
29
30
31

Algorithm in [1]
Average
Max
time (s)
time (s)
#Opt
0.01
0.05
35
0.02
0.14
35
0.08
0.89
35
0.03
0.39
35
0.05
0.38
35
0.04
0.89
35
0.09
1.34
35
0.06
0.63
35
0.00
0.05
35
0.01
0.08
35
0.01
0.08
35
0.01
0.06
35
0.01
0.09
35
0.01
0.11
35
0.09
1.38
35
0.03
0.58
35
0.00
0.00
35
0.00
0.03
35
0.00
0.05
35
0.01
0.05
35
0.01
0.05
35
0.00
0.01
35
0.02
0.20
35
0.01
0.09
35
0.02
0.14
35
0.08
1.07
35
0.42
4.57
35
0.51
7.81
35
0.28
3.00
35
0.47
8.02
35
0.49
7.75
35
0.05
0.80
35
0.02
0.17
35
0.04
0.30
35
0.22
2.16
35
0.28
2.17
35
0.22
1.98
35
0.19
1.63
35
0.26
7.30
35
0.04
0.44
35
0.00
0.01
35
0.01
0.14
35
0.15
0.73
35
0.11
1.17
35
0.10
0.67
35
0.12
0.84
35
0.02
0.10
35
0.02
0.16
35

Proposed exact approach
Average
Max
time (s)
time (s)
#Opt
0.01
0.03
35
0.01
0.12
35
0.02
0.14
35
0.01
0.06
35
0.01
0.10
35
0.01
0.05
35
0.01
0.03
35
0.03
0.40
35
0.01
0.18
35
0.01
0.08
35
0.01
0.03
35
0.01
0.03
35
0.01
0.03
35
0.00
0.04
35
0.01
0.05
35
0.01
0.05
35
0.00
0.01
35
0.01
0.03
35
0.00
0.03
35
0.01
0.03
35
0.00
0.03
35
0.00
0.01
35
0.00
0.01
35
0.00
0.01
35
0.02
0.17
35
0.07
1.40
35
0.04
0.32
35
0.03
0.21
35
0.03
0.28
35
0.03
0.23
35
0.02
0.11
35
0.01
0.09
35
0.05
0.38
35
0.02
0.22
35
0.03
0.27
35
0.03
0.13
35
0.02
0.12
35
0.02
0.09
35
0.02
0.11
35
0.01
0.07
35
0.01
0.03
35
0.01
0.04
35
0.02
0.05
35
0.02
0.05
35
0.02
0.05
35
0.02
0.06
35
0.01
0.03
35
0.00
0.02
35

Table 8: Computational results for instances with 1000 items and different correlations between penalties and weights: time (s) and number of optima over 35 instances.

24

n = 10000
Weight
type
a1

τ
0.5

0.1

0.01

a2

0.5

0.1

0.01

Penalty
class
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8
π1
π2
π3
π4
π5
π6
π7
π8

CPLEX 12.5
Average
Max
time (s)
time (s)
26.96
100.00
51.68
100.00
45.50
100.00
52.72
100.00
54.65
100.00
55.55
100.00
38.21
100.00
34.49
100.00
27.19
100.00
48.67
100.00
54.65
100.00
59.08
100.00
57.49
100.00
51.93
100.00
48.77
100.00
23.95
100.00
21.36
100.00
37.31
100.00
45.55
100.00
45.75
100.00
49.01
100.00
44.44
100.00
38.94
100.00
21.96
100.00
50.50
100.00
51.30
100.00
46.81
100.00
55.72
100.00
52.02
100.00
47.85
100.00
37.68
100.00
27.78
100.00
46.84
100.00
49.39
100.00
57.48
100.00
60.68
100.00
73.48
100.00
57.68
100.00
41.52
100.00
30.19
100.00
61.19
100.00
60.12
100.00
65.69
100.00
77.25
100.00
73.10
100.00
60.01
100.00
58.23
100.00
34.99
100.00

#Opt
29
18
20
17
17
16
25
27
28
22
18
17
19
21
22
30
30
26
21
21
21
23
22
31
18
18
21
19
19
21
24
26
21
21
18
18
10
18
22
26
16
19
14
10
12
18
17
25

Algorithm in [1]
Average
Max
time (s)
time (s)
#Opt
1.07
8.74
35
4.93
100.00
34
8.83
100.00
33
24.28
100.00
28
18.01
100.00
29
23.99
100.00
27
11.72
100.00
31
7.54
100.00
33
0.88
18.70
35
2.17
20.73
35
7.52
100.00
33
15.20
100.00
32
8.46
100.00
34
7.55
100.00
34
11.15
100.00
32
4.07
73.67
35
0.17
3.00
35
6.20
73.05
35
2.26
33.15
35
2.36
59.95
35
1.25
10.15
35
1.28
26.15
35
13.75
100.00
31
3.30
100.00
34
4.70
44.55
35
16.08
100.00
30
19.17
100.00
29
14.48
100.00
32
20.40
100.00
30
18.55
100.00
29
11.97
100.00
32
12.14
100.00
33
11.89
100.00
33
15.23
100.00
34
21.44
100.00
29
19.71
100.00
31
23.79
100.00
29
23.00
100.00
31
8.76
100.00
33
6.75
100.00
34
2.94
26.59
35
5.40
49.36
35
15.40
100.00
31
16.77
100.00
30
17.29
100.00
30
16.08
100.00
30
24.62
100.00
30
4.95
51.47
35

Proposed exact approach
Average
Max
time (s)
time (s)
#Opt
1.04
10.54
35
0.89
8.74
35
1.06
5.78
35
2.22
17.67
35
1.66
10.09
35
2.46
20.65
35
1.08
10.73
35
9.05
70.71
35
0.72
18.88
35
0.70
6.27
35
1.30
18.19
35
0.91
7.16
35
1.00
8.53
35
0.39
2.26
35
0.85
8.59
35
1.27
8.73
35
0.31
6.57
35
0.58
5.66
35
0.28
3.69
35
0.33
2.50
35
0.46
5.62
35
0.58
14.20
35
0.47
3.36
35
0.35
6.39
35
2.91
17.61
35
4.55
53.64
35
5.14
42.97
35
4.80
58.60
35
4.84
29.21
35
4.29
39.81
35
3.61
25.55
35
4.02
26.06
35
3.47
41.73
35
3.55
40.59
35
4.78
28.76
35
3.62
19.90
35
4.05
14.26
35
6.56
80.02
35
1.70
7.87
35
1.70
15.50
35
3.98
29.00
35
3.37
20.51
35
1.87
12.09
35
2.39
13.24
35
2.08
11.25
35
1.71
8.97
35
1.70
6.82
35
0.97
6.53
35

Table 9: Computational results for instances with 10000 items and different correlations
between penalties and weights: time (s) and number of optima over 35 instances.

6. Approximation results
In this section we investigate the approximability of PKP. The classical 0–1
Knapsack Problem admits fully polynomial time approximation schemes (FPTAS), see, e.g. [3]. PKP has “only” an additional penalty to consider in the
objective with respect to KP. Thus, one might expect some straightforward approximation algorithm for this problem as well. Nonetheless, we prove here the
general result that no polynomial time approximation algorithm exists for PKP
(under P 6= N P).
Theorem 11. PKP does not admit a polynomial time algorithm with a bounded
approximation ratio unless P = N P.
Proof. The theorem is proved by reduction from the Subset Sum Problem (SSP).
Given n items with integer weights wj′ (j = 1, . . . , n) and a value W ′ (with
25

Pn

wj′ > W ′ ), we recall that the decision version of SSP is an NP–complete
problem
whether there exists a subset of items represented by x∗ such
Pn and ′asks
∗
that j=1 wj xj = W ′ .
We build an instance of PKP with n items, profits and weights pj = wj = wj′ ,
penalties πj = W ′ − 1 (j = 1, . . . , n ) and capacity c = W ′ .PThe capacn
ity constraint implies that for every feasible solution there is
j=1 pj xj =
Pn
′
′
w
x
≤
W
.
The
penalty
value
will
be
equal
to
either
W
− 1 if we
j=1 j j
pack at least one item or 0 otherwise,
therefore
the
optimal
solution
of this
Pn
PKP instance is bounded by j=1 pj xj − (W ′ − 1) ≤ 1. Not placing any item
in the knapsack attains the trivial solution with value equal to 0. By integrality
of the input data, this limits the optimal solution value to 0 or 1, where the
latter value can be reached if and only if the Subset Sum Problem has a solution.
Hence, if there was a polynomial time algorithm for PKP with a bounded
approximation ratio, we could decide SSP just by checking if the approximate
solution of PKP is strictly positive. Clearly this is not possible unless P =
N P.
j=1

While the result of Theorem 11 rules out any reasonable approximation for
the general case, one can impose mild restrictions on the input data which still
permit fully polynomial time approximation algorithms. All our results are
based on the following simple approximation algorithm: Similar to the exact
algorithm sketched in Section 2 we consider all n choices for the penalty value,
namely Π ∈ {π1 , . . . , πn }. For each choice j of the leading item with Π = πj , we
compute a suboptimal solution of problem P KPj+ by packing item j into the
knapsack and applying a (1 − δ)−approximation algorithm for the remaining
knapsack problem with capacity c − wj and item set {j + 1, . . . , n}. The optimal
solution value of the latter problem will be denoted as zjR .
As an output of the resulting approximation algorithm A(δ) with objective
function value z A (δ) we use the maximum value obtained over all n iterations
(including the empty set). For a constant δ > 0, algorithm A(δ) can be performed by running n times an FPTAS for KP. Note that if z ∗ = 0, then also
A(δ) will output a value of 0. Thus we can assume by integrality of the input
data:
(31)
z ∗ = pj ∗ + zjR∗ − πj ∗ ≥ 1.
As a general bound on the performance of A(δ) we get:
z A (δ)

≥

pj ∗ + (1 − δ)zjR∗ − πj ∗

=

(1 − ε)z ∗ + (ε − δ)zjR∗ − ε(πj ∗ − pj ∗ )

Hence, we obtain an FPTAS for a suitable choice of δ ≤ ε if we can prove:
(ε − δ)zjR∗ ≥ ε(πj ∗ − pj ∗ )

(32)

Note that whenever inequality pj ∗ ≥ πj ∗ is implied, condition (32) is trivially
satisfied for any δ ≤ ε.
In the following we will describe four relevant cases which all permit an FPTAS
26

for PKP. We start with the case where each item has a profit greater than (or
equal to) its penalty value.
Proposition 12. If pj ≥ πj for j = 1, . . . , n, then algorithm A(δ) is an FPTAS
for PKP.
Proof. It is trivial to see that setting δ := ε the right-hand side of (32) is
always less than (or equal to) zero for every j and thus the inequality is always
fulfilled.
We henceforth assume the restricting condition πj ∗ − pj ∗ ≥ 0. We first
consider the case where penalties are bounded by a given constant C.
Proposition 13. If πj + 1 ≤ C for j = 1, . . . , n and a constant C, algorithm
A(δ) constitutes an FPTAS.
Proof. We can choose δ :=
We have that:
(ε − δ)zjR∗

ε
C

≥
=
≥
=
≥

and consider from (31) that zjR∗ ≥ πj ∗ − pj ∗ + 1.
(ε − δ)(πj ∗ − pj ∗ + 1)
ε
ε(πj ∗ − pj ∗ + 1) − (πj ∗ − pj ∗ + 1)
C
ε
ε(πj ∗ − pj ∗ ) + ε − (C − pj ∗ + 1)
C
ε
ε(πj ∗ − pj ∗ ) + (pj ∗ − 1)
C
ε(πj ∗ − pj ∗ )

(33)
(34)
(35)
(36)
(37)

The last inequality (37) follows from the integrality of profits. Hence, condition
(32) is shown.
As generalization of the case in Proposition 12, we consider for each item
smaller profits than penalties and manage to derive an FPTAS as long as this
difference is bounded by a constant.
Proposition 14. PKP admits an FPTAS if πj − pj ≤ C for j = 1, . . . , n and
a constant C.
Proof. By choosing δ :=
(ε − δ)zjR∗

ε
C+1

we get:

ε
)z R∗
C+1 j
ε
)z R∗
≥ (ε −
πj ∗ − pj ∗ + 1 j
ε
≥ (ε −
)(πj ∗ − pj ∗ + 1)
πj ∗ − pj ∗ + 1
= ε(πj ∗ − pj ∗ ) + ε − ε
= (ε −

For inequality (40) we invoke again (31). This shows condition (32).

27

(38)
(39)
(40)
(41)

Finally, consider the case where there exists a bounded interval containing all
profit and penalty values. This can be expressed by assuming a constant parameter ρ ∈ (1/2, 1) with pmin ≥ ρ · πmax , i.e. all profits are not too small compared
to the largest penalty. On the other hand, profits can well be arbitrarily large.
The following proposition holds.
Proposition 15. There is an FPTAS for PKP if pmin ≥ ρ · πmax with ρ ∈
(1/2, 1).
Proof. If the optimal solution consists only of the leading item, then A(δ) also
yields the optimum. Thus, we have zjR∗ ≥ pmin ≥ ρ πmax . Choosing δ := ε 2ρ−1
ρ
(note that δ > 0 for ρ > 1/2) we get:
(ε − δ)zjR∗

≥

(42)

=
=

(ε − δ)ρ πmax
2ρ − 1
(ε − ε
)ρ πmax
ρ
(ερ − 2ερ + ε)πmax
ε(1 − ρ)πmax

≥
≥

ε(πmax − pmin )
ε(πj ∗ − pj ∗ )

(46)
(47)

=

(43)
(44)
(45)

This shows again condition (32).
We remark that, although we cannot exclude other approximation schemes
for PKP, it seems hard to construct any meaningful approximation algorithm
different from A(δ). The algorithm considers each term pj − πj explicitly and
thus will also include the part of the optimal solution value contributed by
the leading item pj ∗ − πj ∗ . Then, the knapsack problem zjR∗ is solved by a
(1 − δ)−approximation with a suitably chosen parameter δ which is the best
one can do for the remaining sub–problem.
7. Conclusions
We proposed a dynamic programming based exact approach for PKP which
leverages an algorithmic framework originally constructed for KP. The proposed
approach turns out to be very effective in solving instances of the problem with
up to 10000 items and favorably compares to both solver CPLEX 12.5 and an
exact algorithm in the literature. From a theoretical point of view we also show
that PKP can be solved in the same pseudopolynomial running time O(nc) as
the standard knapsack problem. We also gave further insights on the structure
and properties of PKP by providing a characterization of its linear relaxation
and an effective procedure to compute upper bounds on the problem. By studying the approximability of PKP, we showed rather surprisingly that there is no
polynomial time approximation algorithm with bounded approximation ratio,
while imposing some mild conditions on the input of PKP allows an FPTAS.
In future research, we will investigate extensions of our procedures to other KP
28

generalizations. It would also be interesting to evaluate the performances of our
approach on new benchmark and challenging PKP instances.
Acknowledgments
We thank the authors of [1] for providing us with the code of their algorithm
and the generation scheme of the instances.
Rosario Scatamacchia was supported by a fellowship from TIM Joint Open
Lab SWARM (Turin, Italy). Ulrich Pferschy was supported by the University
of Graz project ”Choice-Selection-Decision”.
References
[1] A. Ceselli and G. Righini. An optimization algorithm for a penalized knapsack problem. Operations Research Letters, 34:394–404, 2006.
[2] R. S. Dembo and P. L. Hammer. A reduction algorithm for knapsack problems. Methods of Operations Research, 36:49–60, 1980.
[3] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer,
2004.
[4] A. Lodi, S. Martello, and M. Monaci. Two–dimensional packing problems:
a survey. European Journal of Operational Research, 141:241–252, 2002.
[5] S. Martello, D. Pisinger, and P. Toth. New trends in exact algorithms for the
0–1 knapsack problems. European Journal of Operational Research, 123:325–
332, 2000.
[6] S. Martello and P. Toth. A new algorithm for the 0–1 knapsack problem.
Management Science, 34:633–644, 1988.
[7] S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer
Implementations. Wiley, 1990.
[8] D. Pisinger. A minimal algorithm for the 0–1 knapsack problem. Operations
Research, 45:758–767, 1997.
[9] D. Pisinger. Linear time algorithms for knapsack problems with bounded
weights. Journal of Algorithms, 33:1–14, 1999.

29

