1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i guess you could generate all feasible optimal solutions with the regular constraint afterwards, you apply the 40% constraint to reject "bad" ones. In many cases all the solutions are only few optimal ones. $\endgroup$ – NoChance May 10 at 22:49
  • $\begingroup$ Solving the LP is outside the scope of this. Is there a way other than min() to model this? I can't think of any unless I have it be greater by 40% than both of them. $\endgroup$ – Ryder May 10 at 22:50
  • $\begingroup$ So you only want to stop at modeling? $\endgroup$ – NoChance May 10 at 22:51
  • $\begingroup$ Yeah exactly. This is part of a practice problem in University and the question only states to model the LP, not solve it. $\endgroup$ – Ryder May 10 at 22:52
  • 1
    $\begingroup$ @NoChance you can do a bit better than your suggestion of generating all feasible optimals and then rejecting "bad" ones: SPlit the problem into 2 LP problems, each of which you can model. Then at the end choose the model for which the objective function is better, as the one determining the $x_i$. $\endgroup$ – Mark Fischler May 10 at 23:04
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Unfortunately there are no other interactions which would help with this. I guess writing the two constraints which make it larger by 40% than both of them is the only way to go. $\endgroup$ – Ryder May 10 at 22:56
  • $\begingroup$ If you have upper bounds on $x_2$ and $x_3$, you could at least model the convex hull with linear constraints, which would be an improvement. But without those upper bounds, the convex hull is trivial. $\endgroup$ – Misha Lavrov May 10 at 22:58
  • $\begingroup$ I do have upper bounds, x_i are all <= 5000, however I am not sure what you mean by convex hulls (will probably cover that in the course later on, but haven;t yet) $\endgroup$ – Ryder May 10 at 23:00
  • $\begingroup$ I have elaborated on this idea. Basically, we can include points that don't satisfy the $\min$ constraint, but lie between two points that do, and this doesn't hurt us when we're optimizing a linear function, because such points won't be better anyway. $\endgroup$ – Misha Lavrov May 10 at 23:05
  • $\begingroup$ This is wonderful, thanks a lot! $\endgroup$ – Ryder May 10 at 23:13
0
$\begingroup$

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.

$\endgroup$

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.