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$
3

1 Answer 1

Reset to default
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$
3
  • $\begingroup$ I wonder which method is faster... $\endgroup$ Commented Dec 29, 2019 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$ Commented Dec 29, 2019 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$ Commented Dec 29, 2019 at 19:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.