# Is the following binary quadratic integer programming NP-Hard？

I'am trying to prove the following binary quadratic integer programming problem NP hard.

$$\min \frac{\sum\limits_{i=1}^m(u_i-\bar u)^2}{m}\text{ , where }u=Q x,Q\in\mathbb{R}^{m\times n}\\ s.t. \begin{cases} Ax\leq b, \ A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m \\Cx=d, \ C\in \mathbb{R}^{m\times n},d\in\mathbb{R}^m\\ \forall i: x_{i}\in\{0,1\}\end{cases}$$

• x is a n-dimensional programming variable.

• u is a m-dimensional vector, and $$\bar u = \frac{\sum\limits_{i=1}^mu_i}{m}$$.

• A, C, Q are constant coefficient matrices.

• b, d are constant coefficient vectors.

I guess it could be reduced into the knapsack problem. But because of the complexity of the target function, I haven't figured out how to relate it to the knapsack problem.

• Sums are ugly. Just write $$\frac1m \| {\bf u} - {\bar u} {\bf 1}_m \|_2^2 = \frac1m \left\| \left( {\bf I}_m -\frac1m {\bf 1}_m {\bf 1}_m^\top \right) {\bf u} \right\|_2^2$$ and note that ${\bf I}_m -\frac1m {\bf 1}_m {\bf 1}_m^\top$ is a projection matrix Commented May 9, 2023 at 8:37
• Your matrices and vectors should be over $\Bbb Q$ Commented May 9, 2023 at 10:26
• @RodrigodeAzevedo: this horrible notation hides the fact that the cost function is a variance.
– user16034
Commented May 9, 2023 at 11:57

This problem is NP-hard. Well, to be precise, currently, it is not specified what happens when there is no $$x$$ that satisfies all constraints. Determining whether a valid solution for $$x$$ exists is NP-hard, as the integer linear program feasiblity is a special case of this problem. But I think you're more interested in the optimization part.

So, suppose $$A,B,c,d$$ are chosen such that there always is a solution for $$x$$ that satisfies the constraints. Then the problem is still NP-hard. Let $$\mathsf{IS'}$$ be the problem of finding a maximum independent set in graphs where there exists an independent set of size at least half the number of nodes. For every graph $$G$$ with $$n$$ vertices, we can create a graph $$G'$$ that is a valid input for $$\mathsf{IS'}$$ by adding $$n$$ isolated vertices to $$G$$. With this observation, it is easy to show $$\mathsf{IS'}$$ is NP-hard via a reduction from the ordinary independent set problem.

We can now encode $$\mathsf{IS'}$$ as an instance of this optimization program, which shows the problem is NP-hard. For simplicity, I'm assuming $$A$$ may have more rows than $$Q$$. We can obtain these extra rows by padding $$x$$ with extra values of which we can fix the sum using $$C$$.

Given a graph $$G$$ of $$n$$ vertices, let $$x$$ be a vector where the indices $$i$$ correspond to vertices $$v_i$$ in $$G$$.

For each edge $$(v_i,v_j)$$ in $$G$$, add the constraint $$x_i+x_j\leq 1$$. Also, add the constraint $$\sum_{i=1}^n x_i \geq n/2$$. Let $$Q$$ be the identity matrix, $$C$$ and $$d$$ can be set to $$0$$. Note that the construction of $$\mathsf{IS}'$$ guarantees there exists an $$x$$ that satisfies these constraints.

Due to the edge constraint, the set of vertices $$v_i$$ where $$x_i=1$$ is an independent set in $$G$$. Due to the second constraint, at least half of the entries of $$x$$ are set to $$1$$. The objective function calculates the variance of $$Qx= x$$, which is strictly decreasing in the number of $$1$$-entries under the condition that at least half of the entries are $$1$$. So, a minimum objective function for $$x$$ corresponds to maximum independent set in $$G$$.

• I kind of get a rough understanding of your proof. Since I have not studied the computational complexity theory, I have the following problems about your proof: - I don't understand how constraint $x_i+x_j\leq 1$ affects the corresponding edge $<v_i,v_j>$ in graph G. Does it mean that there is at most one edge between two vertices? Commented May 9, 2023 at 12:14
• 2. Based on your proof, may I take your statement to mean that you constructed a special instance of my programming problem (I see that you set special conditions for A, C, Q, d) and then connected this special case to an NP-hard problem: reducing this instance to the MIS problem. I wonder if the conclusion is still tenable for A, C, Q and d in other cases. I mean I want to know how to compare the hadness between the instance and the original problem. Commented May 9, 2023 at 12:14
• 3. Finally, I have seen some notes (en.wikipedia.org/wiki/Reduction, below the example header) showing that proving problem P is NP-hard requires reducing an NP-hard problem (let's call it problem Q) to problem P, which illustrate the difficulty of solving P is greater than or equal to the NP-hard problem Q. Thus proving that the problem P is NP-hard. From your proof process, I seem to see that the problem instance is reduced to MIS problem. I am a little confused. Commented May 9, 2023 at 12:15
• 1. The entries of $x$ with value 1 correspond to the vertices in a potentially independent set. So, $x_i+x_j\leq 1$ means we can select at most one of $v_i,v_j$ for the set. We need to have this constraint for every edge to ensure no pair of vertices in the independent set have an edge in $G$. 2. If $A'$ is a more specific problem of $A$, then showing $A'$ is NP-hard implies $A$ is NP-hard. This is also how reductions generally work: the map in a reduction from problem $A$ to $B$ is usually not surjective. Commented May 9, 2023 at 12:50
• 3. I'm not sure what you're referring to, the page you link has no example header. Indeed, we need to reduce Q to P. In the proof, I first claim we can reduce IS' from IS (i.e. IS reduces to IS') and then reduce IS' to the problem in question. Commented May 9, 2023 at 13:06