# Linear System with constrained solutions

After a model my problem I found a rectangular linear system : $$Ax=b$$ I can easely solve it with a least square with QR/SVD... But the model include constrains for each solution $x_i$, the $\vec{x}$ have n elements. ($1\leqslant i\leqslant n$)

For each $x_i$ I have a min and max: $$x_i \geqslant min_i$$ $$x_i \leqslant max_i$$ And exist some couple constraint with $(i,j)$ as: $$(i,j) \in \left (\frac{\mathbb{Z}}{n\mathbb{Z}} \right )^2 | i \neq j$$ $i$ and $j$ is on $\mathbb{Z}$ and is included on $[1,n]$

I have 2 others kinds of constraints $L^p_{ij}$ and $E^q_{ij}$ on "99.9%" of my cases : $$L^p_{ij} = L^p_{ji}$$ $$E^q_{ij} = E^q_{ji}$$ I have N ($1 \leqslant p \leqslant N$) contrains L and K ($1 \leqslant q \leqslant K$) constains E.

$$L^p_{ij} : x_i + x_j = 1 \space \mathbf{or} \space 0$$ $$E^p_{ij} : x_i > 0 \Rightarrow x_j = 0$$ I can rewrite $E^q_{ij}$ like : $$\begin{matrix} x_i+x_j=\max(x_i,x_j) \Rightarrow \\ x_i + x_j = \frac{1}{2}\left(x_i + x_j + \left | x_i - x_j \right |\right) \Rightarrow \\ x_i + x_j = \frac{1}{2}\left (x_i + x_j + \sqrt{ (x_i - x_j)^2 }\right ) \end{matrix}$$

I search a way to minimize $\|Ax=b\|$ with my $min_i$, $max_i$, $L^p_{ij}$, $E^q_{ij}$. All $x_i$ have one $min_i$ and $max_i$, but for $L^p_{ij}$ and $E^q_{ij}$ I have no control on number or "topology" constrains.

As you see I have an $\mathbf{or}$ on $L^p_{ij}$ and the derivation of $E^q_{ij}$ is not continue so I can't simply use the Lagrange Multiplier.

Any comment or solutions are welcome.

Thanks

$Ax = b$ with bounds on $x$ is dealt with in linear programming. Your $L$ and $E$ constraints will take you into mixed integer linear programming.
• I'm not a specialist of "Mixed Integer Linear Programming" but this method was not developped to constrain the solution as Interger ? In $\mathbb{Z}$. I forget to specify something, in major part of my cases $min_i = 0$ and $max_i = 1$ So my $x_i$ is not integer. Thanks – chkone Sep 3 '13 at 14:18
• Your $x_i$ are not integer, but you'd have additional variables that are integer. That's why it's "mixed". For example, $L^p_{ij}$ would be handled with an additional binary variable $u_{ij}$ (i.e. its allowed values are $0$ and $1$), with constraint $x_i + x_j = u_{ij}$. For $E^p_{ij}$ you'd have binary variables $u_i$ and $u_j$, with constraints $max_i u_i \ge x_i$, $max_j u_j \ge x_j$, $u_i + u_j \le 1$. – Robert Israel Sep 3 '13 at 15:12
• I have no link for $L^p_{ij}$ and $E^q_{ij}$. For that I'm not sur to understand the second part for $E^p_{ij}$ : $$max_i u_i \geqslant x_i ?$$ $$max_j u_j \geqslant x_j ?$$ $$u_i+u_j\leqslant 1$$ $max_i u_i$ it is a multiplication ? Thanks – chkone Sep 3 '13 at 15:44
• Yes, it's multiplication. The point is that $\max_i u_i \ge x_i$ means that when $x_i > 0$, $u_i$ can't be $0$ (so it must be $1$), while $u_i = 1$ is always allowed. $u_i + u_j \le 1$ means you can't have both $u_i = 1$ and $u_j = 1$. – Robert Israel Sep 4 '13 at 4:04