6

Say I have two sets of variables $x$ and $y$ of equal size. $x$'s have a lower bound $x_{min}<0$, and $y$'s have a lower bound $0$.

Is there a linear way to constrain that $x_i\geq0$ if the solution has $y_i>0$, and $x_i\geq x_{min,i}$ if the solution has $y_i=0$.

A few other points that might be useful

  • $x$ and $y$ are of length ~100
  • $x$ and $y$ both should be integers, but their values are large enough to be treated as continuous, and rounding the solution doesn't hurt too much.
  • The objective function is, for a given scalar $t$ and vector $y_0$ $$min\,|\Sigma(x+y)-t| + \Sigma|y-y_0|$$
jf328
  • 482
  • 2
  • 8
  • 2
    How large is the problem in terms for the number of $x_i$? – Richard Dec 07 '23 at 16:19
  • 1
    And can you share your objective function? – Richard Dec 07 '23 at 16:53
  • @Richard, please see edits, thx – jf328 Dec 08 '23 at 01:41
  • 1
    Ah, well, the fact that $x$ and $y$ can be treated like integers makes this much, much easier, because suddenly instead of $y > 0$ you can write $y \geq 1$, which is much more helpful. Similarly for $x$ if you are okay to replace $x_i \geq 0$ with $x_i > -1$ it suddenly becomes much easier to come up with a big-M constraint. – Stef Dec 08 '23 at 10:14
  • Do you know if there is a value $M$ such that you can add constraint $-M \leq x_i \leq M$ and $-M \leq y_i \leq M$ for all i without changing the problem? – Stef Dec 08 '23 at 10:16
  • @Stef, thanks, good thinking. At the post-LP rounding step, I could simply round to 0 for any $|x| < 1$. It won't be optimal, but no big deal for general $|x|$ in the range of 500 to 10000. Do you mind posting as an answer so I can accept? – jf328 Dec 11 '23 at 02:54

2 Answers2

7

I don't think it is possible in general.

If we introduce variables $t_i$, we can write the problem as:

$\max ...$

s.t.

$x_i \ge t_i$

$ y_i \ge 0 $

$ x_{min} \le t_i \le 0 $

$ y_it_i = 0 $ (this encodes that $y_i = 0$ or $t_i = 0$)

The last constraint is nonlinear, so this is not a solution to the problem. We have only succeeded in transferring the problem to forcing one of two variables to be zero. Some quick google searches did not lead to me to anything useful and this situation is much more common so I don't think a general solution is possible.

I have encountered it (requiring one of two variables to be zero) before in some applications and there we could rewrite the problem in such a way that we did not need to constrain it directly, but we could prove that an optimal solution would need to satisfy that constraint. It may be possible in your application as well.

Thijs Steel
  • 1,693
  • 8
  • 16
3

When we "Plot" the region covered by a Pair of $(x,y)$ variables , we can see that it is Non-Convex , hence Linear Programming can not work out.

NON-CONVEX

With that Point , we have couple of alternatives to try :

(Alternative 1) If we have only 1 such Pair (& all other variables are linear) then we can make 2 LP formulations LP1 where $y=0$ (Blue line) & LP2 where $y>0$ (Purple area) & get the 2 Solutions & then choose the better of those 2.
This will work even if we have 2 such Pairs but beyond that , it will be to cumbersome & tedious.

(Alternative 2) We can have Binary variable (Mixed Integer Programming) eg $b=0$ to choose the Purple area & $b=1$ to choose the Blue line.
[[ It is similar to Alternative 1 , though the algorithm itself is choosing the better Solution automatically ]]
We can , of course , have 1 Binary variable for each such $(x,y)$ Pair , hence this will work for general case too.

Prem
  • 141
  • 1
  • 1
  • 4
  • It's probably worth highlighting that once you move into any sort of integer constraints, that's a very different world from continuous linear programming. – Josiah Dec 08 '23 at 12:02
  • Not sure about this, but in your plot, could one extend the region by drawing a line from (xmin,0) to (0,ymax) and including the resulting triangle in the feasible set? That would make it convex and the optimal solution of a linear programming problem is (i think) always on a corner so the final solution would still satisfy the constraints. – Thijs Steel Dec 08 '23 at 13:46
  • 2
    In general , extending the area might not work , @ThijsSteel , because some other criteria might have made a new corner in the unwanted area & the algorithm might give the Solution with that corner. – Prem Dec 08 '23 at 14:17
  • Point about Integer Programming is Correct , @Josiah , though I think Binary Case is somewhat easier & suitable algorithms can get the Solution reasonably well : It will have to check $2^n$ Cases rather than $m^n$ Cases. When $n$ is small , that alternative should work out well. – Prem Dec 08 '23 at 14:24