# Linear programming: reduce a contstraint that includes minimun

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 $$\min$$ to the following pair: $$x_1 \le x_2$$ and $$x_1 \le x_3$$. However, this doesn't work if $$x_1$$ has a positive coefficient in $$\mathbf c$$, which is exactly the case for me. In fact, all the entries are positive in $$\mathbf c$$.

• – D.W.
Dec 29 '19 at 20:34
• sorry :( I was impatient to get responses Dec 30 '19 at 9:20

Solve two linear programs. The first has the constraints $$A \mathbf x = \mathbf b,\quad x_1 = x_2 \le x_3.$$ The second has the constraints $$A \mathbf x = \mathbf b,\quad x_1 = x_3 \le x_2.$$ Choose whichever solution gives you a smaller value for $$\mathbf c' \mathbf x$$.
This works for your particular situation. It doesn't scale to a case where you have a large number of $$\min$$ constraints.