2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Commented May 9, 2023 at 8:37
  • $\begingroup$ Your matrices and vectors should be over $\Bbb Q$ $\endgroup$ Commented May 9, 2023 at 10:26
  • 1
    $\begingroup$ @RodrigodeAzevedo: this horrible notation hides the fact that the cost function is a variance. $\endgroup$
    – user16034
    Commented May 9, 2023 at 11:57

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – OvinaSun
    Commented May 9, 2023 at 12:14
  • $\begingroup$ 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. $\endgroup$
    – OvinaSun
    Commented May 9, 2023 at 12:14
  • $\begingroup$ 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. $\endgroup$
    – OvinaSun
    Commented May 9, 2023 at 12:15
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Commented May 9, 2023 at 12:50
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Commented May 9, 2023 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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