# Matrix equation & integer programming

I have a series of matrix equations that look like:

$$x^TA_ky=b_k$$

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

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

Besides,

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

• Note that this can be linearized and solved with a linear MIP solver. Hopefully there is a feasible solution. – Erwin Kalvelagen Dec 20 '18 at 11:02
• Hi @ErwinKalvelagen Could you be more specific by saying "linearized"? Thanks! – 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}

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

• Thanks! Just curious, what package is this? – James Dec 20 '18 at 18:39
• I used GAMS+Cplex. But any MIP solver will do (although better ones have better performance). – Erwin Kalvelagen Dec 20 '18 at 18:44
• 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... – 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).

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