* Wang and Wang (2010) Wang, Y.-W. and C.-R. Wang (2010).  Locating passenger vehicle refueling stations.  Transportation Research Part E: Logistics and Transportation Review 46(5), 791–801.
  * Wen et al. (2016) Wen, M., E. Linde, S. Ropke, P. Mirchandani, and A. Larsen (2016).  An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem.  Computers & Operations Research 76, 73–83.
  * Xu et al. (2013) Xu, H., S. Miao, C. Zhang, and D. Shi (2013).  Optimal placement of charging infrastructures for large-scale integration of pure electric vehicles into grid.  International Journal of Electrical Power & Energy Systems 53, 159–165.
  * Xylia et al. (2017) Xylia, M., S. Leduc, P. Patrizio, F. Kraxner, and S. Silveira (2017).  Locating charging infrastructure for electric buses in Stockholm.  Transportation Research Part C: Emerging Technologies 78, 183–200.
  * Yang et al. (2017) Yang, C., W. Lou, J. Yao, and S. Xie (2017).  On charging scheduling optimization for a wirelessly charged electric bus system.  IEEE Transactions on Intelligent Transportation Systems 19(6), 1814–1826.
  * Yao et al. (2020) Yao, E., T. Liu, T. Lu, and Y. Yang (2020).  Optimization of electric vehicle scheduling with multiple vehicle types in public transport.  Sustainable Cities and Society 52, 101862.
  * Zhang et al. (2016) Zhang, H., S. J. Moura, Z. Hu, and Y. Song (2016).  PEV fast-charging station siting and sizing on coupled transportation and power networks.  IEEE Transactions on Smart Grid 9(4), 2595–2605.
  * Zhang et al. (2022) Zhang, L., Z. Liu, W. Wang, and B. Yu (2022).  Long-term charging infrastructure deployment and bus fleet transition considering seasonal differences.  Transportation Research Part D: Transport and Environment 111, 103429.
  * Zhou et al. (2020) Zhou, G.-J., D.-F. Xie, X.-M. Zhao, and C. Lu (2020).  Collaborative optimization of vehicle and charging scheduling for a bus fleet mixed with electric and traditional buses.  IEEE Access 8, 8056–8072.
  * Zhou et al. (2020) Zhou, Y., X. C. Liu, R. Wei, and A. Golub (2020).  Bi-objective optimization for battery electric bus deployment considering cost and environmental equity.  IEEE Transactions on Intelligent Transportation Systems 22(4), 2487–2497.
  * Zhou et al. (2022) Zhou, Y., Q. Meng, and G. P. Ong (2022).  Electric bus charging scheduling for a single public transport route considering nonlinear charging profile and battery degradation effect.  Transportation Research Part B: Methodological 159, 49–75.


# Non-convex relaxation and 1/2-approximation algorithm for the chance-
constrained binary knapsack problem

Junyoung Kim<EMAIL_ADDRESS>Kyungsik Lee<EMAIL_ADDRESS>Department of
Industrial Engineering, Seoul National University, 1 Gwanak-ro, Gwanak-gu,
Seoul 08826, Republic of Korea

###### Abstract

We consider the chance-constrained binary knapsack problem (CKP), where the
item weights are independent and normally distributed. We introduce a
continuous relaxation for the CKP, represented as a non-convex optimization
problem, which we call the non-convex relaxation. A comparative study shows
that the non-convex relaxation provides an upper bound for the CKP, at least
as tight as those obtained from other continuous relaxations for the CKP.
Furthermore, the quality of the obtained upper bound is guaranteed to be at
most twice the optimal objective value of the CKP. Despite its non-convex
nature, we show that the non-convex relaxation can be solved in polynomial
time. Subsequently, we proposed a polynomial-time 1/2-approximation algorithm
for the CKP based on this relaxation, providing a lower bound for the CKP.
Computational test results demonstrate that the non-convex relaxation and the
proposed approximation algorithm yields tight lower and upper bounds for the
CKP within a short computation time, ensuring the quality of the obtained
bounds.

###### keywords:

Knapsack problem , Chance-constrained programming , Relaxation , Non-convex
optimization , Approximation algorithm

##  1 Introduction

The binary knapsack problem (BKP) is a widely studied combinatorial
optimization problem. In this problem, we are given a set of items
$N=\\{1,...,n\\}$, where each item $j\in N$ has a profit $c_{j}>0$ and a
weight $a_{j}>0$. The objective is to select a subset of items that can be
packed into a knapsack of a given capacity $b>0$, aiming to maximize the total
profit of the selected items. The BKP holds both theoretical and practical
significance in integer programming. Its combinatorial structure, defined with
general coefficients, provides insights for analyzing complexity status and
developing solution approaches for complicated integer programs. Specifically,
the BKP frequently arises as a sub-problem of several large-scale integer
programs, such as column generation sub-problems for generalized assignment
problems (Savelsbergh, 1997) or cutting-stock problems (Gilmore and Gomory,
1961). Developing an efficient solution approach for the BKP is essential for
successfully solving such large-scale integer programs. While the BKP is known
to be NP-hard, it can be solved in pseudo-polynomial time using a dynamic
programming algorithm. In addition to exact algorithms such as the dynamic
programming algorithm, efficient approximation or heuristic algorithms have
been developed over the last few decades. Comprehensive reviews of these
studies can be found in Martello and Toth (1990) and Kellerer et al. (2004).

Given the importance of the BKP, recent research has focused on its variants
that have emerged in challenging real-world optimization problems. Data
uncertainty is a significant concern in practical optimization problems,
impacting the quality and feasibility of solutions (Ben-Tal et al., 2009).
Various modeling frameworks have been developed to address this issue and
incorporate data uncertainty into optimization models. Two representative
frameworks are robust optimization (Ben-Tal et al., 2009) and stochastic
optimization approaches (Birge and Louveaux, 2011). The former assumes that
the data is drawn from a given uncertainty set and aims to find the best
solution feasible for all realizations of the data. The latter approach
utilizes stochastic information about the data and typically optimizes the
expectation of the objective value. The chance-constrained programming
approach introduced by Charnes et al. (1958) is a type of stochastic
optimization approach. Its primary goal is to obtain the best solution
satisfying the constraints within a specified probabilistic threshold.
Uncertain variants of the BKP within these frameworks, such as the robust
knapsack problem (Yu, 1996; Iida, 1999; Bertsimas and Sim, 2004) and the
stochastic knapsack problem (Kosuch and Lisser, 2010; Merzifonluoğlu et al.,
2012), have also been extensively explored along with their solution
approaches.

We consider the chance-constrained binary knapsack problem (CKP), where each
item $j\in N$ has an uncertain item weight $\tilde{a}_{j}$. The objective of
the CKP is to find a subset of items maximizing the total profit, while the
probability of satisfying the capacity constraint is greater than or equal to
a given threshold $\rho$. Here, we assume that $\rho\geq 0.5$. The CKP can be
formulated as follows:

$\displaystyle\max\quad$ $\displaystyle\sum_{j\in N}c_{j}x_{j}$ s.t
$\displaystyle\mathbb{P}\left\\{\sum_{j\in N}\tilde{a}_{j}x_{j}\leq
b\right\\}\geq\rho$ (1) $\displaystyle x\in\\{0,1\\}^{n}$

The feasible solution set of the CKP changes depending on the distribution of
$\tilde{a}_{j}$’s due to the chance constraint (1). This study assumes that
the item weights are mutually independent and normally distributed with mean
$a_{j}$ and standard deviation $\sigma$, i.e.,
$\tilde{a}_{j}\sim\mathcal{N}(a_{j},\sigma_{j}^{2})$. In this case, the chance
constraint (1) can be reformulated as the following second-order cone
constraint:

$\sum_{j\in N}a_{j}x_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in
N}\sigma_{j}^{2}x_{j}^{2}}\leq b,,$ (2)

where $\Phi^{-1}(\cdot)$ denotes the inverse of the cumulative density
function for the standard normal distribution. Consequently, the CKP can be
formulated as the following second-order cone program, which we refer to as
the ISP.

$\text{ISP: }\max\left\\{\sum_{j\in
N}c_{j}x_{j}:\eqref{chancon_convex},x\in\\{0,1\\}^{n}\right\\}$

Without loss of generality, we assume that $\sum_{j\in
N}a_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in N}\sigma_{j}^{2}}>b$ and
$a_{j}+\Phi^{-1}(\rho)\sigma\leq b$ for each $j\in N$.

The CKP may seem artificial due to the normality assumption on the probability
distribution. However, the CKP can represent other BKP variants under
different assumptions on the uncertain item weights. For example, when only
the uncertainty set is known as an ellipsoidal set, the corresponding robust
knapsack problem can be formulated as a form of the ISP (Ben-Tal and
Nemirovski, 1998). In addition, when the uncertain item weights are known only
through their first and second moments, the chance constraint (1) under the
worse-case probability distribution can be represented as the constraint (2)
where $\Phi^{-1}(\rho)=\sqrt{\rho/(1-\rho)}$ (Ghaoui et al., 2003; Bertsimas
and Popescu, 2005). Therefore, studies on the CKP can be applied to these BKP
variants.

Solution approaches for the CKP have been studied in the literature. The CKP
is a generalization of the BKP, where the latter is a special case with
$\sigma_{j}=0$ for each $j\in N$. Therefore, the CKP is also NP-hard. While an
optimal solution for the CKP with a few items can be obtained by solving the
ISP using the branch-and-bound algorithm provided by commercial optimization
software, solving large-sized CKPs remains challenging. Scalable exact
solution approaches, such as the dynamic programming algorithm for the BKP,
have not yet been proposed. However, several heuristic algorithms have been
developed for the CKP.

Shabtai et al. (2018) proposed a FPTAS (fully polynomial-time approximation
scheme) for the CKP in a relaxed sense. For a given $\epsilon>0$, this scheme
provides a feasible solution for the relaxed CKP where $b$ is replaced by
$(1+\epsilon)b$, with the corresponding objective value being greater than or
equal to $(1-5\epsilon)$ times the optimal objective value of the original
CKP. Han et al. (2016) considered a relaxation of the CKP, represented as a
robust knapsack problem under a polyhedral uncertainty set. The authors
proposed a pseudo-polynomial time algorithm for solving this problem and
showed that the optimal solution satisfies the capacity constraint of the CKP
with a probability of at least $\rho-\epsilon$ for a given $\epsilon>0$. We
note that the solution approaches proposed by Shabtai et al. (2018) and Han et
al. (2016) may yield an infeasible solution for the CKP. However, they can be
used as a heuristic approach by applying them to the CKP instances modified
appropriately. Joung and Lee (2020) proposed another robust optimization-based
heuristic for the CKP. The authors approximated the CKP as a robust knapsack
problem under a box uncertainty set with a cardinality constraint. The authors
then proposed a pseudo-polynomial time heuristic algorithm for the CKP, which
solves this robust knapsack problem iteratively while adjusting the value of
the cardinality.

These solution approaches, however, may still involve a considerable amount of
computation due to their high computational complexity. Furthermore, the
quality of the obtained solutions is not guaranteed. A PTAS for the CKP was
proposed by Goyal and Ravi (2010) using the parametric linear programming
reformulation, which provides a $(1-3\epsilon)$-approximate solution for a
given $\epsilon>0$. However, the PTAS also has a prohibitively large running
time, which is undesirable in practice.

On the other hand, various formulations for the CKP have been introduced in
the literature. Atamtürk and Narayanan (2008) formulated the CKP as an integer
linear program using a submodular polytope (Conforti et al., 2014). Goyal and
Ravi (2010) introduced an integer non-convex program for the CKP by replacing
$x_{j}^{2}$ with $x_{j}$ in the ISP, based on the binarity of the decision
variables. These formulations, including the ISP, yield continuous relaxations
for the CKP, and their optimal solutions provide upper bounds for the problem.
Typically, bounds obtained from relaxations of integer programming problems
can be used to evaluate the quality of solutions obtained from heuristic
algorithms. They also play a crucial role in developing exact algorithms based
on enumeration schemes, such as the branch-and-bound algorithm. Moreover,
approximate solutions for integer programming problems can often be obtained
from optimal solutions of their continuous relaxations.

However, the CKP’s continuous relaxations have been scarcely studied; only two
studies have addressed this issue. Goyal and Ravi (2010) showed that the
continuous relaxation of the ISP can have a large integrality gap. Atamtürk
and Narayanan (2009) examined the special case of the continuous relaxation of
the integer non-convex program introduced by Goyal and Ravi (2010), where
$c_{j}\leq n$ for each $j\in N$. The authors proved that this case can be
solved in polynomial time. To the best of our knowledge, no studies have yet
theoretically compared the continuous relaxations of the CKP, and proposed
solution approaches that utilize them for the CKP.

In this paper, we consider the continuous relaxation of the integer non-convex
program for the CKP introduced by Goyal and Ravi (2010). This relaxation,
denoted as the non-convex relaxation, is defined as the following non-convex
optimization problem:

$\max_{x\in[0,1]^{n}}\left\\{\sum_{j\in N}c_{j}x_{j}:g(x)\leq b\right\\},$

where $g(x)=\sum_{j\in N}a_{j}x_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in
N}\sigma_{j}^{2}x_{j}}$. We conduct a comparative study on the non-convex
relaxation with the other continuous relaxations, along with an analysis of
the properties of its optimal solution. Subsequently, an efficient algorithm
is proposed for solving this relaxation. We also show that an approximate
solution for the CKP can be obtained from the non-convex relaxation. Our
contributions can be summarized as follows.

  * •

We show that the non-convex relaxation provides an upper bound for the CKP, at
least as strong as those provided by the other continuous relaxations
presented in the literature. Furthermore, we prove that the upper bound is
less than or equal to twice the optimal objective value of the CKP.

  * •

Despite the non-convexity, we show that the non-convex relaxation can be
solved in polynomial time. Subsequently, we propose a polynomial-time
1/2-approximation algorithm for the CKP based on the non-convex relaxation.

  * •

Through extensive computational tests, we demonstrate that the non-convex
relaxation and the proposed approximation algorithm provide tight upper and
lower bounds for the CKP within a short computation time.

The remainder of this paper is organized as follows. In Section 2, we
introduce the other continuous relaxations for the CKP presented in the
literature and compare them with the non-convex relaxation. An efficient
algorithm for solving the non-convex relaxation is devised in Section 3.
Section 4 presents how an approximate solution for the CKP can be obtained
from the non-convex relaxation. Computational test results are reported in
Section 5. Finally, the concluding remarks are given in Section 6.

##  2 Comparison of the continuous relaxations for the CKP

We start this section by formally defining the other continuous relaxations
derived from the CKP formulations introduced in Section 1. By relaxing the
integrality condition in the ISP, the following relaxation can be obtained:

$\max\left\\{\sum_{j\in N}c_{j}x_{j}:x\in\mathcal{P}_{C}\right\\},$

where $\mathcal{P}_{C}=\left\\{x\in[0,1]^{n}:\eqref{chancon_convex}\right\\}$.
We refer to this relaxation as the convex relaxation for the CKP because the
feasible solution set $\mathcal{P}_{C}$ is convex. The objective value of this
relaxation, denoted as $z_{C}$, can be efficiently obtained since this
relaxation corresponds to a second-order cone programming problem.

Let us define a set function $F(S)=\sum_{j\in
S}a_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in S}\sigma^{2}_{j}}$. Another
formulation for the CKP proposed by Atamtürk and Narayanan (2008) is based on
the submodularity of $F(S)$ and defined as the following integer linear
program:

$\displaystyle\max\quad$ $\displaystyle\sum_{j\in N}c_{j}x_{j}$ s.t
$\displaystyle\sum_{j\in N}\pi_{j}x_{j}\leq b,\;\forall\pi\in\text{ext}(\Pi)$
(3) $\displaystyle x\in\\{0,1\\}^{n},$

where $\Pi=\left\\{\pi\in\mathbb{R}^{n}:\sum_{j\in S}\pi_{j}\leq
F(S),\;\forall S\subseteq N\right\\}$, and $\text{ext}(\Pi)$ is the set of
extreme points of $\Pi$. The continuous relaxation of this formulation can be
described as

$\max\left\\{\sum_{j\in N}c_{j}x_{j}:x\in\mathcal{P}_{P}\right\\},$

where $\mathcal{P}_{P}=\left\\{x\in[0,1]^{n}:\eqref{modconst}\right\\}$.
$\mathcal{P}_{P}$ is a polyhedron since $|\text{ext}(\Pi)|$ is finite. Hence,
we refer to this relaxation as the polyhedral relaxation for the CKP and
denote its optimal objective value as $z_{P}$. Even though this relaxation has
exponentially many constraints, $z_{P}$ can be obtained in polynomial time
using the cutting-plane algorithm (Edmond, 1970).

In the following discussion, we compare the optimal objective values of the
convex, polyhedral, and non-convex relaxations, which are upper bounds for the
CKP. Additionally, we examine the integrality gaps of these relaxations by
comparing their optimal objective values with the optimal objective value of
the CKP.

###  2.1 Comparison of the optimal objective values of the continuous
relaxations

In this section, we show that an upper bound the CKP provided by the non-
convex relaxation is at least as strong as those obtained from the other
continuous relaxations. We first introduce two properties of an optimal
solution for the non-convex relaxation. Let $\mathcal{P}_{NC}$ be the feasible
solution set of the non-convex relaxation.

######  Proposition 1.

Let $x^{\star}\in\mathcal{P}_{NC}$ be an optimal solution for the non-convex
relaxation. Then $g(x^{\star})=b$.

###### Proof.

There exists $k\in N$ such that $x^{\star}_{k}<1$ by the assumption that
$\sum_{j\in N}a_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in N}\sigma_{j}^{2}}>b$. Now,
suppose that $g(x^{\star})<b$. In this case, an improved solution can be
obtained by increasing the values of $x^{\star}_{k}$ since $c_{k}>0$. However,
this result contradicts the optimality of $x^{\star}$. Therefore, the result
follows. ∎∎

######  Proposition 2.

There exists an optimal solution for the non-convex relaxation in which at
most one variable has a fractional value.

###### Proof.

Let $\hat{x}\in\mathcal{P}_{NC}$ be an optimal solution of the non-convex
relaxation, and suppose that $\hat{x}$ has more than two fractional variables.
We show that another optimal solution can be constructed from $\hat{x}$, where
one of the fractional variables becomes $0$ or $1$. Let $k$ and $l$ be the
indices of some two fractional variables, where $0<\hat{x}_{k}<1$ and
$0<\hat{x}_{l}<1$. Let us consider the following optimization problem with two
variables.

$\displaystyle\max\quad$ $\displaystyle\sum_{j\in
N\setminus\\{k,l\\}}c_{j}\hat{x}_{j}+c_{k}x_{k}+c_{l}x_{l}$ s.t
$\displaystyle\sum_{j\in
N\setminus\\{k,l\\}}a_{j}\hat{x}_{j}+a_{k}x_{k}+a_{l}x_{l}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in
N\setminus\\{k,l\\}}\sigma^{2}_{j}\hat{x}_{j}+\sigma^{2}_{k}x_{k}+\sigma^{2}_{l}x_{l}}=b$
(4) $\displaystyle 0\leq x_{k},x_{l}\leq 1$

It is clear that $(\hat{x}_{k},\hat{x}_{l})$ is an optimal solution to the
above problem, with feasibility ensured by Proposition 1. We first show that
there exists another optimal solution for the problem (4), where one of the
two variables has an integral value.

From the first constraint of the problem (4), we can express $x_{l}$ as a
function of $x_{k}\in[0,1]$, denoted as $h(x_{k})$. It is clear that
$h(x_{k})$ is a decreasing function for $x_{k}\in[0,1]$. Furthermore, it can
be easily shown that $h(x_{k})$ is convex. The problem (4) can be rewritten
with $h(x_{k})$ as follows.

$\max\\{c_{k}x_{k}+c_{l}h(x_{k}):0\leq h(x_{k})\leq 1,\;0\leq x_{k}\leq 1\\}$
(5)

Here, we leave out the constant term in the objective function of the problem
(4). The problem (5) is a single-variable maximization problem where the
feasible solution set is convex due to the monotonicity of $h(x_{k})$ for
$x_{k}\in[0,1]$. The objective function is also convex due to the convexity of
$h(x_{k})$. Therefore, an optimal solution $x^{\star}_{k}$ for the problem (5)
can be found on the boundary of $x_{k}$, that is, $x^{\star}_{k}\in\\{0,1\\}$
or $h(x^{\star}_{k})\in\\{0,1\\}$. Let $x_{l}^{\star}=h(x^{\star}_{k})$. Then,
$(x^{\star}_{k},x^{\star}_{l})$ is another optimal solution for the problem
(4), which has fewer fractional variables compared to
$(\hat{x}_{k},\hat{x}_{l})$.

Now, another feasible solution for the non-convex relaxation can be
constructed from $\hat{x}$ by replacing $\hat{x}_{k}$ and $\hat{x}_{l}$ with
$x^{\star}_{k}$ and $x^{\star}_{l}$, respectively. The obtained solution is
also optimal for the non-convex relaxation, which has fewer fractional
variables, by the definition of $(x^{\star}_{k},x^{\star}_{l})$. By applying
this procedure repeatedly until one or no variable has a fractional value, we
can construct an optimal solution for the non-convex relaxation, which
satisfies the condition in the statement. Therefore, the result follows.∎∎

Based on these two properties, we compare the non-convex and polyhedral
relaxations.

######  Proposition 3.

$z_{NC}\leq z_{P}$

###### Proof.

Let $x^{\star}\in\mathcal{P}_{NC}$ be an optimal of the non-convex relaxation,
which satisfies Proposition 2. We show that $x^{\star}\in\mathcal{P}_{P}$,
hence, $z_{NC}\leq z_{P}$. For some $T\subseteq N$ and $t\in N\setminus T$,
$x^{\star}$ can be described as $x^{\star}_{j}=1$ for each $j\in T$, $0\leq
x_{t}<1$, and $x_{j}=0$ for each $j\in N\setminus T\cup\\{t\\}$. For the sake
of simplicity, let $T=\\{1,...,t-1\\}$. We can check whether
$x^{\star}\in\mathcal{P}_{P}$ by solving the following separation problem
associated with $\mathcal{P}_{P}$:

$\eta=\max\left\\{\sum_{j\in N}\pi_{j}x^{\star}_{j}:\sum_{j\in S}\pi_{j}\leq
F(S),\;S\subseteq N\right\\}.$

If $x^{\star}\notin\mathcal{P}_{P}$, then $\eta>b$ while $\eta\leq b$ implies
that $x^{\star}\in\mathcal{P}_{P}$. It is well-known that an optimal solution
$\pi^{\star}$ of this separation problem is defined as
$\pi^{\star}_{j}=F(S_{j})-F(S_{j-1})$ for each $j\in N$ where
$S_{j}=\\{1,\ldots,j\\}$ and $S_{0}=\emptyset$ (Edmond, 1970). Then,

$\eta=\sum_{j\in
N}\pi^{\star}_{j}x^{\star}_{j}=F(S_{t-1})+(F(S_{t})-F(S_{t-1}))x^{\star}_{t}.$

Let $x^{S}\in\\{0,1\\}^{n}$ be the vector that represents a set $S\subseteq
N$, where, for each $j\in N$, $x^{S}_{j}=1$ if $j\in S$, otherwise,
$x^{S}_{j}=0$. Then, $F(S)=g(x^{S})$ for all $S\subseteq N$, and
$x^{\star}=(1-x^{\star}_{t})x^{S_{t-1}}+x^{\star}_{t}x^{S_{t}}$. Furthermore,
$\eta$ can be rewritten as follows:

$\eta=(1-x^{\star}_{t})g(x^{S_{t-1}})+x^{\star}_{t}g(x^{S_{t}})$

It can be easily shown that $g(x)$ is concave. Accordingly, we have the
following result.

$b\geq
g(x^{\star})=g((1-x^{\star}_{t})x^{S_{t-1}}+x^{\star}_{t}x^{S_{t}})\geq(1-x^{\star}_{t})g(x^{S_{t-1}})+x^{\star}_{t}g(x^{S_{t}})=\eta$

Therefore, $x^{\star}\in\mathcal{P}_{P}$, and the result follows. ∎∎

Next, we compare the convex relaxation and the polyhedral relaxation.

######  Proposition 4.

$z_{P}\leq z_{C}$

###### Proof.

We define an ellipsoidal set $\mathcal{U}$ as follows.

$\mathcal{U}=\left\\{u\in\mathbb{R}_{+}^{n}:\sum_{j\in
N}\left(\frac{u_{j}-a_{j}}{\sigma_{j}}\right)^{2}\leq(\Phi^{-1}(\rho))^{2}\right\\}$

Let us consider the following robust knapsack problem under the ellipsoidal
uncertainty set $\mathcal{U}$.

$\displaystyle\max\quad$ $\displaystyle\sum_{j\in N}c_{j}x_{j}$ s.t
$\displaystyle\sum_{j\in N}u_{j}x_{j}\leq b,\;\forall u\in\mathcal{U}$
$\displaystyle x\in\\{0,1\\}^{n}$

As mentioned in Section 1, this problem is equivalently reformulated as the
ISP. Let $z_{R}$ and $\mathcal{P}_{R}$ be the optimal objective value and the
feasible solution set of the continuous relaxation of this problem,
respectively. Then, $z_{R}=z_{C}$ and $\mathcal{P}_{R}=\mathcal{P}_{C}$. On
the other hand, $\mathcal{P}_{P}$ remains the same even if $\text{ext}(\Pi)$
is replaced with $\Pi$ in its definition. Based on this observation, we prove
that $\mathcal{P}_{P}\subseteq\mathcal{P}_{R}=\mathcal{P}_{C}$ by showing that
$\mathcal{U}\subseteq\Pi$.

For some $\hat{u}\in\mathcal{U}$, we can see that

$\sum_{j\in S}\hat{u}_{j}\leq\sum_{j\in
S}a_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in S}\sigma_{j}^{2}}=F(S),\;\forall
S\subseteq N,$

because

$\max\left\\{\sum_{j\in S}u_{j}:u\in\mathcal{U}\right\\}=\sum_{j\in
S}a_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in S}\sigma_{j}^{2}}.$

Therefore, $\hat{u}\in\Pi$. This result implies that $\mathcal{U}\subseteq\Pi$
and $\mathcal{P}_{R}\subseteq\mathcal{P}_{P}$, that is, $z_{P}\leq
z_{R}=z_{C}$. ∎∎

Proposition 3 and 4 directly lead to the following result.

######  Theorem 1.

$z_{NC}\leq z_{P}\leq z_{C}$.

Therefore, the upper bound for the CKP, provided by the non-convex relaxation
is as strong as those provided by the other continuous relaxations.

###  2.2 Integrality gaps of the continuous relaxations

We further analyze the tightness of the upper bounds provided by the
continuous relaxations in terms of the integrality gaps. The integrality gap
of each continuous relaxation is defined as $(z-z_{OPT})/z_{OPT}$ where $z$ is
the optimal objective value of the continuous relaxation and $z_{OPT}$ is the
optimal objective value of the CKP.

Let us consider the following example introduced in Goyal and Ravi (2010).

######  Example 1.

Consider the CKP instances where $c_{j}=\sigma_{j}=1$, and $a_{j}=1/\sqrt{n}$
for each $j\in N$ where $n\geq 56$. Additionally, let $b=3$ and
$\Phi^{-1}(\rho)=1.5$. Then, optimal solutions for these CKP instances should
select 3 items. If 4 items are selected, the solution is not feasible for
these instances because

$\frac{4}{\sqrt{n}}+\Phi^{-1}(\rho)\sqrt{4}=\frac{4}{\sqrt{n}}+3>3.$

Therefore, $z_{OPT}=3$.

Goyal and Ravi (2010) showed that the integrality gap of the convex relaxation
is $\Omega(\sqrt{n})$ through this example. Therefore, the convex relaxation
may have a large integrality gap which increases as $n$ grows.

We obtain the similar result for the polyhedral relaxation using Example 1.

######  Proposition 5.

There exists CKP instances where the integrality gap of the polyhedral
relaxation is $\Omega(\sqrt{n})$.

###### Proof.

Let us consider $\hat{x}\in\mathbb{R}_{+}^{n}$ defined as
$\hat{x}_{j}=1/\sqrt{n}$ for each $j\in N$. We first show that $\hat{x}$ is a
feasible solution of the polyhedral relaxation for the CKP instances in
Example 1. The separation problem for $\hat{x}$ is defined as follows.

$\eta=\max\left\\{\sum_{j\in N}\pi_{j}\hat{x}_{j}:\sum_{j\in S}\pi_{j}\leq
F(S),\;S\subseteq N\right\\}.$

Let $S_{j}=\\{1,\ldots,j\\}$ for each $j\in N$ where $S_{0}=\emptyset$. An
optimal solution $\pi^{\star}$ of this separation problem can be constructed
as

$\pi_{j}^{\star}=F(S_{j})-F(S_{j-1})=\frac{1}{\sqrt{n}}+\Phi^{-1}(\rho)(\sqrt{j}-\sqrt{j-1}),$

for each $j\in N$. Then, we can see that

$\eta=\sum_{j\in
N}\frac{1}{\sqrt{n}}\cdot\pi_{j}^{\star}=\frac{1}{\sqrt{n}}\cdot
F(n)=1+\Phi^{-1}(\rho)=2.5.$

Therefore, $\hat{x}\in\mathcal{P}_{P}$ since $\eta<b=3$. On the other hand,
the objective value of the polyhedral relaxation, corresponding to $\hat{x}$,
is $\sqrt{n}$. These results imply that $z_{P}\geq\sqrt{n}$ and the
integrality gap of the polyhedral relaxation is $(\sqrt{n}-3)/3$ for these
instances. Therefore, the result follows. ∎∎

On the contrary to the convex and polyhedral relaxations, the following
theorem shows that the integrality gap of the non-convex relaxation is bounded
by a constant factor.

######  Theorem 2.

$z_{NC}\leq 2z_{OPT}$

###### Proof.

Let $x^{\star}\in\mathcal{P}_{NC}$ be an optimal solution for the non-convex
relaxation, which satisfies Proposition 2. We denote $t\in N$ as the index of
the fractional variable in $x^{\star}$ such that $0\leq x^{\star}_{t}<1$. From
$x^{\star}$, we can construct two feasible solutions $x^{D}$ and $x^{U}$ for
the CKP as follows: $x^{D}_{j}=\lfloor x^{\star}_{j}\rfloor$ for each $j\in N$
and $x^{U}_{t}=1$ while $x^{U}_{j}=0$ for each $j\in N\setminus\\{t\\}$. Then,
we can see that

$z_{NC}=\sum_{j\in
N\setminus\\{t\\}}c_{j}x_{j}^{\star}+c_{t}x_{t}^{\star}\leq\sum_{j\in
N}c_{j}x_{j}^{D}+c_{t}x_{t}^{U}\leq 2z_{OPT},$

where the last inequality holds due to the feasibility of $x^{D}$ and $x^{U}$
for the CKP. Therefore, the result follows. ∎∎

Theorem 2 implies that the integrality gap of the non-convex relaxation is
always less than 1 since

$\frac{z_{NC}-z_{OPT}}{z_{OPT}}\leq\frac{z_{OPT}}{z_{OPT}}=1.$

Therefore, the non-convex relaxation provides a quality-guaranteed upper bound
for the CKP.

The difference between the non-convex relaxation and the other continuous
relaxations can be definitely shown in Example 1. As shown in the proof of
Proposition 5, $z_{C}$ and $z_{P}$ are greater than or equal to $\sqrt{n}$ for
the CKP instances described in Example 1. These results mean that $z_{C}$ and
$z_{P}$ go to infinity as $n$ goes to infinity, while $z_{OPT}$ is always 3.
However, $z_{NC}$ is always less than or equal to $6$ regardless of $n$ by
Theorem 2.

In summary, the non-convex relaxation provides a quality-guaranteed upper
bound for the CKP, which is at least as tight as the other continuous
relaxations. To obtain such a bound, we should solve the non-convex relaxation
represented as a non-convex optimization problem. In general, non-convex
optimization problems are nontrivial to solve. However, in the following
section, we show that an optimal solution of the non-convex relaxation can be
obtained in polynomial time.

##  3 Polynomial-time algorithm for the non-convex relaxation

We first introduce a parametric method that constructs feasible solutions of
the non-convex relaxation. Utilizing these feasible solutions, we reformulate
the non-convex relaxation as a single-variable optimization problem. We then
devise a polynomial-time algorithm for solving the reformulated problem.

###  3.1 Reformulation of the non-convex relaxation

Let us define a function $a_{j}(\delta)$ for $\delta\in\mathbb{R}_{+}$ as

$a_{j}(\delta)=\begin{cases}a_{j}&,\;\text{if }\delta=0\\\
a_{j}+\frac{\Phi^{-1}(\rho)}{2\sqrt{\delta}}\sigma_{j}^{2}&,\;\text{otherwise}\end{cases},$

for each $j\in N$ and $\bar{N}=\\{j\in N:\sigma_{j}=0\\}$, where
$|\bar{N}|=\bar{n}$. We also define $p_{j}(\delta)=c_{j}/a_{j}(\delta)$ for
each $j\in N$.

Now, let $\tau(\delta)$ be a function representing a variable sequence of $N$
that varies with $\delta\in\mathbb{R}_{+}$. When $\delta>0$, $\tau(\delta)$ is
defined as a variable sequence of $N$ sorted in descending order of
$p_{j}(\delta)$’s. In $\tau(0)$, variables of $\bar{N}$ are sorted first in
descending order $p_{j}(\delta)$’s, followed by variables in
$N\setminus\bar{N}$ being sorted in descending order $p_{j}(\delta)$’s. Ties
in $\tau(\delta)$ are resolved in descending order of
$\sigma_{j}^{2}/c_{j}$’s, and if these values are still equivalent, further
resolution takes place in ascending order of indices. Accordingly,
$\tau(\delta)$ is uniquely defined for each $\delta\in\mathbb{R}_{+}$.

A feasible solution of the non-convex relaxation can be obtained in a greedy
manner following $\tau(\delta)$ for each $\delta\in\mathbb{R}_{+}$. For the
sake of simplicity, let $\tau(\delta)=(\tau_{1},\ldots,\tau_{n})$. We can
easily find $t\in N$ such that

$t=\min\left\\{k\in
N:\sum_{j=1}^{k}a_{\tau_{j}}+\Phi^{-1}(\rho)\sqrt{\sum_{j=1}^{k}\sigma_{\tau_{j}}^{2}}\geq
b\right\\}.$

We note that such $t$ always exists for each $\delta>0$ due to the assumption
that $\sum_{j\in N}a_{j}+\Phi^{-1}(\rho)\sqrt{\sum_{j\in N}\sigma_{j}^{2}}>b$.
Additionally, let $\theta^{\star}$ be a smaller value among two solutions for
the following equation for $\theta\in\mathbb{R}$:

$\Phi^{-1}(\rho)^{2}\left(\sum_{j=1}^{t-1}\sigma^{2}_{\tau_{j}}+\sigma^{2}_{\tau_{t}}\theta\right)=\left(b-\sum_{j=1}^{t-1}a_{\tau_{j}}-a_{\tau_{t}}\theta\right)^{2},$

which is derived from

$\sum_{j=1}^{t-1}a_{\tau_{j}}+a_{\tau_{t}}\theta+\Phi^{-1}(\rho)\sqrt{\sum_{j=1}^{t-1}\sigma^{2}_{\tau_{j}}+\sigma^{2}_{\tau_{t}}\theta}=b.$

It is clear that $0<\theta^{\star}\leq 1$. We define $x(\delta)$ as

$x_{\tau_{j}}(\delta)=\begin{cases}1&,\;j<t\\\ \theta^{\star}&,\;j=t\\\
0&,\;j>t\end{cases}$

for each $j\in N$. Then, $x(\delta)$ for each $\delta\in\mathbb{R}_{+}$ is a
feasible solution for the non-convex relaxation since $g(x(\delta))=b$ and
$x(\delta)\in[0,1]^{n}$ by definition. Furthermore, $x(\delta)$ has at most
one fractional variable and can be constructed in $O(n\log n)$ for each
$\delta\in\mathbb{R}_{+}$.

Let $x^{\star}\in\mathcal{P}_{NC}$ be an optimal solution for the non-convex
relaxation, and $\delta^{\star}=\sum_{j\in N}\sigma_{j}^{2}x_{j}^{\star}$. We
now show that $x(\delta^{\star})$ is an optimal solution for the non-convex
relaxation. Let us first consider the following fractional knapsack problem:

$\displaystyle\text{FK:}\quad\max\quad$ $\displaystyle\sum_{j\in N}c_{j}x_{j}$
s.t $\displaystyle\sum_{j\in N}a_{j}(\delta^{\star})x_{j}\leq
b-\frac{\Phi^{-1}(\rho)}{2}\sqrt{\delta^{\star}}$ (6) $\displaystyle
x_{j}=0,\;j\in N\setminus\bar{N}\;\text{if }\delta^{\star}=0$ (7)
$\displaystyle x\in[0,1]^{n}$

We denote the feasible solution set of the FK as $\mathcal{P}_{FK}$.

######  Proposition 6.

An optimal solution for the FK is optimal for the non-convex relaxation.

###### Proof.

We first show that $x^{\star}\in\mathcal{P}_{FK}$. If $\delta^{\star}=0$, then
$x_{j}^{\star}=0$ for each $j\in N\setminus\bar{N}$ by the definition of
$x^{\star}$, which means that $x^{\star}$ satisfies the constraints (7). On
the other hand, the following equations hold in this case:

$b=g(x^{\star})=\sum_{j\in N}a_{j}(0)x_{j}^{\star},$

where $g(x^{\star})=b$ by Proposition 1. Therefore, $x^{\star}$ satisfies the
constraint (6), and $x^{\star}\in\mathcal{P}_{FK}$ when $\delta^{\star}=0$.
Now, suppose that $\delta^{\star}>0$. $g(x^{\star})$ can be expressed as
follows:

$\displaystyle g(x^{\star})=\sum_{j\in
N}a_{j}(\delta^{\star})x_{j}^{\star}+\frac{\Phi^{-1}(\rho)}{2}\sqrt{\delta^{\star}}$

Then, $g(x^{\star})=b$ by Proposition 1 implies that $x^{\star}$ satisfies the
constraint (6). Therefore, $x^{\star}\in\mathcal{P}_{FK}$ when $\delta>0$.
This result implies that $z_{FK}\geq z_{NC}$ where $z_{FK}$ is the optimal
objective value of the FK.

We next show that $\mathcal{P}_{FK}\subseteq\mathcal{P}_{NC}$, that is,
$z_{FK}\leq z_{NC}$. Let $\hat{x}\in\mathcal{P}_{FK}$ be given when
$\delta^{\star}=0$. Then, we can see that

$g(\hat{x})=\sum_{j\in N}a_{j}\hat{x}_{j}$

by the constraints (7), while the constraint (6) implies that $g(\hat{x})\leq
b$. Therefore, $\hat{x}\in\mathcal{P}_{NC}$. Now, suppose that
$\hat{x}\in\mathcal{P}_{FK}$ is given when $\delta^{\star}>0$. The constraint
(6) can be arranged as follows:

$\sum_{j\in
N}a_{j}\hat{x}_{j}+\frac{\Phi^{-1}(\rho)}{2}\left(\frac{\hat{\delta}}{\sqrt{\delta^{\star}}}+\sqrt{\delta^{\star}}\right)\leq
b,$ (8)

where $\hat{\delta}=\sum_{j\in N}\sigma_{j}^{2}\hat{x}_{j}$. We can obtain the
following arithmetic–geometric mean inequality.

$2\sqrt{\hat{\delta}}\leq\frac{\hat{\delta}}{\sqrt{\delta^{\star}}}+\sqrt{\delta^{\star}}$
(9)

From the inequalities (8) and (9), we can see that

$g(\hat{x})=\sum_{j\in
N}a_{j}\hat{x}_{j}+\Phi^{-1}(\rho)\sqrt{\hat{\delta}}\leq\sum_{j\in
N}a_{j}\hat{x}_{j}+\frac{\Phi^{-1}(\rho)}{2}\left(\frac{\hat{\delta}}{\sqrt{\delta^{\star}}}+\sqrt{\delta^{\star}}\right)\leq
b.$

Hence, $\hat{x}\in\mathcal{P}_{NC}$ and
$\mathcal{P}_{FK}\subseteq\mathcal{P}_{NC}$.

These results implies that $z_{FK}=z_{NC}$. Therefore, an optimal solution for
the FK is not only feasible, but also optimal for the non-convex relaxation.
∎∎

######  Proposition 7.

$x(\delta^{\star})$ is an optimal solution for the FK.

###### Proof.

Let $x^{FK}$ be an optimal solution for the FK. Suppose that
$\delta^{\star}>0$. $x^{FK}$ can be constructed by greedily selecting
variables of $N$ with the highest ratios of $c_{j}/a_{j}(\delta^{\star})$
until the constraint (6) is satisfied as an equation (Dantzig, 1957). $x^{FK}$
is an optimal solution for the non-convex relaxation by Proposition 6, and
$g(x^{FK})=b$ by Proposition 1. In other words, $x^{FK}$ is a feasible
solution for the non-convex relaxation, constructed in a greedy manner
following the sequence $\tau^{\star}$ until $g(x^{FK})=b$. This definition
corresponds to that of $x(\delta^{\star})$, hence, $x^{FK}=x(\delta^{\star})$.
Now, suppose that $\delta^{\star}=0$. In this case,
$\sum_{j\in\bar{N}}a_{j}\geq b$ since

$b=g(x^{\star})=\sum_{j\in\bar{N}}a_{j}x_{j}^{\star}$

by Proposition 1. $x^{FK}$ can then be constructed by selecting variables of
$\bar{N}$ with the highest ratios of $c_{j}/a_{j}(0)$ until $g(x^{FK})=b$,
where $x^{FK}_{j}=0$ for each $j\in N\setminus\bar{N}$. Therefore, $x^{FK}$ is
equivalent to $x(0)$, and the result follows. ∎∎

Proposition 6 and 7 imply that $x(\delta^{\star})$ is an optimal solution for
the non-convex relaxation. Therefore, we have the following result due to the
feasibility of $x(\delta)$ for the non-convex relaxation.

$\sum_{j\in N}c_{j}x_{j}(\delta)\leq\sum_{j\in
N}c_{j}x_{j}(\delta^{\star}),\;\forall\delta\in\mathbb{R}_{+}$

This observation allows us to reformulate the non-convex relaxation as the
following single-variable optimization problem.

$\displaystyle\text{NCR:}\quad\max\quad$ $\displaystyle\sum_{j\in
N}c_{j}x_{j}(\delta)$ s.t $\displaystyle\delta\in\mathbb{R}_{+}$

$\delta^{\star}$ is an optimal solution for the NCR, but it may not be the
unique one. Nonetheless, solving the NCR can provide an optimal solution for
the non-convex relaxation. The following section proposes a polynomial-time
algorithm for solving the NCR.

###  3.2 Polynomial-time algorithm for solving the reformulated non-convex
relaxation

Recall that $x(\delta)$ is determined by the variable sequence $\tau(\delta)$
for each $\delta\in\mathbb{R}_{+}$. In general, there may exist exponentially
many different variable sequences. However, in the subsequent discussion, we
prove that the number of different variable sequences indicated by
$\tau(\delta)$ is polynomially bounded.

The following example illustrates that, when $\delta>0$, $\tau(\delta)$ does
not vary with $\delta$ continuously.

######  Example 2.

Let $N=\\{1,2,3\\}$, $\Phi^{-1}(\rho)=2$,
$(c_{1},a_{1},\sigma^{2}_{1})=(1,2,3)$,
$(c_{2},a_{2},\sigma^{2}_{2})=(1,3,1)$, and
$(c_{3},a_{3},\sigma^{2}_{3})=(1,2.5,1.5)$. When $\delta>0$, $p_{1}(\delta)$,
$p_{2}(\delta)$, and $p_{3}(\delta)$ are defined as follows, and illustrated
in Figure 1.

$p_{1}(\delta)=\frac{1}{2+\frac{3}{\sqrt{\delta}}},\quad
p_{2}(\delta)=\frac{1}{3+\frac{1}{\sqrt{\delta}}},\quad
p_{3}(\delta)=\frac{1}{2.5+\frac{1.5}{\sqrt{\delta}}}$

$\delta$$p_{j}(\delta)$$1$$4$$9$$p_{1}(\delta)$$p_{2}(\delta)$$p_{3}(\delta)$
Figure 1: Illustration of $p_{1}(\delta)$, $p_{2}(\delta)$, and
$p_{3}(\delta)$

We note that $p_{2}(1)=p_{3}(1)$, $p_{1}(4)=p_{2}(4)$, and
$p_{1}(9)=p_{3}(9)$. $\tau(\delta)$ is defined as follows.

$\tau(\delta)=\begin{cases}(2,3,1)&\text{, if}\quad 0<\delta<1\\\
(3,2,1)&\text{, if}\quad 1\leq\delta<4\\\ (3,1,2)&\text{, if}\quad
4\leq\delta<9\\\ (1,3,2)&\text{, if}\quad 9\leq\delta\end{cases}.$

Here, $\tau(1)=(3,2,1)$ since $\sigma_{2}/c_{2}=1<\sigma_{3}/c_{3}=1.5$ by
definition, although $p_{2}(1)=p_{3}(1)$. The same applies to $\tau(4)$ and
$\tau(9)$.

$\tau(\delta)$ changes as $\delta$ increases only when the relative order of
some two variables in $\tau(\delta)$ is reversed. For instance, in Example 2,
variable 1 follows variable 3 in $\tau(\delta)$ when $0<\delta<9$, while
variable 1 is followed by variable 3 when $9\leq\delta$. Therefore,
$\tau(\delta)$ changes at $\delta=9$. We term the values of $\delta$ where
such reversals occur as reverse points for those two variables. Formally, for
a pair of variables $\\{k,l\\}\subseteq N$, a reverse point for $\\{k,l\\}$ is
defined as $q>0$ such that $p_{k}(q)=p_{l}(q)$ and the relative order of $k$
and $l$ changes between $\tau(q-\alpha)$ and $\tau(q)$ for a sufficiently
small $\alpha>0$. This observation enables us to enumerate all the different
variable sequences indicated by $\tau(\delta)$ by investigating all the
reverse points for every pair of variables.

We first show that there exists at most one reverse point for each pair of
variables.

######  Proposition 8.

For some $\\{k,l\\}\subseteq N$ such that
$\sigma_{k}^{2}/c_{k}\leq\sigma_{l}^{2}/c_{l}$, a reverse point uniquely
exists if and only if

$\frac{\sigma_{k}^{2}}{c_{k}}<\frac{\sigma_{l}^{2}}{c_{l}},\;\frac{a_{k}}{c_{k}}>\frac{a_{l}}{c_{l}}.$
(10)

If a reverse point $q$ exists, then $k$ is followed by $l$ in $\tau(\delta)$
when $0<\delta<q$, while $k$ follows $l$ in $\tau(\delta)$ when $q\leq\delta$.

###### Proof.

By definition, a reverse point of $\\{k,l\\}$ is a solution of
$p_{k}(\delta)=p_{l}(\delta)$ which can be rewritten as follows.

$\left(\frac{\sigma_{k}^{2}}{c_{k}}-\frac{\sigma_{l}^{2}}{c_{l}}\right)\frac{\Phi^{-1}(\rho)}{2\sqrt{\delta}}=\frac{a_{l}}{c_{l}}-\frac{a_{k}}{c_{k}}$
(11)

The condition for this equation to have a solution can be categorized into the
following cases.

  1. $\bullet$ Case 1.

(11) is valid for all $\delta>0$ when

$\frac{\sigma_{k}^{2}}{c_{k}}=\frac{\sigma_{l}^{2}}{c_{l}},\;\frac{a_{l}}{c_{l}}=\frac{a_{k}}{c_{k}}$

  2. $\bullet$ Case 2.

(11) has a unique solution $q$ when (10)

In Case 1, no reverse point exists for $\\{k,l\\}$ since the relative order of
$k$ and $l$ in $\tau(\delta)$ remains the same for all $\delta>0$. On the
other hand, in Case 2, the relative order of $k$ and $l$ changes once at
$\delta=q$, as illustrated in Figure 2.

$\delta$$p_{j}(\delta)$$q$$p_{k}(\delta)$$p_{l}(\delta)$ Figure 2: Shapes of
$p_{k}(\delta)$ (solid) and $p_{l}(\delta)$ (dotted) in Case 2

Therefore, $q$ is the unique reverse point for $\\{k,l\\}$. In other words, a
reverse point exists if and only in Case 2, and such reverse point is unique.
Furthermore, as shown in Figure 2, $p_{k}(\delta)>p_{l}(\delta)$ when
$0<\delta<q$, while $p_{k}(\delta)\leq p_{l}(\delta)$ when $q\leq\delta$.
Then, $k$ is followed by $l$ in $\tau(\delta)$ when $0<\delta<q$, while $k$
follows $l$ in $\tau(\delta)$ when $q<\delta$. We note that $l$ is followed by
$k$ in $\tau(q)$ since $\sigma_{k}^{2}/c_{k}<\sigma_{l}^{2}/c_{l}$ in this
case. Therefore, the result follows. ∎∎

By Proposition 8, there exist $O(n^{2})$ reverse points for every pair of
variables. We now show that all different variable sequences represented by
$\tau(\delta)$ can be obtained by investigating such reverse points.

Let $Q$ be the set of reverse points for every pair of variables. For the sake
of simplicity, let $Q=\\{\delta_{1},\ldots,\delta_{m}\\}$ where
$\delta_{1}\leq\cdots\leq\delta_{m}$ and $M=\\{1,\ldots,m\\}$. Subsequently,
we define $\Delta=\\{0,\gamma\\}\cup Q$, where $0<\gamma<\delta_{1}$. Of
course, $Q$ may be empty. In this case, we define $\gamma$ as any positive
real number.

######  Proposition 9.

For each $\delta\in\mathbb{R}_{+}$, there exists $q\in\Delta$ such that
$\tau(\delta)=\tau(q)$.

###### Proof.

We only consider the case when $\delta>0$ since it is clear when $\delta=0$.
Suppose that $Q=\emptyset$. This implies that $\tau(\delta)$ represents the
same variable sequence for each $\delta>0$. Therefore,
$\tau(\delta)=\tau(\gamma)$ for each $\delta>0$. Now, suppose that
$Q\neq\emptyset$ and let $\hat{\delta}>0$ be given. When
$0<\hat{\delta}<\delta_{1}$, then $\tau(\hat{\delta})=\tau(\gamma)$ since the
variable sequence indicated by $\tau(\delta)$ does not change when
$0<\delta<\delta_{1}$. When $\delta_{1}\leq\hat{\delta}<\delta_{m}$, there
exists $i\in M\setminus\\{m\\}$ such that
$\delta_{i}\leq\hat{\delta}<\delta_{i+1}$. Since there are no two variables
such that their relative order in $\tau(\delta)$ is reversed when
$\delta_{i}\leq\delta<\delta_{i+1}$, $\tau(\delta)$ does not change in this
range. Therefore, $\tau(\hat{\delta})=\tau(\delta_{i})$. If
$\hat{\delta}\geq\delta_{m}$, then $\tau(\hat{\delta})=\tau(\delta_{m})$ since
the variable sequence indicated by $\tau(\delta)$ does not change when
$\delta_{m}\leq\delta$. Therefore, the result follows. ∎∎

Proposition 9 states that $\tau(q)$’s for all $q\in\Delta$ can represent all
distinct variable sequences indicated by $\tau(\delta)$. Therefore, there
exists $q^{\star}\in\Delta$ such that $x(q^{\star})=x(\delta^{\star})$.
Accordingly, the NCR can be solved by comparing the objective values
corresponding to $x(q)$’s for all $q\in\Delta$. Although $|\Delta|$ is
$O(n^{2})$, examining all $x(q)$’s may be time-consuming when $n$ is large. In
the subsequent discussion, we show that $\Delta$ can be reduced by introducing
upper and lower bounds for $\delta^{\star}$.

Recall that $\delta^{\star}=\sum_{j\in N}\sigma_{j}^{2}x_{j}^{\star}$ where
$x^{\star}$ is an optimal solution for the non-convex relaxation. Based on
this definition, we define $\delta_{U}$ as

$\delta_{U}=\max_{x\in[0,1]^{n}}\left\\{\sum_{j\in
N}\sigma^{2}_{j}x_{j}:g(x)\leq b\right\\},$ (12)

and $\delta_{L}$ as

$\delta_{L}=\min_{x\in[0,1]^{n}}\left\\{\sum_{j\in
N}\sigma^{2}_{j}x_{j}:g(x)\geq b\right\\}.$ (13)

$x^{\star}$ is feasible for both the problem (12) and (13) since
$g(x^{\star})=b$ by Proposition 1. Therefore, $\delta_{U}$ and $\delta_{L}$
are upper and lower bounds for $\delta^{\star}$, respectively.

######  Proposition 10.

$\delta_{U}$ and $\delta_{L}$ can be obtained in $O(n\log n)$, respectively.

###### Proof.

The problem (12) is a special case of the CKP where $c_{j}=\sigma_{j}^{2}$ for
each $j\in N$. Let us consider the NCR of this problem. By definition, the set
$Q$ is empty since no two variables satisfy the condition (10). Accordingly,
$\Delta=\\{0,\gamma\\}$ and the problem (12) can be solved by comparing $x(0)$
and $x(\gamma)$ which can be constructed in $O(n\log n)$.

Now, let us consider the problem (13). Let $\tau_{\min}$ be the variable
sequence of $N$ sorted in ascending order of $\sigma_{j}^{2}/a_{j}$. We can
obtain $x(\tau_{\min})$ in $O(n\log n)$. We then show that $x(\tau_{\min})$ is
an optimal solution for the problem (13). Suppose that $x(\tau_{\min})$ is not
optimal for the problem (13). Then, there exists $\hat{x}$ such that
$g(\hat{x})\geq b$ and $\sigma(\hat{x})<\sigma(x(\tau_{\min}))$ where
$\sigma(x)=\sum_{j\in N}\sigma_{j}^{2}x_{j}$. Let us consider the following
problem.

$\displaystyle\min\quad$ $\displaystyle\sum_{j\in N}\sigma^{2}_{j}x_{j}$ s.t
$\displaystyle\sum_{j\in N}a_{j}x_{j}\geq
b-\Phi^{-1}(\rho)\sqrt{\sigma(x(\tau_{\min}))}$ (14) $\displaystyle
x\in[0,1]^{n},$

This problem is the LP relaxation of a min-knapsack problem, which can be
transformed into a fractional knapsack problem (Martello and Toth, 1990).
Accordingly, it can be easily shown that $x(\tau_{\min})$ is an optimal
solution for the problem (14), where the optimal objective value is
$\sigma(x(\tau_{\min}))$. On the other hand, $\hat{x}$ is also feasible for
this problem because

$\sum_{j\in N}a_{j}\hat{x}_{j}\geq
b-\Phi^{-1}(\rho)\sqrt{\sigma(\hat{x})}>b-\Phi^{-1}(\rho)\sqrt{\sigma(x(\tau_{\min}))}$

where the last inequality holds due to the assumption that
$\sigma(\hat{x})<\sigma(x(\tau_{\min}))$. Furthermore, the objective value of
the problem (14) corresponding to $\hat{x}$ is $\sigma(\hat{x})$ which is less
than $\sigma(x(\tau_{\min}))$. This result contradicts to the fact that
$x(\tau_{\min})$ is an optimal solution for the problem (14). Therefore, such
$\hat{x}$ cannot exist, and $x(\tau_{\min})$ is an optimal solution for the
problem (13). ∎∎

Proposition 10 states that the upper and lower bound for $\delta^{\star}$ can
be obtained efficiently. By utilizing these bounds, we define $\Delta^{\star}$
as follows.

$\Delta^{\star}=\\{q\in\Delta:\delta_{L}\leq
q\leq\delta_{U}\\}\cup\\{\max\\{\delta_{L},\gamma\\}\\}$

It is clear that $|\Delta^{\star}|\leq|\Delta|$. In addition, the following
result holds.

######  Proposition 11.

There exists $q^{\star}\in\Delta^{\star}$ such that
$\tau(q^{\star})=\tau(\delta^{\star})$.

###### Proof.

By Proposition 9, there exists $q\in\Delta$ such that
$\tau(q)=\tau(\delta^{\star})$. If $\delta_{L}\leq q\leq\delta_{U}$, then
$q\in\Delta^{\star}$. Suppose that $q<\delta_{L}$. We note that $\gamma\leq q$
in this case since $q=0$ implies that $\delta^{\star}=\delta_{L}=0$ as shown
in the proof of Proposition 9. Then, $\max\\{\delta_{L},\gamma\\}=\delta_{L}$
since $\gamma\leq q<\delta_{L}\leq\delta^{\star}$, that is,
$\delta_{L}\in\Delta^{\star}$. On the other hand,
$\tau(\delta_{L})=\tau(\delta^{\star})$ since $\tau(\delta^{\star})=\tau(q)$
implies that $\tau(\delta)=\tau(\delta^{\star})$ for each $\delta$ such that
$q\leq\delta\leq\delta^{\star}$. Now, suppose that $\delta_{U}<q$. Then,
$\delta_{L}\leq\delta^{\star}<q$, which implies that $q=\gamma$ by the proof
of Proposition 9. In this case, $\max\\{\delta_{L},\gamma\\}=\gamma$ and
$q=\gamma\in\Delta^{\star}$. Therefore, the result follows. ∎∎

Proposition 11 implies that the NCR can be solved by comparing $x(q)$’s for
all $q\in\Delta^{\star}$. Based on these results, we propose an efficient
algorithm for solving the NCR, described in Algorithm 1.

Algorithm 1 Algorithm for solving the NCR

1:$\delta_{U},\delta_{L}\leftarrow$ Solve the problem (12) and (13),
respectively ;

2:$\Delta^{\star}\leftarrow\emptyset$, $\delta_{1}\leftarrow\infty$, and
$z^{\star}\leftarrow 0$ ;

3:for $\\{k,l\\}\subseteq N$ do

4: if Condition (10) is satisfied then

5: $q\leftarrow$ Solve $p_{k}(\delta)=p_{l}(\delta)$ ;

6: $\delta_{1}\leftarrow q$ if $q<\delta_{1}$ ;

7: $\Delta^{\star}\leftarrow\Delta^{\star}\cup\\{q\\}$ if $\delta_{L}\leq
q\leq\delta_{U}$ ;

8: end if

9:end for

10:$\gamma\leftarrow\alpha$ such that $0<\alpha<\delta_{1}$ ;

11:$\Delta^{\star}\leftarrow\Delta^{\star}\cup\\{\max\\{\gamma,\delta_{L}\\}\\}$
;

12:for $q\in\Delta^{\star}$ do

13: Construct $\tau(q)$ and $x(q)$ ;

14: $z^{\star}\leftarrow\sum_{j\in N}c_{j}x_{j}(q)$ if $z^{\star}<\sum_{j\in
N}c_{j}x_{j}(q)$ ;

15:end for

16:return $z^{\star}$ ;

######  Theorem 3.

The NCR can be solved in $O(n^{3}\log n)$.

###### Proof.

$\delta_{L}$ and $\delta_{U}$ can be obtained in $O(n\log n)$ by Proposition
10. Hence, $\Delta^{\star}$ can be obtained in $O(n^{2})$, where
$|\Delta^{\star}|\leq n^{2}$. $x(q)$ for each $q\in\Delta^{\star}$ can be
constructed in $O(n\log n)$. Comparing the objective values corresponding to
$x(q)$’s for all $q\in\Delta$ can be performed in $O(n^{2})$. Therefore, the
NCR can be solved in $O(n^{3}\log n)$. ∎∎

Theorem 3 states that the non-convex relaxation can be solved in polynomial
time through the reformulation. In the following section, we show that an
approximate solution for the CKP can be derived from the optimal solution for
the non-convex relaxation, obtained through Algorithm 1.

##  4 Polynomial-time 1/2-approximation algorithm for the CKP based on the
non-convex relaxation

Here, let $x^{\star}$ be the optimal solution for the non-convex relaxation,
obtained through Algorithm 1. By definition, $x^{\star}$ has at most one
fractional variable, denoted as $t\in N$. We define $x^{D}$ and $x^{U}$ from
$x(\delta^{\star})$ in the same manner presented in the proof of Theorem 2,
i.e., $x_{j}^{D}=\lfloor x_{j}^{\star}\rfloor$ for each $j\in N$, while
$x^{U}_{t}=1$ and $x_{j}^{U}=0$ for each $j\in N\setminus\\{t\\}$. Then, it is
clear that $x^{D}$ and $x^{U}$ are feasible solutions for the CKP.

Now, let us define $x^{A}\in\\{0,1\\}^{n}$ as follows.

$x^{A}=\begin{cases}x^{D}&\text{, if }\sum_{j\in
N}c_{j}x^{U}_{j}\leq\sum_{j\in N}c_{j}x^{D}_{j}\\\ x^{U}&\text{,
otherwise.}\end{cases}$

######  Theorem 4.

$x^{A}$ is a 1/2-approximate solution for the CKP, which can be obtained in
$O(n^{3}\log n)$.

###### Proof.

By the feasibility of $x^{D}$ and $x^{U}$ for the CKP, $x^{A}$ is also a
feasible solution for the CKP. Recall that $z_{OPT}$ denotes the optimal
objective value of the CKP. We can derive the following inequalities from the
feasibility of $x^{D}$ and $x^{U}$.

$\sum_{j\in N}c_{j}x^{A}_{j}=\max\left\\{\sum_{j\in
N}c_{j}x^{U}_{j},\sum_{j\in N}c_{j}x^{D}_{j}\right\\}\leq\sum_{j\in
N}c_{j}x^{U}_{j}+\sum_{j\in N}c_{j}x^{D}_{j}\leq 2z_{OPT}$

This result implies that the objective value corresponding to $x^{A}$ is less
than or equal to $2z_{OPT}$. Therefore, $x^{A}$ is a 1/2-approximate solution
for the CKP. On the other hand, $x(\delta^{\star})$ can be obtained in
$O(n^{3}\log n)$ by Theorem 3, and $x^{A}$ can be derived from
$x(\delta^{\star})$ in $O(n)$. Hence, this 1/2-approximate solution can be
obtained in $O(n^{3}\log n)$. ∎∎

Theorem 4 directly leads us to devise a polynomial time 1/2-approximation
algorithm for the CKP using Algorithm 1. The detail are described in Algorithm
2.

Algorithm 2 Polynomial time 1/2-approximation algorithm for CKP

1:$x^{\star}\leftarrow$ Solve the non-convex relaxation using Algorithm 1 ;

2:$t\leftarrow$ fractional variable index in $x^{\star}$ ;

3:$x^{D}_{j}\leftarrow\lfloor x^{\star}_{j}\rfloor$ for all $j\in N$ ;

4:$x^{U}_{t}\leftarrow 1$ and $x^{U}_{j}\leftarrow 0$ for all $j\in
N\setminus\\{t\\}$ ;

5:if $\sum_{j\in N}c_{j}x^{U}_{j}\leq\sum_{j\in N}c_{j}x^{D}_{j}$ then

6: $x^{A}\leftarrow x^{D}$ ;

7:else

8: $x^{A}\leftarrow x^{U}$ ;

9:end if

10:return $x^{A}$ ;

In summary, we can obtain both quality-guaranteed upper and lower bounds for
the CKP in polynomial time from the non-convex relaxation using Algorithm 1
and 2. In the following section, we evaluate the efficiency of the proposed
algorithms and the quality of the obtained bounds through computational
experiments.

##  5 Computational test results

In this section, we present our computational experiments on the non-convex
relaxation and the proposed algorithms. First, we computationally compare
three continuous relaxations for the CKP, introduced in Section 2.
Subsequently, we evaluate the performance of the proposed approximation
algorithm. The result was compared with other solution approaches for the CKP.
All algorithms were implemented using C++ with optimization solvers provided
by XPRESS. Our tests were performed using a machine with an Intel Core i7,
3.10GHz CPU, and 16GB RAM.

Three types of the CKP instances were used in our experiments, which were
generated in the same manner with Han et al. (2016) as follows.

  * •

SC (strongly correlated): each $a_{j}$ is an integer value randomly chosen in
$[1,100]$ and $c_{j}=a_{j}+100$.

  * •

IC (inversely correlated): each $c_{j}$ is an integer value randomly chosen in
$[1,100]$ and $a_{j}=\min\\{100,c_{j}+10\\}$.

  * •

SS (subset sum): each $a_{j}$ is an integer value randomly chosen in $[1,100]$
and $c_{j}=a_{j}$.

The standard deviation $\sigma_{j}$ was randomly chosen in
$[0.1a_{j},0.2a_{j}]$ for each $j\in N$, and we set $b=\lfloor\sum_{j\in
N}a_{j}\rfloor$. For each combination of instance type (SC, IC, SS),
$n\in\\{100,500,1000,5000\\}$, and $\rho\in\\{0.9,0.95\\}$, we generated 10
instances, and the average results were reported.

###  5.1 Comparison of upper bounds provided by the continuous relaxations

We computationally compared the upper bounds for the CKP, $z_{C}$, $z_{P}$,
and $z_{NC}$ provided by the convex, non-convex, and polyhedral relaxations.
The convex relaxation was solved using the SOCP solver provided by XPRESS with
its default setting. We implemented the cutting-plane algorithm for the
polyhedral relaxation. Specifically, we iteratively added the constraints (3)
to the convex relaxation, where the convex relaxation with some of the
constraints (3) was solved using the SOCP solver provided by XPRESS. The
separation problem was solved using the greedy algorithm proposed by Edmond
(1970). Finally, the non-convex relaxation was solved using Algorithm 1. The
time limit was 600 seconds.

We present the average results specifically for $\rho=0.9$ in Table 1, as
there was no significant difference in the outcomes when $\rho=0.95$. Here,
“time(s)” denotes the average computation time required to solve each
continuous relaxation. “cgap($\%$)” indicates the average duality gap closed
by each continuous relaxation. It is calculated as

$\text{cgap($\%$)}=\frac{z_{C}-z}{z_{C}-z_{LB}}\times 100,$

where $z$ denotes the objective value of each continuous relaxation, and
$z_{LB}$ represents the best lower bound obtained by solving the ISP using
XPRESS with its default setting within a time limit of 1800 seconds. A larger
cgap implies a better quality of the upper bound. We marked the cgap value
with “$\star$” for instances not solved within the time limit. The number of
instances not solved is also given in parentheses. The column headed “#cut”
presents the average number of cutting planes added when solving the
polyhedral relaxation. In addition, we reported $|\Delta|$ and
$|\Delta^{\star}|$ investigated when solving the non-convex relaxation.

Table 1: Comparison of continuous relaxations for the CKP ($\rho=0.90$) Type |  $n$ | $z_{C}$ |  | $z_{P}$ |  | $z_{NC}$
---|---|---|---|---|---|---
|  | time(s) |  | cgap (%) | #cut | time(s) |  | cgap(%) |  $|\Delta|$ |  $|\Delta^{\star}|$ | time(s)
SC | 100 |  0.011 |  |  47.75 |  6.7 |  0.040 |  |  48.00 |  $7.3\times 10^{2}$ |  $4.0\times 10^{1}$ |  0.000
| 500 |  0.021 |  |  61.73 |  7.9 |  0.094 |  |  62.28 |  $1.8\times 10^{4}$ |  $5.8\times 10^{2}$ |  0.022
| 1000 |  0.032 |  |  54.08 |  7.3 |  0.129 |  |  55.02 |  $7.3\times 10^{4}$ |  $1.7\times 10^{3}$ |  0.147
| 5000 |  0.092 |  |  42.68 |  5.2 |  0.403 |  |  51.48 |  $1.8\times 10^{6}$ |  $1.8\times 10^{4}$ |  9.583
IC | 100 |  0.010 |  |  56.85 |  18.4 |  0.116 |  |  57.06 |  $3.4\times 10^{3}$ |  $4.7\times 10^{1}$ |  0.000
| 500 |  0.011 |  |  61.80 |  16.4 |  0.227 |  |  62.13 |  $8.5\times 10^{4}$ |  $5.2\times 10^{2}$ |  0.017
| 1000 |  0.019 |  |  54.73 |  15.7 |  0.292 |  |  55.24 |  $3.4\times 10^{5}$ |  $1.3\times 10^{3}$ |  0.096
| 5000 |  0.062 |  |  41.19 |  23.2 |  1.748 |  |  43.05 |  $8.7\times 10^{6}$ |  $1.2\times 10^{4}$ |  4.497
SS | 100 |  0.008 |  |  51.64 |  125.6 |  2.455 |  |  94.76 |  2 |  1 |  0.000
| 500 |  0.016 |  |  54.31⋆ |  562.0 |  362.3(6) |  |  91.22 |  2 |  1 |  0.001
| 1000 |  0.021 |  |  56.58⋆ |  410.4 |  306.6(5) |  |  91.16 |  2 |  1 |  0.002
| 5000 |  0.068 |  |  55.95 |  144.9 |  58.28 |  |  90.21 |  2 |  1 |  0.047
average |  0.031 |  |  53.27 |  112.0 |  61.06 |  |  66.80 |  $9.2\times 10^{5}$ |  $2.8\times 10^{3}$ |  1.201

As discussed in Section 2, the non-convex relaxation consistently improved the
duality gap compared to the polyhedral relaxation. The differences in bound
improvements between polyhedral and non-convex relaxations were insignificant
in SC and IC type instances, whereas the non-convex relaxation required more
computation time when $n\geq 1000$. Nevertheless, even when $n=5000$, the non-
convex relaxation could provide upper bounds for the CKP, which are tighter
than $z_{C}$ and $z_{P}$, within 10 seconds. The lower and upper bounds for
$\delta^{\star}$ significantly contributed to this result, as indicated in
columns $|\Delta|$ and $|\Delta^{*}|$. These bounds substantially reduced the
number of reverse points investigated in $\Delta$. Without these bounds,
solving the non-convex relaxation took longer computation time, increasing
proportionally to the ratio of $|\Delta^{\star}|$ to $|\Delta|$.

On the other hand, the non-convex relaxation outperformed the other continuous
relaxations for SS type instances, both in terms of the quality of upper
bounds and computation time. In this case, the cutting-plane algorithm for the
polyhedral relaxation did not terminate within the time limit for some
instances. However, the non-convex relaxation could be solved significantly
faster, even compared to the convex relaxation. This result can be explained
by the absence of reverse points for SS type instances, as $c_{j}=a_{j}$ for
each $j\in N$, meaning $Q=\emptyset$.

###  5.2 Performance of the proposed approximation algorithm

We evaluated the performance of the proposed approximation algorithm for the
CKP. The results were compared with the robust optimization-based heuristic
algorithm proposed by Joung and Lee (2020) and the branch-and-bound algorithm
provided by XPRESS, which we refer to as the RO heuristic and BnB,
respectively. When we tested the RO heuristic, the parameter associated with
the algorithm’s step size was set to $K=3$ as recommended in Joung and Lee
(2020). The BnB solves the ISP using XPRESS with its default setting. The time
limit for the BnB was set to 1800 seconds.

We also implemented the robust optimization-based approach by Han et al.
(2016) and PTAS by Goyal and Ravi (2010). For the algorithm by Han et al.
(2016), the parameter was set to as recommended in their paper. We set
$\epsilon=1/6$ for the PTAS to obtain a $1/2$-approximate solution. However,
these algorithms failed to find a feasible solution even after 2 hours, as
observed by Joung and Lee (2020). Hence, we did not report the results of
these algorithms.

Table 2 shows the results of the proposed algorithm, RO heuristic, and the
BnB. The column headed “time (s)” denotes the computation time for each
algorithm. “gap ($\%$)” refers to the duality gaps of the obtained objective
values, computed as follows.

$\text{gap ($\%$)}=\frac{z_{UB}-\hat{z}}{z_{UB}}\times 100$

Here, $\hat{z}$ denotes the objective values corresponding to the feasible
solutions found in each algorithm. $z_{UB}$ indicates the best upper bound,
which is the smaller of the upper bounds obtained from the BnB and non-convex
relaxation. A smaller gap implies a better feasible solution. When the average
gap value of the BnB result is greater than $0$, we presented the number of
instances not solved to optimality in parentheses.

Table 2: Comparison of the proposed approximation algorithm and other solution approaches for the CKP ($\rho=0.9$) Type |  $n$ | Proposed |  | RO heuristic |  | BnB
---|---|---|---|---|---|---
|  | gap(%) | time(s) |  | gap(%) | time(s) |  | gap(%) | time(s)
SC | 100 |  1.357 |  0.001 |  |  0.013 |  0.080 |  |  0 |  69.564
| 500 |  0.247 |  0.023 |  |  0.014 |  0.855 |  |  0.016 |  920.08(5)
| 1000 |  0.103 |  0.149 |  |  0.017 |  3.624 |  |  0.011 |  1462.7(8)
| 5000 |  0.032 |  9.621 |  |  0.005 |  98.12 |  |  0.004 |  1800.0(10)
IC | 100 |  1.360 |  0.001 |  |  0.004 |  0.063 |  |  0 |  40.523
| 500 |  0.279 |  0.017 |  |  0.007 |  0.452 |  |  0.009 |  563.12(3)
| 1000 |  0.144 |  0.096 |  |  0.006 |  1.477 |  |  0.009 |  1083.0(6)
| 5000 |  0.016 |  4.560 |  |  0.002 |  27.73 |  |  0.004 |  1621.6(9)
SS | 100 |  1.494 |  0.001 |  |  0.031 |  0.059 |  |  0.017 |  366.48(2)
| 500 |  0.311 |  0.001 |  |  0.021 |  0.344 |  |  0.086 |  1800.0(10)
| 1000 |  0.135 |  0.002 |  |  0.015 |  0.864 |  |  2.198 |  1800.0(10)
| 5000 |  0.037 |  0.047 |  |  0.007 |  15.54 |  |  23.81 |  1800.0(10)
average |  0.459 |  1.204 |  |  0.012 |  12.43 |  |  2.180 |  1110.6

As discussed in Section 4, the proposed approximation algorithm guarantees
that the integrality gaps of the obtained solutions are less than or equal to
$50\%$. However, in our experiments, the observed duality gaps were
significantly below $50\%$ for all instances, although the duality gaps are
greater than or equal to the integrality gaps by definition.

The RO heuristic provided near-optimal solutions with gaps of less than
$0.05\%$ for all instances within about 100 seconds. Furthermore, for some
instances of IC and SS types, the solutions obtained through the RO heuristic
outperformed those obtained by the BnB within the time limit.

The solutions obtained through our approximation algorithm were not better
than those found in the RO heuristic. However, our algorithm found feasible
solutions in significantly less time than the RO heuristic, while the duality
gaps of the obtained solutions were not large ($<0.5\%$ on average).
Furthermore, our algorithm outperformed the BnB for large SS type instances,
both in terms of the quality of solutions and computation time. Therefore, our
algorithm may be more effective than the RO heuristic when solving numerous
CKPs, such as sub-problems of large-scale integer programs. Additionally, our
algorithm ensures solution quality and does not require tuning parameters, in
contrast to the RO heuristic.

##  6 Conclusion

In this study, we introduced a non-convex relaxation for the CKP and compared
it with other continuous relaxations. We showed that the non-convex relaxation
provides an upper bound for the CKP, at least as tight as those obtained from
the other continuous relaxations. We also showed that the non-convex
relaxation provides both upper and lower bounds for the CKP in polynomial
time, where the quality of the bounds is ensured. The computational test
results demonstrated that these upper and lower bounds are tight for the CKP
and obtainable within a short time. The proposed approximation algorithm may
be utilized as a heuristic algorithm for solving numerous CKPs, such as sub-
problems of large-scale integer programs. Furthermore, the upper bounds
provided by the non-convex relaxation can be used in the lifting technique for
probabilistic cover inequalities for the CKP, proposed by Atamtürk and
Narayanan (2009). To enhance the effectiveness of our results in these
applications, developing more efficient solution approach for the non-convex
relaxation is necessary. It is also an interesting research direction to
develop solution approaches based on continuous relaxations for the CKP under
different probability distributions.

## References

  * Atamtürk and Narayanan (2008) Atamtürk A, Narayanan V (2008) Polymatroids and mean-risk minimization in discrete optimization. Operations Research Letters 36(5):618–622
  * Atamtürk and Narayanan (2009) Atamtürk A, Narayanan V (2009) The submodular knapsack polytope. Discrete Optimization 6(4):333–344
  * Ben-Tal and Nemirovski (1998) Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Mathematics of operations research 23(4):769–805
  * Ben-Tal et al. (2009) Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization, vol 28. Princeton university press
  * Bertsimas and Popescu (2005) Bertsimas D, Popescu I (2005) Optimal inequalities in probability theory: A convex optimization approach. SIAM Journal on Optimization 15(3):780–804
  * Bertsimas and Sim (2004) Bertsimas D, Sim M (2004) The price of robustness. Operations research 52(1):35–53
  * Birge and Louveaux (2011) Birge JR, Louveaux F (2011) Introduction to stochastic programming. Springer Science & Business Media
  * Charnes et al. (1958) Charnes A, Cooper WW, Symonds GH (1958) Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Management science 4(3):235–263
  * Conforti et al. (2014) Conforti M, Gérard C, Zambelli G (2014) Integer Programming. Springer International Publishing
  * Dantzig (1957) Dantzig GB (1957) Discrete-variable extremum problems. Operations research 5(2):266–288
  * Edmond (1970) Edmond J (1970) Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and Their Applications, Gordon and Breach, Louvain, pp 69–87
  * Ghaoui et al. (2003) Ghaoui LE, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Operations research 51(4):543–556
  * Gilmore and Gomory (1961) Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Operations research 9(6):849–859
  * Goyal and Ravi (2010) Goyal V, Ravi R (2010) A ptas for the chance-constrained knapsack problem with random item sizes. Operations Research Letters 38(3):161–164
  * Han et al. (2016) Han J, Lee K, Lee C, Choi KS, Park S (2016) Robust optimization approach for a chance-constrained binary knapsack problem. Mathematical Programming 157(1):277–296
  * Iida (1999) Iida H (1999) A note on the max-min 0-1 knapsack problem. Journal of Combinatorial Optimization 3:89–94
  * Joung and Lee (2020) Joung S, Lee K (2020) Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity. Optimization Letters 14(1):101–113
  * Kellerer et al. (2004) Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems. Springer, Berlin, Germany
  * Kosuch and Lisser (2010) Kosuch S, Lisser A (2010) Upper bounds for the 0-1 stochastic knapsack problem and a b&b algorithm. Annals of Operations Research 176:77–93
  * Martello and Toth (1990) Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc.
  * Merzifonluoğlu et al. (2012) Merzifonluoğlu Y, Geunes J, Romeijn HE (2012) The static stochastic knapsack problem with normally distributed item sizes. Mathematical Programming 134(2):459–489
  * Savelsbergh (1997) Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Operations research 45(6):831–841
  * Shabtai et al. (2018) Shabtai G, Raz D, Shavitt Y (2018) A relaxed fptas for chance-constrained knapsack. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
  * Yu (1996) Yu G (1996) On the max-min 0-1 knapsack problem with robust optimization applications. Operations Research 44(2):407–415