Approximation issues of fractional knapsack with penalties: a note

Abstract

Malaguti et al. introduce (Eur J Oper Res 273:874–888, 2019) the Fractional Knapsack Problem with Penalties, which is similar to the classical 0-1 Knapsack problem, except that each of the n variables associated with one of the n items can take any value from the interval [0, 1], and values other than 0 and 1 are penalized. They state that the problem is NP-hard in the ordinary sense as a generalization of the classical 0-1 knapsack problem and develop a fully polynomial-time approximation scheme for the case of non-negative non-decreasing profit functions. It is demonstrated that, unless $\mathcal P=NP$, no polynomial-time approximation algorithm with any approximation ratio exists for the case of polynomially defined, polynomially computable, discontinuous and non-monotone penalty functions even if there is a single item. A fully polynomial-time approximation scheme which is roughly n times faster than the one of Malaguti et al. for the same case is also presented.

1 Introduction

Malaguti et al. (2019) study the following Fractional Knapsack Problem with Penalties (FKPP). There are items of a set $N=\{1,\ldots ,n\}$ and a knapsack with weight capacity $W>0$. Any part of an item can be packed into the knapsack. Let variable $x_j$, $0\le x_j\le 1$, represent the part of the item j packed into the knapsack. Each item $j\in N$ is associated with a weight $w_j>0$, a full-size-item profit $p_j>0$ and a profit function

$$\begin{aligned} F_j(x_j)={\left\{ \begin{array}{ll} 0 &{} \text{ if } x_j=0, \\ p_j &{} \text{ if } x_j=1, \\ p_jx_j-f_j(x_j) &{} \text{ if } 0<x_j<1, \end{array}\right. } \end{aligned}$$

where $f_j(x_j)$ is an arbitrary, even discontinuous, non-negative penalty function applied when a fractional part of the item j is packed into the knapsack. Denote $x=(x_1,\ldots ,x_n)$. The FKPP problem is

$$\begin{aligned}&\max _{x} \sum _{j\in N} F_j(x_j),\hbox { subject to }\\&\sum _{j\in N} w_jx_j\le W, \\&0\le x_j\le 1, j\in N. \end{aligned}$$

Note that, in the classical knapsack problem, relations $w_j\le W$, $j\in N$, can be assumed, because if $w_j>W$, then item j cannot be packed into the knapsack, and hence, it can be removed from the input. In FKPP, if $w_j>W$, then a part of item j can still be packed into the knapsack, and therefore, relations $w_j\le W$, $j\in N$, are restrictive. Assume that in FKPP weights $w_j$, $j\in N$, are not bounded from above by W.

Let $\varepsilon$ be a number or a function of the input data of FKPP such that $0<\varepsilon <1$. An algorithm for a maximization problem is called an $(1-\varepsilon )$ -approximation algorithm if for any instance of the problem it finds a feasible solution with value $H^0\ge H^*-\varepsilon |H^*|$, where $H^*$ is the maximum value. The absolute value of $H^*$ is used in this definition because $H^*$ can be negative. A Fully Polynomial-Time Approximation Scheme (FPTAS) for a maximization problem is a collection of $(1-\varepsilon )$-approximation algorithms $\{A_\varepsilon \}$ each of which runs in time bounded by a polynomial of $1/\varepsilon$ and of the problem input length in binary encoding.

Malaguti et al. (2019) remark that FKPP is an NP-hard problem since the classical 0-1 knapsack problem reduces to it by setting $f_j(x_j)=p_jx_j$, $j\in N$. They concentrate on a special case of FKPP, in which $F_j(x_j)$, $j\in N$, are non-negative non-decreasing functions. For this case, among other results, they develop an FPTAS with running time $O(n^4/\varepsilon ^2)$.

Earlier publications, in which optimization problems with penalized item splitting are studied, include Freling et al. (2003), Liu and Cheng (2004), Lodi et al. (2011), Archetti and Speranza (2012), Malaguti et al. (2014), Casazza and Ceselli (2014), Fung (2014) and Liu and Draper (2016).

In the next section, it is proved that, unless $\mathcal P=NP$, no polynomial-time $(1-\varepsilon )$-approximation algorithm exists for FKPP even if $n=1$ and the penalty function $f_1(x_1)$ is polynomially defined, polynomially computable, discontinuous and non-monotone. It is shown that this statement also applies for the general FKPP with an arbitrary number of items. Section 3 contains an $O(n^3\log _2n+n^3/\varepsilon ^2)$ time FPTAS for FKPP with non-negative non-decreasing profit functions.

2 Non-approximability

The non-approximability proof is similar to the NP-hardness proof of Cheng and Kovalyov (2002) for an unconstrained optimization problem.

Theorem 1

Unless $\mathcal P=NP$, no polynomial-time $(1-\varepsilon )$-approximation algorithm with any $0<\varepsilon <1$ exists for FKPP even if $n=1$ and the penalty function $f_1(x_1)$ is polynomially computable, polynomially defined, discontinuous and non-monotone.

Proof

Firstly, it is shown that the decision version of FKPP in the statement of the theorem is NP-complete by a transformation from the NP-complete problem Partition (Garey and Johnson 1979): Given positive integers $a_1,\ldots ,a_k$ and A such that $\sum ^k_{i=1}a_i=2A$, is there a 0-1 vector $y=(y_1,\ldots ,y_k\}$, $y\not \in \{(0,\ldots ,0),(1,\ldots ,1)\}$, such that $\sum _{i=1}^k a_iy_i=A$?

Given any instance of Partition, construct the following instance of FKPP. Set $n=1$, $p_1=2(2^k-1)$, $w_1=2$ and $W=1$. Let b(z) denote a binary representation of z, $z\in \{1,2,\ldots ,\frac{p_1}{2}\}$, using k bits, $b(z)=(b_1(z),\ldots ,b_k(z))$, $b_i(z)\in \{0,1\}$, $i=1,\ldots ,k$, such that $z=\sum _{i=1}^k 2^{k-i} b_i(z)$. Define

$$\begin{aligned} f_1(x_1)={\left\{ \begin{array}{ll} p_1x_1-1+|\sum _{i=1}^k a_ib_i(\lfloor p_1x_1\rfloor )-A| &{} \text{ if } x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,\frac{p_1}{2}\} \\ p_1x_1 &{} \text{ if } x_1\in \{\frac{q}{p_1}\mid q=\frac{p_1}{2}+1,\ldots ,p_1\}. \end{array}\right. } \end{aligned}$$

Domain of the function $f_1(x_1)$ is the discrete set $\{\frac{q}{p_1}\mid q=1,\ldots ,p_1\}$. It is easy to see that the function $p_1(x_1)$ is polynomially defined, polynomially computable, discontinuous and non-monotone. Furthermore, the length of $p_1$ in binary encoding is O(k). The value $\lfloor p_1x_1\rfloor$ and the binary representation $b(\lfloor p_1x_1\rfloor )$ for any $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,\frac{p_1}{2}\}$ can be found in O(k) time. Using $b(\lfloor p_1x_1\rfloor )$, the value $f_1(x_1)$ can be calculated in O(k) time as well. Therefore, the reduction is polynomial with respect to the input length of the Partition instance. Clearly, $f_1(x_1)\ge 0$ for $0<x_1<1$, as it is required by the definition of FKPP.

Since $f_1(x_1)$ is polynomially computable and defined for $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,p_1\}$, the variable value of q in $x_1=\frac{q}{p_1}$ can be taken as a certificate to verify whether a decision version of FKPP has a solution. The length of such a certificate is bounded by a polynomial of $\log p_1$. It is deduced that a decision version of FKPP is in the class $\mathcal NP$. The transformation is the following.

It is shown that an instance of Partition has a solution if and only if for the associated instance of FKPP there exists a solution $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,p_1\}$ such that $F_1(x_1)\ge 1$ and $w_1x_1\le W$. Observe that the definitions of the functions $f_1(x_1)$ and $F_1(x_1)$ imply that the values $F_1(x_1)$ are integral. Assume that the instance of Partition has a solution $y=(y_1,\ldots ,y_k)$, $y_i\in \{0,1\}$, $i=1,\ldots ,k$. Define $z=\sum _{i=1}^k 2^{k-i} y_i\ge 1$ and $x_1=\frac{z}{p_1}$. Observe that $1\le p_1x_1=z\le 2^k-1=\frac{p_1}{2}$. Hence, $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,\frac{p_1}{2}\}$ and $w_1x_1=2x_1\le 1=W$. Furthermore,

$$\begin{aligned} F_1(x_1)= & {} 1-\Big |\sum _{i=1}^k a_ib_i(\lfloor p_1x_1\rfloor )-A\Big |= 1-\Big |\sum _{i=1}^k a_ib_i(z)-A\Big |\\= & {} 1-\Big |\sum _{i=1}^k a_iy_i-A\Big |=1. \end{aligned}$$

It was shown that the constructed instance of FKPP has a solution if the associated instance of Partition has a solution. Now, assume that the instance of FKPP has a solution $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,p_1\}$ such that $F_1(x_1)\ge 1$ and $w_1x_1\le W$. These relations imply that $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,\frac{p_1}{2}\}$, $\lfloor p_1x_1\rfloor \le p_1/2\le 2^k-1$ and $F_1(x_1)=1-|\sum _{i=1}^k a_ib_i(\lfloor p_1x_1\rfloor )-A|\ge 1$. The latter relation can only happen if $\sum _{i=1}^k a_ib_i(\lfloor p_1x_1\rfloor )=A$. It is deduced that the 0-1 vector y such that $y_i=b_i(\lfloor p_1x_1\rfloor )$, $i=1,\ldots ,k$, is a solution of the associated instance of Partition.

Thus, FKPP is NP-hard if $n=1$ and the penalty function $f_1(x_1)$ is polynomially computable, polynomially defined, discontinuous and non-monotone. Assume that $0<\varepsilon <1$ and there exists a $(1-\varepsilon )$-approximation algorithm for FKPP. Let it deliver a solution $x^0_1$ with value $F^0_1$ for the FKPP instance associated with a Partition instance. Since $w_1x^0_1=2x^0_1\le W=1$, we know that $x_1\in \{\frac{q}{p_1}\mid q=1,\ldots ,\frac{p_1}{2}\}$. Together with the definitions of the functions $f_1(x_1)$ and $F_1(x)$, this implies that $F^0_1$ is an integer satisfying $F^0_1\le 1$. Denote by $F^*_1$ the maximum objective function value for the instance of FKPP. Similar to $F^0_1$, the number $F^*_1$ is an integer satisfying $F^*_1\le 1$. By the definition of an $(1-\varepsilon )$-approximation algorithm, relations

$$\begin{aligned} F^*_1-\varepsilon |F^*_1|\le F^0_1\le F^*_1 \end{aligned}$$

(1)

must be satisfied.

It is shown in the above NP-completeness proof that if $F^*_1=1$, then the Partition instance has a solution, and if $F^*_1\le 0$, then the Partition instance has no solution. It follows from (1), relation $0<\varepsilon <1$ and integrality of $F^0_1$ and $F^*_1$ that $F^0_1=1$ if and only if $F^*_1=1$. It is deduced that $F^0_1=1$ if and only if the Partition instance has a solution. Thus, if a polynomial-time $(1-\varepsilon )$-approximation algorithm for FKPP exists, then Partition admits a polynomial-time algorithm, which is impossible, unless $\mathcal P=NP$. $\square$

Corollary 1

Unless $\mathcal P=NP$, no polynomial-time $(1-\varepsilon )$-approximation algorithm with any $0<\varepsilon <1$ exists for FKPP.

Proof

For any instance $I_1$ of FKPP in the proof of Theorem 1, construct an instance $I_2$ of the general FKPP, in which $W=1$, $n=\log _2 p_1$, all the input parameters of item 1 are the same as in $I_1$, $w_j=0$ and $f_j(x_j)=p_j=0$ for $0\le x_j\le 1$, $j=2,\ldots ,n$. The transformation of $I_1$ into $I_2$ is polynomial in the input length of $I_1$. The remaining proof is similar to the proof of Theorem 1. $\square$

3 Non-negative non-decreasing profit functions: FPTAS

Consider FKPP with non-negative non-decreasing profit functions $F_j(x_j)$, $j\in N$. Similar to the FPTAS of Malaguti et al. (2019), the present FPTAS is based on a scaled and rounded re-formulation of FKPP and a dynamic programming algorithm for the latter problem. However, the current re-formulation is different from that in Malaguti et al. (2019), which results in a more efficient running time.

Let $x^*=(x^*_1,\ldots ,x^*_n)$ be an optimal solution of FKPP and $F^*=\sum _{j\in N} F_j(x^*_j)$. Observe that any 0-1 vector $x^{(j)}$ such that $x^{(j)}_j=\min \{1,\frac{W}{w_j}\}$ and $x^{(j)}_i=0$, $i\ne j$, $i\in N$, $j\in N$, is feasible for FKPP. Hence, $L'=\max _{j\in N}\{F_j(\min \{1,\frac{W}{w_j}\})\}$ is a lower bound for $F^*$. Furthermore, if $F_j(\min \{1,\frac{W}{w_j}\})=0$, then, since $F_j$ is non-negative and non-decreasing, the contribution of item j to the objective function is zero in any feasible solution, and this item can be removed from the input. Therefore, assume without loss of generality that $F_j(\min \{1,\frac{W}{w_j}\})>0$, $j\in N$. One more observation is that $F_j(\min \{1,\frac{W}{w_j}\})$ is the maximum contribution of item j to the objective function value of any feasible solution because the functions $F_j(x_j)$ are non-decreasing, $j\in N$. It follows that $U'=nL'$ is an upper bound on $F^*$.

From now on assume that arbitrary lower and upper bounds L and U are known such that $0<L'\le L\le F^*\le U\le U'$. For a given $\varepsilon >0$, define scaling parameter $\delta =\frac{\varepsilon L}{n}$ and formulate the following Scaled and Rounded FKPP (SRK) problem.

$$\begin{aligned}&\max _{x} \sum _{j\in N} \Big \lfloor \frac{F_j(x_j)}{\delta }\Big \rfloor , \text{ subject } \text{ to }\\&\sum _{j\in N} w_jx_j\le W, \\&x_j\in \{r_j(0),r_j(1),\ldots ,r_j(\Big \lfloor \frac{U}{\delta }\Big \rfloor )\}, j\in N, \end{aligned}$$

where

$$\begin{aligned}&r_j(s)=\inf \Big \{ x\mid 0\le x\le \min \Big \{1,\frac{W}{w_j}\Big \}, \Big \lfloor \frac{F_j(x)}{\delta }\Big \rfloor =s\Big \}=\\&\inf \Big \{ x\mid 0\le x\le \min \Big \{1,\frac{W}{w_j}\Big \}, s\delta \le F_j(x)< (s+1)\delta \Big \}, j\in N. \end{aligned}$$

Note that, by the definition of the infimum, the value $r_j(s)$ may not exist. Assume that the value $\inf \{x\mid F_j(x)\ge D\}$ can be computed in O(1) time for any D, $0<D\le U$, and $j\in N$. Then, since functions $F_j(x)$ are non-decreasing, all the existing values $r_j(s)$ for $s=0,1,\ldots ,\lfloor \frac{U}{\delta }\rfloor$, $j\in N$, can be computed in $O( \frac{nU}{\delta })$ time. A similar assumption is made by Malaguti et al. (2019).

Let $x^0$, $S^0$ and $F^0$ denote an optimal solution of SRK, its objective function value with respect to SRK and its objective function value with respect to the original FKPP, respectively. Note that $x^0$ is feasible for FKPP. Furthermore, there exists a feasible solution $x'$ of SRK such that $\lfloor \frac{F_j(x'_j)}{\delta }\rfloor =\lfloor \frac{F_j(x^*_j)}{\delta }\rfloor$, $j\in N$. Let us evaluate the quality of $x^0$ with respect to FKPP.

$$\begin{aligned}&F^0=\sum _{j\in N} F_j(x^0_j)=\delta \sum _{j\in N} \frac{F_j(x^0_j)}{\delta }\ge \delta \sum _{j\in N} \Big (\Big \lfloor \frac{F_j(x^0_j)}{\delta }\Big \rfloor \Big )\ge \delta \sum _{j\in N} \Big (\Big \lfloor \frac{F_j(x'_j)}{\delta }\Big \rfloor \Big )=\\&\delta \sum _{j\in N} \Big (\Big \lfloor \frac{F_j(x^*_j)}{\delta }\Big \rfloor \Big )>\delta \sum _{j\in N} \Big (\frac{F_j(x^*_j)}{\delta }-1\Big ) =F^*-n\delta \ge (1-\varepsilon )F^*. \end{aligned}$$

This chain of relations proves that any optimal algorithm for SRK is an $(1-\varepsilon )$-approximation algorithm for FKPP. Let us evaluate $S^0$ from above.

$$\begin{aligned} S^0=\sum _{j\in N}\Big \lfloor \frac{F_j(x^0_j)}{\delta }\Big \rfloor \le \sum _{j\in N}\frac{F_j(x^0_j)}{\delta }\le \sum _{j\in N}\frac{F_j(x^*_j)}{\delta }\le \frac{U}{\delta }. \end{aligned}$$

Let $U^0=\lfloor \frac{U}{\delta }\rfloor$. Since $S^0$ is integral, $S^0\in \{0,1,\ldots ,U^0\}$.

A profit-based dynamic programming algorithm for SRK, denoted as DP, is now presented. In this algorithm, partial solutions $x=(x_1,\ldots ,x_j)$ are constructed for $j=1,\ldots ,n$. With each partial solution $x=(x_1,\ldots ,x_j)$, a state (j, g) is associated, where $g=\sum _{i=1}^j \lfloor \frac{F_i(x_i)}{\delta }\rfloor$. A total weight function $T_j(g)$ is recursively calculated for each state (j, g), which is the minimum total weight of partial solutions in the same state (j, g). A partial solution with value $T_j(g)$ is dominant over partial solutions in the state (j, g) meaning that if there is a partial solution in this state that can be extended to an optimal solution of SRK, then the dominant solution can be extended to an optimal solution of SRK in the same way. Therefore, only a single dominant solution needs to be stored for each state, and the other solutions can be discarded.

The initialization of Algorithm DP is $T_0(0)=0$, and $T_0(g)=W+1$ for $g\ne 0$, $g=0,1,\ldots ,U^0$. The recursion for $j=1,\ldots ,n$ and $g=0,1,\ldots ,U^0$, is

$$\begin{aligned} T_j(g)=\min _{x\in \{r_j(0),r_j(1),\ldots ,r_j(U^0)\}}\Big \{T_{j-1}\Big (g-\Big \lfloor \frac{F_j(x)}{\delta }\Big \rfloor \Big )+w_jx\Big \}. \end{aligned}$$

The optimal objective function value of the problem SRK is equal to

$$\begin{aligned} S^0=\max \{g\mid T_n(g)\le W, g=0,1,\ldots ,U^0\}, \end{aligned}$$

and the corresponding optimal solution $x^0$ is determined by the optimal solutions of the recursive equation on the way to $T_n(g)=S^0$. The recursive equation can be solved in $O(\frac{U}{\delta })$ time for each state (j, g). Since the state space cardinality is $O(nU^0)=O(\frac{nU}{\delta })$, the running time of Algorithm DP is $O(\frac{nU^2}{\delta ^2})=O(\frac{n^3}{\varepsilon ^2}(\frac{U}{L})^2)$.

Remark 1

Algorithm DP produces a solution with profit $F^0\ge F^*-\varepsilon L$ and it does it in $O(\frac{n^3}{\varepsilon ^2}(\frac{U}{L})^2)$ time irrespectively of whether L, $0<L'\le L\le U$, is a lower bound for $F^*$.

Kovalyov (1995) presents a bound improvement procedure for a minimization problem, which can be easily modified for a maximization problem, to determine lower and upper bounds B and C for optimum value $F^*$ such that $B\le F^*\le C$ and $B/C=O(1)$, if there exist lower and uppers bounds $L'$ and $U'$ satisfying $0<L'\le F^*\le U'$ and a specific approximation algorithm. For FKPP, DP is such an algorithm. The running time of the bound improvement procedure for the FKPP problem is $O(n^3\log _2 n)$ if it employs lower and upper bounds $L'$ and $U'=nL'$ and Algorithm DP. For completeness, the bound improvement procedure after the following lemma is presented.

Lemma 1

A combination of Algorithm DP and the bound improvement procedure is an FPTAS for FKPP with running time $O(n^3\log _2 n+\frac{n^3}{\varepsilon ^2})$, if the profit functions $F_j(x)$, $j\in N$, are non-negative non-decreasing and the value $\inf \{x\mid F_j(x)\ge D\}$ is computable in O(1) time for any D, $0<D\le U$, and $j\in N$.

Bound improvement procedure. The procedure calculates numbers B and C such that $B\le F^*\le C$ and $C\le 4B$. For a maximization problem with the optimum value $F^*$, let lower and upper bounds $L'$ and $U'$ be given such that $0<L'\le F^*\le U'$. Compute integer number k satisfying $2^{k-1}L'<U'\le 2^kL'$. We have $L'\le F^*\le 2^kL'$ and $k=O(\log _2\frac{U'}{L'})$.

For $q=k,k-1,\ldots ,1$, apply an approximation algorithm for the maximization problem which finds a feasible solution with value $F^{(q)}\ge F^*-2^{q-2}L'$ if $F^*\le 2^qL'$. If $F^*>2^qL'$, then the algorithm can still find a feasible solution with value $F^{(q)}\ge F^*-2^{q-2}L'$, but it is not guaranteed. For FKPP, Algorithm DP with $\varepsilon =1/2$, $U=2^qL'$ and $L=2^{q-1}L'$ is such an algorithm because, due to Remark 1, it finds a solution with value $F^0\ge F^*-\varepsilon L=F^*-\frac{1}{2}L=F^*-2^{q-2}L'$ if $F^*\le U=2^qL'$. For FKPP, it runs in $O(n^3)$ time. Since $F^*\le 2^kL'$, a feasible solution with value $F^{(k)}\ge F^*-2^{k-2}L'$ will be found. If $F^{(k)}\ge 2^{k-2}L'$, then $2^{k-2}L'\le F^{(k)}\le F^*\le 2^kL'$. Hence, $B=F^{(k)}$, $C=2^kL'$, and the procedure stops. If $F^{(k)}<2^{k-2}L'$, then $F^*\le F^{(k)}+2^{k-2}L'<2^{k-1}L'$, and we can re-set $k:=k-1$. Therefore, $B=F^{(t)}$ and $C=2^tL'$ where t is the largest index such that $k\ge t\ge 1$ and $F^{(t)}\ge 2^{t-2}L'$. Such an index t exists. Assume that it does not exist for all iterations up to the iteration in which k is re-set to 1. Since this iteration is reached, relations $F^{(2)}<2^0L'$ and $F^*\le F^{(2)}+2^0L'<2L'$ are satisfied. Furthermore, $L'\le F^*$ by the definition of $L'$. Hence, $L'\le F^*\le 2L'$, and for $t=1$ we have $F^{(1)}\ge F^*-2^{-1}L'\ge 2^{-1}L'$, as it is required by the definition of t. Note that if $t=1$, then $C/B=2$. For FKPP, since $0<L'\le F^*\le nL'$, the number of iterations of the bound improvement procedure is at most $k=O(\log _2\frac{U'}{L'})=O(\log _2 n)$ and its overall running time is $O(n^3\log n)$.