# Linear programming: reduce a constraint that includes a minimum

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).

• Is the coefficient of $x_{1}$ in $c$ positive or negative? Are you willing to consider using a 0-1 integer variable if necessary? – Brian Borchers Dec 29 '19 at 15:36
• all the entries in $\mathbf c$ are positive/nonnegative. I would prefer to avoid 0-1 integer but if it's the only way to go... – Yauhen Yakimenka Dec 29 '19 at 16:04
• – D.W. Dec 29 '19 at 20:33

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.
• 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. – Rob Pratt Dec 29 '19 at 17:19
• actually, in my problem, all $x_i <= 1$ (this is enforced by $A \mathbf x = \mathbf b$ constraints). Hence, $M = 1$ naturally. – Yauhen Yakimenka Dec 29 '19 at 19:51