How to specify a constraint for an LP when it needs to be related to ONE of two other variables depending on smallest?

Question

So I have a problem where I need to model a LP, but the question specifies a constraint such that x_1 must be at least 40% more than x_2 or x_3

I thought of defining it as x_1 >= 1.4 (min(x_2, x_3)) but that's not allowed.

Another approach I thought of was defining two constraints as such:

x_1 >= 1.4 (x_2)

x_1 >= 1.4 (x_3)

But this will lead it to be greater than the max (x_2, x_3) which is feasible but not optimal. Any help would be appreciated.

Answer 1

This cannot be written as a linear constraint.

A combination of linear constraints will always define a convex region. However, this region is not convex: it includes the points $(x_1, x_2, x_3) = (1, 2, 0)$ (since in this case, $x_1 \ge 1.4 x_3$ because $1\ge 0$) and $(x_1, x_2, x_3) = (1, 0, 2)$ (since in this case, $x_1 \ge 1.4x_2$ because $1\ge0$) but not the midpoint between them, $(x_1, x_2, x_3) = (1,1,1)$ (in this case $x_1 < 1.4x_2$ and $x_1 < 1.4x_3$ because $1 < 1.4$).

It's possible that interactions with other constraints will simplify the situation, though. For example, if you know $x_2 \le x_3$, then it's enough to require $x_1 \ge 1.4x_2$.

---

Assuming we know $0 \le x_1$ and $x_2, x_3 \le 5000$, we can do the following. In the case $x_1 \ge 1.4x_2$ we have \begin{align} x_1 - 1.4 x_2 &\ge 0 \\ x_1 - 1.4 x_3 &\ge -7000. \end{align} In the case $x_1 \ge 1.4x_3$ we have \begin{align} x_1 - 1.4x_2 &\ge -7000 \\ x_1 - 1.4 x_3 &\ge 0 \end{align} Points that are on a line segment between a point satisfying the first constraint and a point satisfying the second constraint will satisfy the inequalities \begin{align} x_1 - 1.4x_2 &\ge -7000t \\ x_1 - 1.4x_3 &\ge -7000(1-t) \end{align} for some $t$ such that $0 \le t \le 1$. We might as well include such points: if we're going to be optimizing a linear function, then the interior of a line segment is not going to be optimal anyway, because it's not as good as the endpoints. And anything that satisfies the first or the second set of constraints will still be feasible for the third set (taking $t=0$ or $t=1$ respectively).

In other words, taking this third set of constraints, with the inequality $0 \le t \le 1$ on $t$, is a model for $x_1 \ge \min\{1.4x_2, 1.4x_3\}$ that's good enough when solving a linear program.

Answer 2

I’m going to offer a different take here. I would interpret “x_1 must be at least 40% more than x_2 or x_3” as saying “x_1 must be at least 40% more than x_2” and “x_1 must be at least 40% more than x_3”. In that case you want $x_1 \ge 1.4\max\{x_2,x_3\}$, not $\min$, and your idea of using $$x_1 \ge 1.4 x_2$$ $$x_1 \ge 1.4 x_3$$ is correct.