5
$\begingroup$

The quadratic knapsack problem (QKP) $$\max_x x^TPx$$ $$\mathrm{s.t.}\;\;w^Tx\leq c,\; x\in\{0,1\}$$ where $P\geq0, w\geq0$ elementwise, is well studied and has existing solvers.

My problem below seems closely related to QKP, but I can't find a way to transform it to a QKP to use existing solvers. $$\min_x x^TPx$$ $$\mathrm{s.t.}\;\;w^Tx\geq c,\; x\in\{0,1\}$$ where $P\geq0, w\geq0$.

It's easy to translate the constraints by using $y=1-x$, but how can I deal with the objective?

FWIW, in my problem $w=$ all ones vector, and it's exactly the same as in Knapsack problem with fixed number of elements? but I would like to have global solution rather than approximate solution.

$\endgroup$
3
$\begingroup$

Applying the transformation you suggested, we get:

$$\min_{y \in\{0,1\}^n} (\mathbf{1}-y)^TP(\mathbf{1}-y)$$ $$\mathrm{s.t.}\;\;w^T(\mathbf{1}-y)\geq c\, ,$$ where $n$ is the dimension where $x$ lives and $\mathbf{1}$ is a vector of $n$ ones.

Working with the objective function, $$ \begin{align*} (\mathbf{1}-y)^T P(\mathbf{1}-y) & = \mathbf{1}^T P\mathbf{1} - y^T P\mathbf{1} - \mathbf{1}^T P y + y^T Py \\ & = \mathbf{1}^T P\mathbf{1} - (P\mathbf{1})^T y - \mathbf{1}^T P y + y^T Py \\ & = \mathbf{1}^T P\mathbf{1} - ( \mathbf{1}^T P^T - \mathbf{1}^T P ) y + y^T Py \, , \end{align*} $$ while for the linear constraint, $$ w^T \cdot \mathbf{1} - w^T y \geq c \Leftrightarrow w^Ty \leq w^T \cdot \mathbf{1} - c \,. $$

Therefore, the optimization problem is equivalent to:

$$\max_{y \in\{0,1\}^n} y^T Qy + b^T y $$ $$\mathrm{s.t.}\;\;w^Ty \leq w^T \cdot \mathbf{1} - c \, ,$$ where $Q = -P\, $, $b^T = \mathbf{1}^T P^T + \mathbf{1}^T P $ and we changed sign in the objective function to get a maximization problem. Note the $\mathbf{1}^T P\mathbf{1}$ term can be omitted as it's constant. This is indeed a quadratic knapsack problem. In this case $w = \mathbf{1}$, so the knapsack constraint yields $w^Ty \leq n - c$ thus if $c \leq n$ the problem is feasible.

Some alternatives to get an exact solution (apart from brute force, which could be enough for $n$ not too big and $(n - c)$ relatively small):

  • Linearization, i.e. reformulating the model as a mixed linear program. This will result in a mixed integer program (MIP) that can be approached using MIP techniques, e.g. branch-and-bound or branch-and-cut. There are two common approaches here, you can read more about them in the dedicated literature:

    1. the standard linearization technique, where a continuous variable $z_{ij}$ is introduced to replace the $y_i y_j$ term. See for example Section 1 of [1].
    2. Fred Glover's linearization, which yields a model with significantly less variables and constraints than using standard linearization. cf. section 2.3 of [2].
  • If $Q$ is positive semi-definite1, then the operator $yQy + b^Ty$ is convex and the problem can be solved using a quadratic integer programming solver (MIQP solver, e.g. CPLEX or Gurobi).

  • There's also a custom-made technique using branch-and-bound and Lagrangian relaxation, called Quadknap. It was proposed by Caprara, Pisinger and Toth in [1] and you can read about it here. C code is available at this site.

A couple of benchmarks are available for the different methods, for example [2] which is available here.


Remark: For some of the methods you'll need to have the objective function in the form $x^TQx$, instead of $x^TQx + b^Tx$. As $x$ is binary, $x_i = x_i^2$ and therefore you can bring the linear coefficients to the matrix's diagonal.

[1] Caprara, Alberto, David Pisinger, and Paolo Toth. "Exact solution of the quadratic knapsack problem." INFORMS Journal on Computing 11.2 (1999): 125-137.

[2] Wang, Haibo, Gary Kochenberger, and Fred Glover. "A computational study on the quadratic knapsack problem with multiple constraints." Computers & Operations Research 39.1 (2012): 3-11.

1 As $P \geq 0$, it's likely $Q$ won't be semidefinite positive in this case. Nonetheless, I decided to mention this method anyway for a more complete answer.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.