A Two-Phase Method for Solving Continuous Rank-One Quadratic Knapsack Problems

Sayyed Ehsan Monabbati [email protected] Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

Abstract

In this paper, we propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R1QKP). In particular, we study the solution structure of the problem without the knapsack constraint. We propose an $O(n\log n)$ algorithm in this case. We then use the solution structure to propose an $O(n^{2}\log n)$ algorithm that finds an interval containing the optimal value of the Lagrangian dual of R1QKP. In the second phase, we solve the restricted Lagrangian dual problem using a traditional single-variable optimization method. We perform a computational test on random instances and compare our algorithm with the general solver CPLEX.

keywords:

Quadratic Knapsack Problem , Line-Sweep Algorithm

^†^†journal: …

\DeclareNewFootnote

B[alph]

1 Introduction

The quadratic knapsack problem (QKP) deals with minimizing a quadratic function over one allocation constraint together with simple bounds on decision variables. Formally, this problem can be written as to


$\displaystyle\operatorname{minimize}\quad$	$\displaystyle\frac{1}{2}x^{\top}Qx-c^{\top}x,$	(1a)
$\displaystyle\operatorname{subject\;to}\quad$	$\displaystyle a^{\top}x=b,$	(1b)
	$\displaystyle 0\leq x\leq u,$	(1c)

where $Q$ is a symmetric $n\times n$ matrix, $a,c,l,u\in\mathbb{R}^{n}$ and $b\in\mathbb{R}$ . QKP as a quadratic optimization problem is polynomially solvable when $Q$ is positive definite matrix [12]. When $Q$ is diagonal with strictly positive diagonal entries QKP can be viewed as a strictly convex separable optimization problem that has many applications (e.g. resource allocation [14, 13, 2] and multicommodity network flows [9]). The solution methods for solving this type of QKPs usually rely on the fact that the optimal solution of the Lagrangian dual subproblems can be explicitly obtained in terms of the Lagrange multiplier $\lambda$ of (1b). Therefore the problem reduces to find a value for $\lambda$ such that the solution of the corresponding Lagrangian subproblem is satisfied in equality constraint (1b). The resulting equation is solved by different methods. Helgason et. al [9] propose an $O(n\log n)$ algorithm for solving the equation based on searching breakpoints of the Lagrangian dual problem. Brucker [3] finds an $O(n)$ bisection algorithm based on the properties of the Lagrangian dual function. Dai and Fletcher [5] propose a two-phase method; A bracketing phase that determines an interval containing the solution followed by the secant phase that approximates the solution within the promising interval. This method is modified by Comminetti et. al [4] with ignoring the bracketing phase and using a semi-smooth Newton method instead of the secant method. Liu and Yong-Jin [11] consider a special case of the strictly convex form of the problem. They find the solution structure of the subproblems and use it in a modified secant algorithm.

Robinson et. al [15] use the geometric interpretation of the problem and propose an algorithm that works in the primal space rather than the dual space. This algorithm iteratively fixes variables and terminates after at most $n$ iterations.

In a more general case, when $Q$ is positive semidefinite in (1), Dussault et. al [7] propose an iterative algorithm in which a QKP with diagonal $Q$ should be solved in each iteration. Paradalos et. al [12] suggest a potential reduction algorithm to solve this class of QKP. di Serafino et. al [6] propose a two-phase gradient projection that has acceptable numerical performance in comparison with similar gradient-based methods.

QKPs with positive definite $Q$ are also solved by a gradient projection method [5], and an augmented-Lagrangian approach [8].

In this paper, we suppose $Q$ is a rank one symmetric matrix, that is $Q=qq^{\top}$ for some $q\in\mathbb{R}^{n}$ . Moreover, we assume that $0<u$ . Without loss of generality we assume that $q_{i}\neq 0$ for each $i$ . By the following change of variables

\displaystyle x_{i}\leftarrow q_{i}x_{i},\quad c_{i}\leftarrow\frac{c_{i}}{q_{i}},\quad a_{i}\leftarrow\frac{a_{i}}{q_{i}},\quad l_{i}\leftarrow\min\{0,q_{i}u_{i}\},\quad u_{i}\leftarrow\max\{0,q_{i}u_{i}\},

problem (1) is reduced to


$\displaystyle\operatorname{minimize}\quad$	$\displaystyle\frac{1}{2}({\boldsymbol{1}}^{\top}x)^{2}-c^{\top}x,$	(2a)
$\displaystyle\operatorname{subject\;to}\quad$	$\displaystyle a^{\top}x=b,$	(2b)
	$\displaystyle 0\leq x\leq u.$	(2c)

Sharkey et. al [16] study a class of nonseparable nonlinear knapsack problems in which one has to

$\displaystyle\operatorname{minimize}$	$\displaystyle g(s^{\top}x)-c^{\top}x,$	(3)
$\displaystyle\operatorname{subject\;to}$	$\displaystyle a^{\top}x=b,$
	$\displaystyle l\leq x\leq u,$

where $g:\mathbb{R}\to\mathbb{R}$ is an arbitrary real-valued function, and $s\in\mathbb{R}^{n}$ is given. They introduce an algorithm for solving (3) that runs in $O(n^{2}\max\{\log n,\phi\})$ , where $\phi$ is the time required to solve a single-variable optimization problem $\min\{g(S)-\alpha S\;:\;L\leq S\leq U\}$ for given $\alpha,L,U\in\mathbb{R}$ . With $g(t)=t^{2}$ and $s$ equals to the all-one vector, problem (2) is a special case of problem (3). That is, there exists an $O(n^{2}\max\{\log n,1\})=O(n^{2}\log n)$ algorithm for solving problem (2).

In this paper, we propose a two-phase algorithm for problem (2). In section 2 we study the solution structure of the bounded version of the problem in which the equality constraint (2b) is omitted. We show that the bounded version could be solved in $O(n\log n)$ time. In section 3, in phase I, we use the solution structure of the bounded version to find an interval that may contain the optimal value of the Lagrangian dual function. This is done in $O(n^{2}\log n)$ time in the worst case. Then, we perform phase II, in which we explore the interval by a single-variable optimization method to find the optimal Lagrangian multiplier with desired precision. In section 4, we perform a computational test. In particular, we compare the algorithm with the general quadratic programming solver CPLEX.

2 Solution structure of the bounded version

In this section we consider the following bounded version of the problem


$\displaystyle\operatorname{minimize}\quad$	$\displaystyle f(x)=\frac{1}{2}({\boldsymbol{1}}^{\top}x)^{2}-c^{\top}x,$	(4a)
$\displaystyle\operatorname{subject\;to}\quad$	$\displaystyle 0\leq x\leq u.$	(4b)

We propose a characterization of the solution in the primal space. Note that most of algorithms for such problems use the so-called KKT conditions to study the solution structure. Without loss of generality, we assume that $c_{1}\geq c_{2}\geq\cdots\geq c_{n}\geq 0$ , and $l_{i}=0$ , $i=1,\cdots,n$ . Given two vectors $a,b\in\mathbb{R}^{n}$ , we denote the set $\{x\;:\;a\leq x\leq b\}$ by $[a,b]$ . Finally, given vector $u\in\mathbb{R}^{n}$ we define $U_{k}=\sum_{i=1}^{k}u_{i}$ for $k=1,\cdots,n$ , and $U_{0}=0$ .

We begin with preliminary lemmas.

Lemma 2.1.

For $k=1,\cdots,n$ define $x^{(k)}$ as

\displaystyle x_{i}^{(k)}=\begin{cases}u_{i},&i=1,\dots,k,\\ 0,&i=k+1,\dots,n,\end{cases}

and $x^{(0)}$ as the all-zero vector, and, define $G_{k}$ as

G_{k}=\frac{1}{2}\left(U_{k}+U_{k-1}\right)-c_{k}=U_{k-1}+\frac{1}{2}u_{k}-c_{k}.

Then the following assertions hold

1.

If $\bar{n}$ is the smallest index in $\{1,\cdots,n\}$ such that $G_{\bar{n}}\geq 0$ then $\min_{i=1,\cdots,n}f(x^{(i)})=f(x^{(\bar{n}-1)})$ .
2.

If $G_{k}<0$ for all $k=1,\cdots,n-1$ then $\min_{i=1,\cdots,n}f(x^{(i)})=f(x^{(n)})$ .

Proof.

(1) For $1\leq k\leq n-1$ we have

	$\displaystyle G_{k}-G_{k+1}$	$\displaystyle=\frac{1}{2}\left(U_{k}+U_{k-1}\right)-c_{k}-\frac{1}{2}\left(U_{k+1}+U_{k}\right)+c_{k+1}$
		$\displaystyle=-\frac{1}{2}\left(u_{k}+u_{k+1}\right)+(c_{k+1}-c_{k})$
		$\displaystyle<0\cdot$

Thus

G_{1}<G_{2}<\cdots<G_{\bar{n}-1}<0\leq G_{\bar{n}}<G_{\bar{n}+1}<\cdots<G_{n}.

On the other hand, for $1\leq k\leq n-1$ we have

$\displaystyle f(x^{(k+1)})-f(x^{(k)})$	$\displaystyle=\frac{1}{2}U_{k+1}^{2}-\sum_{i=1}^{k+1}u_{i}c_{i}-\frac{1}{2}U_{k}^{2}+\sum_{i=1}^{k}u_{i}c_{i}$	(5)
	$\displaystyle=\frac{1}{2}U_{k+1}^{2}-u_{k+1}c_{k+1}-\frac{1}{2}U_{k}^{2}$
	$\displaystyle=\frac{1}{2}(U_{k+1}^{2}-U_{k}^{2})-u_{k+1}c_{k+1}$
	$\displaystyle=\frac{1}{2}(U_{k+1}-U_{k})(U_{k+1}+U_{k})-u_{k+1}c_{k+1}$
	$\displaystyle=u_{k+1}\left(\frac{1}{2}(U_{k+1}+U_{k})-c_{k+1}\right)$
	$\displaystyle=u_{k+1}G_{k+1}.$

Now let $m>\bar{n}-1$ . Then

	$\displaystyle f(x^{(m)})-f(x^{(\bar{n}-1)})$	$\displaystyle=f(x^{(m)})-f(x^{(m-1)})+f(x^{(m-1)})+\cdots+f(x^{(\bar{n})})-f(x^{(\bar{n}-1)})$
		$\displaystyle=u_{m}G_{m}+\cdots+u_{\bar{n}}G_{\bar{n}}>G_{\bar{n}}(u_{m}+\cdots+u_{\bar{n}+1})$
		$\displaystyle>0.$

Similarly, if $m<\bar{n}-1$ , then we have $f(x^{(m)})-f(x^{(\bar{n}-1)})>0$ .

(2) The second part can be easily proved considering (5). ∎

We need the following result about two-dimensional version of problem (4).

Lemma 2.2.

Consider the following optimization problem

$\displaystyle\operatorname{minimize}$	$\displaystyle f(x_{1},x_{2})=\frac{1}{2}(x_{1}+x_{2})^{2}-c_{1}x_{1}-c_{2}x_{2},$	(6)
$\displaystyle\operatorname{subject\;to}$	$\displaystyle 0\leq x_{1}\leq u_{1},$
	$\displaystyle 0\leq x_{2}\leq u_{2},$

where $c_{1}\geq c_{2}\geq 0$ and $u_{1}$ and $u_{2}$ are real constants. Define set $I=I_{1}\cup I_{2}$ where $I_{1}=\{(u_{1},x_{2})\;:\;0\leq x_{2}\leq u_{2}\}$ and $I_{2}=\{(x_{1},0)\;:\;0\leq x_{1}\leq u_{1}\}$ . Then, problem (6) has no optimal solution outside of $I$ .

Proof.

If $c_{1}=c_{2}$ , then $f(x_{1},x_{2})=\frac{1}{2}(x_{1}+x_{2})^{2}-c_{1}(x_{1}+x_{2})=\frac{1}{2}z^{2}-c_{1}z=g(z)$ where $z=x_{1}+x_{2}$ . It is easy to see that $x^{\ast}=(x_{1}^{\ast},x_{2}^{\ast})$ with $x_{1}^{\ast}=\min\{c_{1},u_{1}\}$ and $x_{2}^{\ast}=\min\{c_{1}-x_{1}^{\ast},u_{2}\}$ is the optimal solution of the problem, and we have $x^{\ast}\in I$ . Assume that $c_{1}\neq c_{2}$ . The feasible region of (6) is equal to $I_{1}\cup I_{2}\cup I_{3}\cup I_{4}$ where $I_{3}=\{(x_{1},x_{2})\;:\;0<x_{1}<u_{1},0<x_{2}<u_{2}\}$ and $I_{4}=\{(0,x_{2})\;:\;0<x_{2}<u_{2}\}\cup\{(x_{1},u_{2})\;:\;0<x_{1}<u_{1}\}$ . We show that there is no optimal solution in $I_{3}$ and $I_{4}$ . Indeed, we write the KKT optimality conditions as follows

	$\displaystyle x_{1}+x_{2}-c_{1}+\alpha_{1}-\alpha_{2}=0,$		(7)
	$\displaystyle x_{1}+x_{2}-c_{2}+\beta_{1}-\beta_{2}=0,$		(8)
	$\displaystyle\alpha_{1}(x_{1}-u_{1})=0,\quad\alpha_{2}x_{1}=0,$		(9)
	$\displaystyle\beta_{1}(x_{2}-u_{2})=0,\quad\beta_{2}x_{2}=0,$		(10)
	$\displaystyle 0\leq x_{1}\leq u_{1},$		(11)
	$\displaystyle 0\leq x_{2}\leq u_{2},$		(12)
	$\displaystyle\alpha_{1},\alpha_{2},\beta_{1},\beta_{2}\geq 0,$		(13)

where $\alpha_{i}$ and $\beta_{i}$ , $i=1,2$ are KKT multipliers corresponding to the bound constraints. If $(x_{1},x_{2})\in I_{3}$ then from (9) and (10) we have $\alpha_{1}=\alpha_{2}=\beta_{1}=\beta_{2}=0$ . Substituting these values in (7) and (8) implies that $c_{1}=c_{2}$ which contradicts our assumption. On the other hand, if $(x_{1},x_{2})\in I_{4}$ and $x_{1}=0$ , then we have $\alpha_{1}=0$ . Now, (7) implies that $x_{2}=c_{1}+\alpha_{2}<0$ . Thus $\beta_{2}=0$ . From (8) we have $x_{2}=c_{2}-\beta_{1}$ . Therefore, $c_{2}=c_{1}+\alpha_{2}+\beta_{1}\geq c_{1}$ . This contradicts our assumption on $c_{i}$ s. That is, problem (6) has no optimal solution with $x_{1}=0$ . By similar argument one can conclude that (6) has no solution with $x_{2}=u_{2}$ . This completes the proof. ∎

Theorem 2.3.

Suppose $x^{(k)}$ and $G_{k}$ , $k=1,\cdots,n$ and $\bar{n}$ are defined as in Lemma 2.1. Then the following assertions hold

If $\bar{n}>1$ , then define $\delta_{1},\delta_{2}$ as $\delta_{1}=\min\left\{c_{\bar{n}-1}-U_{\bar{n}-2},u_{\bar{n}-1}\right\}$ and $\delta_{2}=\max\left\{c_{\bar{n}}-U_{\bar{n}-1},0\right\}$ . Also, define $\bar{x}$ , $\tilde{x}$ as

\bar{x}=x^{(\bar{n}-2)}+\delta_{1}e_{\bar{n}-1},\quad\tilde{x}=x^{(\bar{n}-1)}+\delta_{2}e_{\bar{n}},

where $e_{i}$ is the $i$ th column of the identity matrix of dimension $n$ . Then $\min\{f(\bar{x}),f(\tilde{x})\}$ is the optimal value of the following optimization problem

	$\displaystyle\operatorname{minimize}$	$\displaystyle f(x),$		(14)
	$\displaystyle\operatorname{subject\;to}$	$\displaystyle x^{(\bar{n}-2)}\leq x\leq x^{(\bar{n})}.$		(14)

2.

If $\bar{n}=1$ , then define $\delta=\min\{c_{1},u_{1}\}$ . Also define $\tilde{x}=\delta e_{1}$ . Then $f(\tilde{x})$ is the optimal value of the following optimization problem

$\displaystyle\operatorname{minimize}$ $\displaystyle f(x),$

$\displaystyle\operatorname{subject\;to}$ $\displaystyle x^{(0)}\leq x\leq x^{(1)}.$
3.

if $G_{k}<0$ for all $k=1,\cdots,n$ , then define $\delta=\min\{c_{n}-U_{n-1},u_{n}\}$ . Also define $\tilde{x}=x^{(n-1)}+\delta e_{n}$ . Then $f(\tilde{x})$ is the optimal value of the following optimization problem

$\displaystyle\operatorname{minimize}$ $\displaystyle f(x),$

$\displaystyle\operatorname{subject\;to}$ $\displaystyle x^{(n-1)}\leq x\leq x^{(n)}.$

Proof.

(1) By Lemma 2.2 we can partition the optimal solution set as $I_{1}\cup I_{2}$ where $I_{1}=[x^{(\bar{n}-2)},x^{(\bar{n}-1)}]$ and $I_{2}=[x^{(\bar{n}-1)},x^{(\bar{n})}]$ . We show that $f(\bar{x})=\min\{f(x):x\in I_{1}\}$ and $f(\tilde{x})=\min\{f(x):x\in I_{2}\}$ . Indeed, we use a simple technique of single-variable calculus. Let $x\in I_{1}$ , then $x=x(\delta)$ , for some $\delta\in[0,u_{\bar{n}-1}]$ , where $x(\delta)=x^{(\bar{n}-2)}+\delta e_{\bar{n}-1}$ . Thus the problem $\min\{f(x):x\in I_{1}\}$ reduces to $\min\{f(x(\delta)):0\leq\delta\leq u_{\bar{n}-1}\}$ . On the other hand, one can write

f(x(\delta))=\frac{1}{2}\left(U_{\bar{n}-2}+\delta\right)^{2}-\sum_{i=1}^{\bar{n}-2}c_{i}u_{i}-c_{\bar{n}-1}\delta.

We have $df(x(\delta))/d\delta=U_{\bar{n}-2}+\delta-c_{\bar{n}-1}$ . Thus $df(x(\delta))/d\delta=0$ only if $\delta=\delta^{\prime}=c_{\bar{n}-1}-U_{\bar{n}-2}$ . Since $d^{2}f(x(\delta))/d\delta^{2}>0$ and $\delta^{\prime}>\frac{1}{2}u_{\bar{n}-1}$ the optimal value is achieved at $\delta_{1}$ .

To prove $f(\tilde{x})=\min\{f(x):x\in I_{2}\}$ , by the same argument as the previous paragraph, it suffices to solve single optimization problem $\min\{f(x(\delta)):0\leq\delta\leq u_{\bar{n}}\}$ , where $x(\delta)=x^{(\bar{n}-1)}+\delta e_{\bar{n}}$ . It is easy to see that if $\delta=\delta^{\prime}=c_{\bar{n}}-U_{\bar{n}-1}$ then $df(x(\delta))/d\delta=0$ . Since $\delta^{\prime}\leq\frac{1}{2}u_{\bar{n}}$ , by definition of $\bar{n}$ , then $f(\tilde{x})$ is the optimal value of $\min\{f(x):x\in I_{2}\}$ .

The proof of parts (2) and (3) is similar. ∎

The following Corollary 2.4 states simple conditions under which the optimal solution of the problem in Theorem 2.3(1) is $\bar{x}$ or $\tilde{x}$ .

Corollary 2.4.

In Theorem 2.3(1),

1.

if $\delta_{1}=u_{\bar{n}-1}$ then $\min\{f(\bar{x}),f(\tilde{x})\}=f(\tilde{x})$ , and,
2.

if $\delta_{2}=0$ then $\min\{f(\bar{x}),f(\tilde{x})\}=f(\bar{x})$ .

Proof.

For brevity, we just prove part (1). The proof of the second part is similar. Under the assumption of part (1), we have

f(\bar{x})-f(\tilde{x})=\frac{1}{2}U_{\bar{n}-1}^{2}-\sum_{i=1}^{\bar{n}-1}c_{i}u_{i}-\frac{1}{2}c_{\bar{n}}^{2}+\sum_{i=1}^{\bar{n}-1}c_{i}u_{i}+c_{\bar{n}}(c_{\bar{n}}-U_{\bar{n}-1})=\frac{1}{2}\left(U_{\bar{n}-1}-c_{\bar{n}}\right)^{2}\geq 0.

∎

Theorem 2.3 solves a restricted version of problem (2). In the following theorem, we show that the solution of the restricted version is the solution of the original problem.

Theorem 2.5.

Define $G_{k}$ ’s, $x^{(k)}$ ’s, $\bar{n}$ , $\bar{x}$ and $\tilde{x}$ as in Theorem 2.3. Then, the following assertions hold

1.

If $1<\bar{n}\leq n$ , then $\min\{f(\bar{x}),f(\tilde{x})\}$ is the optimal value of (4), where $\tilde{x}$ and $\bar{x}$ are defined as in Theorem 2.3(1).
2.

If $\bar{n}=1$ , then $f(\tilde{x})$ is the optimal value of (4), where $\tilde{x}$ is defined as in Theorem 2.3(2).
3.

If $G_{k}<0$ for all $k=1,\cdots,n$ , then $f(\tilde{x})$ is the optimal solution of (4), where $\tilde{x}=x^{(n-1)}+\delta^{\prime}e_{n}$ , and $\delta^{\prime}=\min\{c_{n}-U_{n-1},u_{n}\}$ .

Proof.

For two vectors $x,z\in\mathbb{R}^{n}$ we have

\displaystyle f(z)-f(x)

\displaystyle=\frac{1}{2}({\boldsymbol{1}}^{\top}z+{\boldsymbol{1}}^{\top}x)({\boldsymbol{1}}^{\top}z-{\boldsymbol{1}}^{\top}x)-c^{\top}(z-x).

(15)

Let $x$ be a feasible solution of (4). If $x=u=x^{(n)}$ , then from the definition of $\bar{n}$ we have $f(x^{\bar{n}-1})\leq f(x)$ , and the result follows from Theorem 2.3. Suppose $x\neq u$ . We show there exists a specially structured feasible solution $x^{\prime}$ that is better than $x$ . Indeed, let $k$ be such that

U_{k}\leq{\boldsymbol{1}}^{\top}x<U_{k+1}.

Define vector $x^{\prime}$ by

x^{\prime}_{i}=\begin{cases}u_{i},&i=1,\cdots,k,\\ {\boldsymbol{1}}^{\top}x-U_{k},&i=k+1,\\ 0,&i=k+2,\cdots,n.\end{cases}

Then, clearly $x^{\prime}$ is feasible for (4) and

\displaystyle{\boldsymbol{1}}^{\top}x^{\prime}=\sum_{i=1}^{k}x^{\prime}_{i}+x^{\prime}_{k+1}+\sum_{i=k+2}^{n}x^{\prime}_{i}=\sum_{i=1}^{k}u_{i}+\sum_{i=1}^{n}x_{i}-\sum_{i=1}^{k}u_{i}={\boldsymbol{1}}^{\top}x.

Moreover we have

$\displaystyle c^{\top}x^{\prime}$	$\displaystyle=\sum_{i=1}^{k}u_{i}c_{i}+c_{k+1}x^{\prime}_{k+1}=\sum_{i=1}^{k}u_{i}c_{i}+c_{k+1}\sum_{i=1}^{n}x_{i}-c_{k+1}\sum_{i=1}^{k}u_{i}$
	$\displaystyle=\sum_{i=1}^{k}u_{i}c_{i}+c_{k+1}\sum_{i=1}^{k}x_{i}+c_{k+1}\sum_{i=k+1}^{n}x_{i}-c_{k+1}\sum_{i=1}^{k}u_{i}$
	$\displaystyle\geq\sum_{i=1}^{k}u_{i}c_{i}+\sum_{i=1}^{k}(x_{i}-u_{i})c_{i}+\sum_{i=k+1}^{n}x_{i}c_{i}$	(by monotonicity of $c_{i}$ ’s)
	$\displaystyle=c^{\top}x.$

Therefor, (15) implies that $f(x^{\prime})-f(x)=-c^{\top}(x^{\prime}-x)\leq 0$ , i.e. $f(x^{\prime})\leq f(x)$ .

(1) Now, we consider three cases for index $k$ introduced in the definition of $x^{\prime}$ : $k\geq\bar{n}$ , $k<\bar{n}-2$ and $k=\bar{n}-1,\bar{n}-2$ . In the latter case, we have $x^{(\bar{n}-2)}\leq x^{\prime}\leq x^{(\bar{n})}$ , so the assertion is true by Theorem 2.3, since

\min\{f(\bar{x}),f(\tilde{x})\}=\min\{f(x)\;:\;x\in[x^{(\bar{n}-2)},x^{(\bar{n})}]\}\leq f(x^{\prime})\leq f(x).

We show in both the other cases there is a point in the set $\{x^{(i)}\}_{i=1,\cdots,n}$ better than $x^{\prime}$ , that is $f(x^{(i)})\leq f(x^{\prime})$ for some $i=1,\cdots,n$ . By Lemma 2.1, $f(x^{(\bar{n}-1)})\leq f(x^{(i)})$ and the result follows by Theorem 2.3.

First, let $k\geq\bar{n}$ . Then we have

	$\displaystyle f(x^{(k)})-f(x^{\prime})$	$\displaystyle=\frac{1}{2}({\boldsymbol{1}}^{\top}x^{(k)}-{\boldsymbol{1}}^{\top}x^{\prime})({\boldsymbol{1}}^{\top}x^{(k)}+{\boldsymbol{1}}^{\top}x^{\prime})-c^{\top}(x^{(k)}-x^{\prime})$
		$\displaystyle=-\frac{1}{2}x^{\prime}_{k+1}(2U_{k}+x^{\prime}_{k+1})+c_{k+1}x^{\prime}_{k+1}$
		$\displaystyle=-x^{\prime}_{k+1}\left(\frac{1}{2}(2U_{k}+x^{\prime}_{k+1})-c_{k+1}\right).$

On the other hand, we have

2U_{k}+x^{\prime}_{k+1}=2\sum_{i=1}^{\bar{n}-1}u_{i}+\sum_{i=\bar{n}}^{k}u_{i}+x^{\prime}_{k+1}\geq U_{\bar{n}}+U_{\bar{n}-1}.

Therefor

\frac{1}{2}(2U_{k}+x^{\prime}_{k+1})-c_{k+1}\geq\frac{1}{2}(U_{\bar{n}}+U_{\bar{n}-1})-c_{\bar{n}}=G_{\bar{n}}\geq 0.

Thus $f(x^{(k)})\leq f(x^{\prime})$ .

Now, let $k<\bar{n}-2$ . Then

	$\displaystyle f(x^{(k+1)})-f(x^{\prime})$	$\displaystyle=\frac{1}{2}({\boldsymbol{1}}^{\top}x^{(k+1)}-{\boldsymbol{1}}^{\top}x^{\prime})({\boldsymbol{1}}^{\top}x^{(k+1)}+{\boldsymbol{1}}^{\top}x^{\prime})-c^{\top}(x^{(k+1)}-x^{\prime})$
		$\displaystyle=\frac{1}{2}(u_{k+1}-x^{\prime}_{k+1})(U_{k+1}+U_{k}+x^{\prime}_{k+1})-c_{k+1}(u_{k+1}-x^{\prime}_{k+1})$
		$\displaystyle=(u_{k+1}-x^{\prime}_{k+1})\left(\frac{1}{2}(2U_{k}+x^{\prime}_{k+1}+u_{k+1})-c_{k+1}\right).$

On the other hand, we have

2U_{k}+x^{\prime}_{k+1}+u_{k+1}\leq 2U_{k}+2u_{k+1}\leq 2U_{k}+2\sum_{i=k+1}^{\bar{n}-2}u_{i}+u_{\bar{n}-1}=U_{\bar{n}-2}+U_{\bar{n}-1}.

Thus

\frac{1}{2}(2U_{k}+x^{\prime}_{k+1}+u_{k+1})-c_{k+1}\leq\frac{1}{2}(U_{\bar{n}-2}+U_{\bar{n}-1})-c_{\bar{n}-1}=G_{\bar{n}-1}<0.

That is $f(x^{(k+1)})<f(x^{\prime})$ . Thus in both cases there exist a point $x^{(t)}$ , say, such that $f(x^{(t)})\leq f(x^{\prime})\leq f(x)$ . Now, by Lemma 2.1, $f(x^{(\bar{n}-1)})\leq f(x^{(t)})\leq f(x)$ and the result follows by Theorem 2.3.

Proof of (2) Consider the possible values of $k$ at the beginning of the proof of part (1). Here, we just have $k\geq\bar{n}=1$ . Now, similar argument for this case proves (2).

Proof of (3) Again consider the possible values of $k$ at the beginning of the proof of part (1). Similar argument with case $k<\bar{n}-2$ with $\bar{n}=n+1$ proves part (3).

∎

One can conclude the following result on the time needed to solve problem (4).

Theorem 2.6.

There exists an $O(n\log n)$ time algorithm for problem (4).

Proof.

Once the index $\bar{n}$ is determined the solution can be determined in $O(n)$ time. We need $O(n\log n)$ to sort vector $c$ , $O(n)$ to compute vector $G$ , and $O(\log n)$ to find index $\bar{n}$ . That is, problem (4) can be solved in $O(n\log n)$ . ∎

3 The algorithm

Our algorithm consists of two phases: bounding the optimal solution, and, computing the optimal solution to the desired precision. The bounding phase is based on the Lagrangian dual of (2) and the solution structure of the bounded version described in section 2.

3.1 Lagrangian dual

Let $\lambda$ be the Lagrange multiplier of equality constraint in (2). Then, the Lagrangian function is defined as

	$\displaystyle\phi(\lambda)$	$\displaystyle=\min\left\{\frac{1}{2}({\boldsymbol{1}}^{\top}x)^{2}-c^{\top}x+\lambda(b-a^{\top}x)\;:\;0\leq x\leq u\right\}$		(16)
		$\displaystyle=\lambda b+\min\left\{\frac{1}{2}({\boldsymbol{1}}^{\top}x)^{2}-(c+\lambda a)^{\top}x\;:\;0\leq x\leq u\right\}$		(16)

We have the following fact about the structure of the Lagrangian function $\phi$ .

Theorem 3.7.

Given Lagrange multiplier $\lambda$ , define $\bar{n}$ as in Theorem 2.5. If $\bar{n}>1$ , then we have

$\displaystyle\phi(\lambda)$	$\displaystyle=\lambda b+f_{\lambda}(x^{(\bar{n}-1)}),\text{if }c_{\bar{n}}(\lambda)\leq U_{\bar{n}-1}\leq c_{\bar{n}-1}(\lambda),$	(Type A)
$\displaystyle\phi(\lambda)$	$\displaystyle=\lambda b+p_{\bar{n}}(\lambda),\text{if }U_{\bar{n}-1}\leq c_{\bar{n}}(\lambda),$	(Type B)
$\displaystyle\phi(\lambda)$	$\displaystyle=\lambda b+p_{\bar{n}-1}(\lambda),\text{if }U_{\bar{n}-1}\geq c_{\bar{n}-1}(\lambda),$	(Type C)

where $f_{\lambda}$ is the objective function of the optimization part of (16), and,

	$\displaystyle p_{k}(\lambda)$	$\displaystyle=-\frac{1}{2}a_{k}^{2}\lambda^{2}-a^{\top}d_{k}\lambda+\frac{1}{2}c_{k}^{2}-c^{\top}d_{k},$
	$\displaystyle d_{k}$	$\displaystyle=x^{(k-1)}+(c_{k}-U_{k-1})e_{k}.$

Proof.

The proof is based on the four possible cases for $\delta_{1}$ and $\delta_{2}$ in Theorem 2.5. We just prove (Type A) and, for brevity, we omit the remaining parts.

Suppose that $c_{\bar{n}}(\lambda)\leq U_{\bar{n}-1}\leq c_{\bar{n}-1}(\lambda)$ . Then we have $c_{\bar{n}-1}(\lambda)-U_{\bar{n}-2}\geq u_{\bar{n}-1}$ and $c_{\bar{n}}(\lambda)-U_{\bar{n}-1}\leq 0$ . Therefor the value of $\delta_{1}$ and $\delta_{2}$ in Theorem 2.5 can be determined as

\delta_{1}=\min\{c_{\bar{n}-1}(\lambda)-U_{\bar{n}-2},u_{\bar{n}-1}\}=u_{\bar{n}-1},\qquad\delta_{2}=\max\{c_{\bar{n}}(\lambda)-U_{\bar{n}-1},0\}=c_{\bar{n}}(\lambda)-U_{\bar{n}-1}.

Thus we have $\bar{x}=x^{(\bar{n}-2)}+\delta_{1}e_{\bar{n}-1}=x^{(\bar{n}-1)}$ . Thus, by some simplifications we have $f_{\lambda}(\tilde{x})-f_{\lambda}(\bar{x})=\frac{1}{2}(c_{\bar{n}}(\lambda)-U_{\bar{n}-1})^{2}\geq 0$ . Now, by Theorem 2.5, we have $\min\{f_{\lambda}(x)\;:\;0\leq x\leq u\}=\min\{f(\tilde{x}),f(\bar{x}\}=f_{\lambda}(\bar{x})=f_{\lambda}(x^{(\bar{n}-1)})$ . ∎

Now, one may conclude that if $\bar{n}$ is fixed on an interval $[\lambda_{a},\lambda_{b}]$ , then $\phi(\lambda)$ is a piecewise function that contains exactly $3$ pieces. However, the following simple example shows that this is not true.

Example 3.1.

Consider problem (2) with the following parameters

		$\displaystyle a^{\top}=\begin{bmatrix}-7&-5&7&-5&7\end{bmatrix},\quad c^{\top}=\begin{bmatrix}54&44&15&-8&-70\end{bmatrix},$
		$\displaystyle u^{\top}=\begin{bmatrix}62&48&36&84&59\end{bmatrix}.$

In Figure 1 we plot $\phi(\lambda)$ for $\lambda\in[-8.36,7.00]$ . We distinct three cases in (Type A), (Type B) and (Type C) with three colors blue, red and green, respectively. As it can be seen in the figure, $\phi(\lambda)$ consists of $4$ pieces.

Refer to caption — Figure 1: Plot of $\phi(\lambda)$ for the problem of Example 3.1.

Inner optimization problem in (16) is a special case of problem (4), that can be solved by Theorem 2.5. In Theorem 2.5 it is assumed that coefficients of the linear term in the objective function is sorted in decreasing order. In problem (16), the order of coefficients of the linear term depends on $\lambda$ . From now on, we denote by $c_{i}(\lambda)$ the coefficient of $x_{i}$ , i.e. $c_{i}(\lambda)=c_{i}+\lambda a_{i}$ . Moreover, we denote the line $\{c_{i}(\lambda)\;:\;\lambda\in\mathbb{R}\}$ by $\ell_{i}$ . It is easy to see that, when $\lambda$ becomes greater than the intersection of $\ell_{i}$ and $\ell_{j}$ , $c_{i}(\lambda)$ and $c_{j}(\lambda)$ change position in the ordered list of coefficients.

We use a modification of the well-known plane sweep algorithm to find the ordered intersection points of lines $\{\ell_{i}\;:\;i=1,\cdots,n\}$ . Now, let $\lambda_{a}$ , $\lambda^{\prime}$ and $\lambda_{c}$ are three consecutive intersection points, then because of the Lagrangian function is unimodal, the optimal Lagrange multiplier $\lambda^{\ast}$ lies in the interval $[\lambda_{a},\lambda_{b}]$ if $\phi(\lambda^{\prime})>\phi(\lambda_{a})$ and $\phi(\lambda^{\prime})>\phi(\lambda_{b})$ .

We modify the implementation of the line-sweep algorithm proposed in [1]. In this algorithm, a vertical line $\ell$ sweeps the plane from left to right. The status of the sweep line is the ordered sequence of lines that intersect it. The status initially contains all lines in the order of decreasing slope, that is the order of lines when they intersect with sweep line at $\lambda=-\infty$ . The status is updated when $\ell$ reaches an intersecting point. For example, suppose that the sequence of four lines $\ell_{l}$ , $\ell_{i}$ , $\ell_{j}$ , and $\ell_{m}$ appears in the status when $\ell$ reaches the intersection point of $\ell_{i}$ and $\ell_{j}$ . Then, $\ell_{i}$ and $\ell_{j}$ switch position and the intersection of lines $\ell_{i}$ and $\ell_{m}$ and the intersection of $\ell_{j}$ and $\ell_{l}$ are to be checked. The new detected intersection points are stored to proceed. The order of cost coefficient of the linear term in $\phi(\lambda)$ is unchanged between two consecutive intersection points.

If $c_{i}(\lambda)<0$ for some $i$ , then $x_{i}=0$ in the optimal solution of the $\phi(\lambda)$ subproblem. We introduce a set $Z$ to store the non-vanished variables. To do so we add a dummy line $\ell_{0}:c_{0}(\lambda)=0$ . In each intersection of the dummy line and the other lines, the set $Z$ should be updated. In fact, if $\ell_{i}$ intersect $\ell_{0}$ and $i\not\in Z$ , then we add $i$ to $Z$ , otherwise, if $i\in Z$ , then it should be removed from $Z$ . In other words, since we sweep the plane from left to right, if $\ell_{i}$ intersect $\ell_{0}$ and $a_{i}<0$ , then we add $i$ to $Z$ . If $\ell_{i}$ intersect $\ell_{0}$ and $a_{i}>0$ then it means $i$ should be removed from $Z$ . $Z$ initially contains the set of all lines with a positive slope. With this modification, we guarantee that between two consecutive intersection points the set of zero-valued variables is unchanged. It should be noted here that lines with equal slopes are sorted based on increasing order of $c_{i}$ s. We summarize the algorithm in the following Algorithm 1. This algorithm is used as the first phase in the main algorithm.

Algorithm 1 A plane sweep algorithm for finding an interval containing the optimal solution of the Lagrangian dual problem.

1: Input: vectors

c

a

and

u

and scaler

b

2: Output: interval

[\lambda_{a},\lambda_{b}]

that contains the optimal solution of problem

\max_{\lambda\in\mathbb{R}}\phi(\lambda)

or the smallest and largest intersection points.

3: Initialize state array,

\ell=[1,\cdots,n]

, with lines

\ell[1],\cdots,\ell[n]

sorted in decreasing order of slope.

4: Initialize queue

Q=\emptyset

5: Initialize line indices array

p=[1,\cdots,n]

6: Fail

\leftarrow

true

7: Insert intersection points of all adjacent lines into

Q

8: Set

\lambda^{\operatorname{prev}}\leftarrow-\infty

\lambda^{\operatorname{prev}\operatorname{prev}}\leftarrow-\infty

9: while

Q

is not empty do

10: Pop from

Q

the current intersection point

\lambda^{\operatorname{new}}

and the corresponding two adjacent lines

\ell[i]

and

\ell[j]

11: Update state array:

\ell[p[i]]\leftrightarrow\ell[p[j]]

12: Update the line indices array:

p[i]\leftrightarrow p[j]

13: Insert the intersection point of

\ell[p[i]]

and

\ell[p[i]+1]

and the intersection point of

\ell[p[j]]

and

\ell[p[j]-1]

into

Q

, if there exists any.

14: if

\phi(\lambda^{\operatorname{prev}})>\phi(\lambda^{\operatorname{prev}\operatorname{prev}})

and

\phi(\lambda^{\operatorname{prev}})>\phi(\lambda^{\operatorname{new}})

then

15: Set Fail

\leftarrow

false

16: return

[\lambda^{\operatorname{prev}\operatorname{prev}},\lambda^{\operatorname{new}}]

as the promissing interval.

17: end if

18: Set

\lambda^{\operatorname{prev}\operatorname{prev}}\leftarrow\lambda^{\operatorname{prev}}

19: Set

\lambda^{\operatorname{prev}}\leftarrow\lambda^{\operatorname{new}}

20: end while

21: if Fail then

22: return the smallest

\lambda_{LB}

and the largest

\lambda_{UB}

interseation points.

23: end if

Theorem 3.8.

Algorithm 1 runs in $O(n^{2}\log n)$ time.

Proof.

Initializing state array $\ell$ , line indices array $p$ and the queue $Q$ in steps 3–7 needs $O(n\log n)$ time. In each iteration we perform two main operations: computing the value of $\phi$ for a new intersect point $\lambda^{\operatorname{new}}$ and updating $Q$ . The order of $c_{i}(\lambda^{\operatorname{new}})$ and the vector $G$ can be updated from the previous intersection point in $O(1)$ time. Finding $\bar{n}$ needs $O(\log n)$ , using binary search. On the other hand, insertion and deletion on the priority queue $Q$ takes $O(\log n)$ since one can implement the priority queue by a heap to store the intersection points. Therefore each iteration of the main loop needs $O(\log n)$ time. Since there are $O(n^{2})$ intersection points, the algorithm runs in $O(n^{2}\log n)$ . ∎

Let $\lambda_{LB}$ and $\lambda_{UB}$ be the smallest and greatest intersection points of lines $\{\ell_{i}\;:\;i=1,\cdots,n\}$ . The optimal solution of the Lagrangian problem may lie out of the interval $[\lambda_{LB},\lambda_{UB}]$ . In this case, Algorithm 1 fails to find the optimal interval. So, we explore the outside of $[\lambda_{LB},\lambda_{UB}]$ in a separate phase.

First consider the exploration of $(-\infty,\lambda_{LB})$ . Since the components of vector $G$ in Theorem 2.5 are linear functions in term of $\lambda$ , then there exists $\lambda^{\prime}_{LB}<\lambda_{LB}$ such that the order of $G_{k}$ s does not change for $\lambda<\lambda^{\prime}_{LB}$ . Indeed, a similar procedure for finding the smallest intersection of lines $\ell_{i}$ ’s can be used here to compute $\lambda^{\prime}_{LB}$ . Now, since $\phi(\lambda)$ is unimodal one can conclude that

\max_{(-\infty,\lambda_{LB}]}\phi(\lambda)=\max_{[\lambda^{\prime}_{LB},\lambda_{LB}]}\phi(\lambda).

(17)

Similarly, for the values of $\lambda$ greater than $\lambda_{UB}$ , one can find a threshold, say $\lambda^{\prime}_{UB}$ , such that

\max_{[\lambda_{UB},\infty)}\phi(\lambda)=\max_{[\lambda_{UB},\lambda^{\prime}_{UB}]}\phi(\lambda).

(18)

We summarize the whole algorithm in Algorithm 2.

Algorithm 2 A two-phase algorithm for solving rank-one quadratic knapsack problem (2).

1: Run Algorithm 1 to find a promising interval that contains the optimal Lagrange multiplier.

2: if Algorithm 1 returns an interval

[\lambda_{a},\lambda_{b}]

then

3: Solve optimization problem

\max_{[\lambda_{a},\lambda_{b}]}\phi(\lambda)

and return the optimal solution.

4: else

5: Solve optimization problems (17) and (18) and store the optimal values.

6: end if

7: return the best

\lambda

found as an optimal Lagrange multiplier.

It is clear that Algorithm 2 converges to the optimal solution, since the output interval of Algorithm 1 contains the optimal solution and $\phi(\lambda)$ is unimodal. In fact, the single variable optimization problem in step 3 can be solved efficiently by a classical root-finding algorithms.

4 Computational Experiments

In this section, we compare the running time and the numerical accuracy of Algorithm 2 with the general convex quadratic programming solver, CPLEX. We implement Algorithm 2 with MATLAB R2019b. All runs are performed on a system with Core i7 $2.00$ GHz CPU and $8.00$ GB of RAM equipped with a $64$ bit Windows operating system. We solve single variables optimization problems (18), (17) and step 3 in Algorithm 2, using MATLAB built-in function fminbnd which is based on golden section search and parabolic interpolation.

Our testbed contains two types of randomly generated rank-one knapsack problems up to $n=50,000$ variables. In the first type, vectors $a$ and $c$ are integral and generated uniformly from the same interval. We denote this type by TypeI. In the second type (TypeII), vectors $a$ and $c$ are positive and negative randomly generated integral vectors, respectively. In Table 1 we summarize the parameter values for problem instances.

Table 1: Parameters for two types of problem instances.

Type	$a$	$c$	$l$	$u-l$ \MLTypeI	$U(-50,50)$	$U(-50,50)$	$U(0,20)$	$U(1,100)$
TypeII	$U(-100,10)$	$U(10,100)$	$U(0,20)$	$U(1,100)$ \LL

As a well-known general convex quadratic programming solver, we chose CPLEX (ver. 12.9) to compare with our results. Based on our numerical tests, we set the quadratic programming solver of CPLEX (qpmethod option) to barrier. The barrier convergence tolerance, convergetol is set to $1e-12$ . After we complete our experimental tests, we found in [10] that the sparsity of the Hessian matrix influences the performance of CPLEX. To increase the performance, we reformulate our problem as

\min\left\{\frac{1}{2}y^{2}-c^{\top}x\;:\;{\boldsymbol{1}}^{\top}x-y=0,\;a^{\top}x=b,\;0\leq x\leq u\right\}.

We denote the results corresponding to running CPLEX on the original problem and the above modification respectively by $\text{CPLEX}_{org}$ and $\text{CPLEX}_{ref}$ .

Table 2 shows the average running time for $5$ runs of each algorithm/solver for each problem size. Dash sign, ’-’, denoted the algorithm/solver encounters out-of-memory status.

In all cases, Algorithm 2 outperforms $\text{CPLEX}_{org}$ . For instances up to $n=5000$ , our algorithm and $\text{CPLEX}_{ref}$ has same performance, whereas for larger instances, $\text{CPLEX}_{ref}$ has smaller running time.

Table 2: A comparison of running times (in seconds) between our algorithm and

\text{CPLEX}_{org}

and

\text{CPLEX}_{ref}

$n$		Our algorithm	$\text{CPLEX}_{org}$	$\text{CPLEX}_{ref}$ \ML $1000$	TypeI	$0.06$	$0.09$	$0.01$
	TypeII	$0.01$	$0.06$	$0.02$
$1500$	TypeI	$0.04$	$0.15$	$0.02$
	TypeII	$0.02$	$0.13$	$0.02$
$2000$	TypeI	$0.04$	$0.27$	$0.02$
	TypeII	$0.02$	$0.27$	$0.02$
$5000$	TypeI	$0.09$	$2.21$	$0.02$
	TypeII	$0.06$	$2.12$	$0.03$
$10000$	TypeI	$0.26$	$16.26$	$0.04$
	TypeII	$0.23$	$16.95$	$0.05$
$15000$	TypeI	$0.62$	$61.20$	$0.10$
	TypeII	$0.63$	$65.88$	$0.10$
$20000$	TypeI	$1.16$	-	$1.20$
	TypeII	$0.88$	-	$1.02$
$50000$	TypeI	$3.22$	-	$0.11$
	TypeII	$3.19$	-	$0.11$
$100000$	TypeI	$12.19$	-	$0.14$
	TypeII	$11.31$	-	$0.17$ \ML

5 Conclusions

In this paper, we proposed a two-phase algorithm for rank-one quadratic knapsack problems. To this end, we studied the solution structure of the problem when it has no resource constraint. Indeed, we proposed an $O(n\log n)$ algorithm to solve this problem. We then used the solution structure to propose an $O(n^{2}\log n)$ line-sweep algorithm that finds an interval that contains the optimal Lagrange multiplier. Then, the estimated optimal interval is explored for computing the optimal solution with the desired accuracy. Our computational tests showed that our algorithm has better performance than CPLEX when CPLEX is used to solve the original problem. After a reformulation of the problem, CPLEX outperforms our algorithm for instances with $n\geq 5000$ .

References

[1] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational geometry: Algorithms and Applications, Springer-Verlag TELOS, 2008.
[2] Gabriel R Bitran and Arnoldo C Hax, Disaggregation and resource allocation using convex knapsack problems with bounded variables, Management Science 27 (1981), no. 4, 431–441.
[3] Peter Brucker, An $O(n)$ algorithm for quadratic knapsack problems, Operations Research Letters 3 (1984), no. 3, 163–166.
[4] Roberto Cominetti, Walter F Mascarenhas, and Paulo JS Silva, A Newton’s method for the continuous quadratic knapsack problem, Mathematical Programming Computation 6 (2014), no. 2, 151–169.
[5] Yu-Hong Dai and Roger Fletcher, New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds, Mathematical Programming 106 (2006), no. 3, 403–421.
[6] Daniela di Serafino, Gerardo Toraldo, Marco Viola, and Jesse Barlow, A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables, SIAM Journal on Optimization 28 (2018), no. 4, 2809–2838.
[7] Jean-Pierre Dussault, Jacques A Ferland, and Bernard Lemaire, Convex quadratic programming with one constraint and bounded variables, Mathematical Programming 36 (1986), no. 1, 90–104.
[8] Roger Fletcher, Augmented lagrangians, box constrained QP and extensions, IMA Journal of Numerical Analysis 37 (2017), no. 4, 1635–1656.
[9] R Helgason, J Kennington, and H Lall, A polynomially bounded algorithm for a singly constrained quadratic program, Mathematical Programming 18 (1980), no. 1, 338–343.
[10] IBM, Cplex performance tuning for quadratic programs, https://www.ibm.com/support/pages/node/397129?mhsrc=ibmsearch_a&mhq=CPLEXPerformanceTuningforQuadraticPrograms, June 2018, [Online; accessed 23-January-2022].
[11] Meijiao Liu and Yong-Jin Liu, Fast algorithm for singly linearly constrained quadratic programs with box-like constraints, Computational Optimization and Applications 66 (2017), no. 2, 309–326.
[12] Panos M Pardalos, Yinyu Ye, and Chi-Geun Han, Algorithms for the solution of quadratic knapsack problems, Linear Algebra and its Applications 152 (1991), 69–91.
[13] Michael Patriksson, A survey on the continuous nonlinear resource allocation problem, European Journal of Operational Research 185 (2008), no. 1, 1–46.
[14] Michael Patriksson and Christoffer Strömberg, Algorithms for the continuous nonlinear resource allocation problem—new implementations and numerical studies, European Journal of Operational Research 243 (2015), no. 3, 703–722.
[15] AG Robinson, N Jiang, and CS Lerme, On the continuous quadratic knapsack problem, Mathematical programming 55 (1992), no. 1-3, 99–108.
[16] Thomas C Sharkey, H Edwin Romeijn, and Joseph Geunes, A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems, Mathematical Programming 126 (2011), no. 1, 69–96.