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.

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.