I have a series of matrix equations that look like:


with $k = 1, 2, .. n$

and $A_k, b_k$ known double precision matrices, $x$ and $y$ unknown.


$$x, y$$

are vectors with each component -1 or 1.

(i) Is there any good method to solve x and y directly?

(ii) If not, what if we relax the integer constraints, and then "round" the x and y to -1 and 1? would it be bad because of the rounding?

(iii) If this is still difficult, I think it may be a good idea to try something like:

$$min\sum_{k=1}^n |x^TA_ky-b_k|^2 + \lambda||x||_2^2 + \mu ||y||_2^2$$ so that the magnitude of x and y are not too "wild".

Can anyone give some suggestions for these kinds of problems? Thanks!

  • 1
    $\begingroup$ Note that this can be linearized and solved with a linear MIP solver. Hopefully there is a feasible solution. $\endgroup$ – Erwin Kalvelagen Dec 20 '18 at 11:02
  • $\begingroup$ Hi @ErwinKalvelagen Could you be more specific by saying "linearized"? Thanks! $\endgroup$ – James Dec 20 '18 at 17:18

Here is how we can develop a MIP model. We prefer to use binary variable, so let's introduce:

$$p_i, q_i \in \{0,1\}$$

We can interpret:

$$\begin{align} & x_i = 2p_i -1\\ & y_i = 2q_i-1\end{align}$$

I.e. we can map this to $x_i, y_i \in \{-1,+1\}$. We can then write:

$$ \sum_{i,j} x_i y_j a_{i,j}^k = \sum_{i,j} \left(1-2 (p_i \text{ xor } q_i)\right) a_{i,j}^k = b^k $$

This is a bit complicated. It says if $p_i=q_j$ (or equivalently if $x_i=y_j$) then the value of $(1-2 (p_i \text{ xor } q_i))$ becomes $+1$ else it will be $-1$.

This can be linearized as: $$\begin{align} & w_{i,j} \le p_i + q_j \\ & w_{i,j} \ge p_i - q_j \\ & w_{i,j} \ge q_j - p_i \\ & w_{i,j} \le 2 - p_i - q_j \\ & \sum_{i,j} \left(1-2 w_{i,j} \right) a_{i,j}^k = b^k \\ & p_i, q_j, w_{i,j} \in \{0,1\} \end{align}$$

Add a dummy objective and you have your MIP model.

PS. Not many MIP models have an XOR operation. This is interesting. See link for more info about the linearization.

PS2. A small example showing this works:

----     62 PARAMETER a  

            i1          i2          i3          i4          i5

i1       0.998       0.579       0.991       0.762       0.131
i2       0.640       0.160       0.250       0.669       0.435
i3       0.360       0.351       0.131       0.150       0.589
i4       0.831       0.231       0.666       0.776       0.304
i5       0.110       0.502       0.160       0.872       0.265

----     62 PARAMETER b                    =        2.222  

----     62 VARIABLE p.L  

i1 1.000,    i4 1.000,    i5 1.000

----     62 VARIABLE q.L  

i1 1.000,    i2 1.000,    i4 1.000

----     62 VARIABLE w.L  

            i1          i2          i3          i4          i5

i1                               1.000                   1.000
i2       1.000       1.000                   1.000
i3       1.000       1.000                   1.000
i4                               1.000                   1.000
i5                               1.000                   1.000

----     62 VARIABLE x.L  

i1  1.000,    i2 -1.000,    i3 -1.000,    i4  1.000,    i5  1.000

----     62 VARIABLE y.L  

i1  1.000,    i2  1.000,    i3 -1.000,    i4  1.000,    i5 -1.000
  • $\begingroup$ Thanks! Just curious, what package is this? $\endgroup$ – James Dec 20 '18 at 18:39
  • $\begingroup$ I used GAMS+Cplex. But any MIP solver will do (although better ones have better performance). $\endgroup$ – Erwin Kalvelagen Dec 20 '18 at 18:44
  • $\begingroup$ Thanks for the awesome answer and editing! Now I'm implementing the math in cvxopt though the manual for this package is a bit simplified... $\endgroup$ – James Dec 20 '18 at 22:04

As Erwin said in a comment, this can be linearized and solved as an integer linear program. If $A_k$ and $b_k$ are integer-valued, I think it could also be solved as a constraint programming problem. (That might also be true even if they are not integer-valued, but I'm not positive.) If the dimension is not too large, it might be just as easy to solve by partial enumeration.

Regarding your list of items: (i) not that I know of; (ii) I doubt this would work (meaning the rounded solution would likely be infeasible); and (iii) I don't see how this makes sense -- if the domains for $x_i$ and $y_i$ are $\{-1,1\}$, then their euclidean norms are constant (equal to their dimension).

  • $\begingroup$ Can you be more specific by saying "this can be linearized"? I'm new to integer programming. Thanks! $\endgroup$ – James Dec 20 '18 at 17:12
  • $\begingroup$ Erwin's answer shows the linearization. $\endgroup$ – prubin Dec 21 '18 at 19:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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