Are binary quadratic and linear programs equivalent with the same constraints?

137 Views Asked by At

If we consider the following two problems (1) and (2), are they equivalent? Because the values in $\bf x$ can only be either one or zero, the value of the objective function at the optimum $\bf x^*$ does not seem to change. Plus, since both problems are subjected to the same constraints, can I say that solving (1) also solves (2) or viceversa?

(1) $$\max {\bf x}^T {\bf c}$$ subject to $${\bf Ax} = {\bf b},$$ $${\bf x} = \{0, 1\}^M$$

(2) $$\max {\bf x}^T {\bf \mit diag\{\bf c\} \bf x}$$ subject to $${\bf Ax} = {\bf b},$$ $${\bf x} = \{0, 1\}^M$$

I would much apprecaite some comments and/or references.

2

There are 2 best solutions below

2
On

Yes, of course they are exactly the same problem.

2
On

Yes.

$$x^Tdiag\{c\}x=\sum_{i=1}^M c_ix_i^2=\sum_{i=1}^M c_ix_i=x^Tc$$