2
$\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 $\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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

You can use a binary variable z in {0,1}:

x_1 <= x_2 x_1 <= x_3 x_1 >= x_2 - Mz x_1 >= x_3 -M(1-z)

It gives you a PLNE. If you have one min inequality, it's better to use the previous answer.

$\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.