6
$\begingroup$

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|$$
$\endgroup$
6
  • 2
    $\begingroup$ How large is the problem in terms for the number of $x_i$? $\endgroup$
    – Richard
    Dec 7, 2023 at 16:19
  • 1
    $\begingroup$ And can you share your objective function? $\endgroup$
    – Richard
    Dec 7, 2023 at 16:53
  • $\begingroup$ @Richard, please see edits, thx $\endgroup$
    – jf328
    Dec 8, 2023 at 1:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Stef
    Dec 8, 2023 at 10:14
  • $\begingroup$ 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? $\endgroup$
    – Stef
    Dec 8, 2023 at 10:16

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Josiah
    Dec 8, 2023 at 12:02
  • $\begingroup$ 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. $\endgroup$ Dec 8, 2023 at 13:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – Prem
    Dec 8, 2023 at 14:17
  • $\begingroup$ 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. $\endgroup$
    – Prem
    Dec 8, 2023 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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