0
$\begingroup$

I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or introduce additional variables) to turn this into a linear programme?

In other words, I have the problem that looks like the following: $$ \mathbf c' \mathbf x \to \min, $$ s.t. $$ A \mathbf x = \mathbf b,\quad x_1 = \min(x_2, x_3). $$

Update: I thought about substituting the constraint with a pair of constraints $x_1 \le x_2$, $x_1 \le x_3$ but it doesn't work if the coefficient of $x_1$ is positive in $\mathbf c$. And this is the case in my problem (actually all the entries of $\mathbf c$ a positive/nonnegative).

$\endgroup$
2
$\begingroup$

You can model this with a single binary variable and additional constraints, or you can just solve two linear programs, one with $x_1=x_2\le x_3$ and one with $x_1=x_3\le x_2$, and take whichever solution yields the better objective value.

$\endgroup$
  • $\begingroup$ I wonder which method is faster... $\endgroup$ – Yauhen Yakimenka Dec 29 '19 at 16:48
  • 2
    $\begingroup$ Here is a binary formulation, which requires an upper bound of $M$ on your variables $x_2$ and $x_3$. It would probably be faster than solving two independent LPs from scratch. But you could speed up the two-LP approach by first solving your original LP with $x_1\le x_2$ and $x_1\le x_3$ and then using the dual simplex method to solve the two LPs starting from an optimal basis. This approach mimics what a MILP solver would do under the hood, but without requiring the big-M constraints. $\endgroup$ – Rob Pratt Dec 29 '19 at 17:19
  • $\begingroup$ actually, in my problem, all $x_i <= 1$ (this is enforced by $A \mathbf x = \mathbf b$ constraints). Hence, $M = 1$ naturally. $\endgroup$ – Yauhen Yakimenka Dec 29 '19 at 19:51

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.