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.



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

  • $\begingroup$ 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 $\endgroup$ – chkone Sep 3 '13 at 14:18
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Sep 3 '13 at 15:12
  • $\begingroup$ 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 $\endgroup$ – chkone Sep 3 '13 at 15:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Sep 4 '13 at 4:04
  • $\begingroup$ I see ! Thanks you. I will find a C++ implementation for a MIP solver. $\endgroup$ – chkone Sep 6 '13 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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