1
$\begingroup$

Suppose I have a binary variables $b$ and two real variables $x$ and $y$ is there a way to assign $z_1=\min(x,y)$ and $z_2=\max(x,y)$ using mixed integer linear programming?

This is my attempt. Assume $-M<x,y<M$. Then let $$-bM\leq x'\leq bM$$ $$x-(1-b)M\leq x'\leq x+ (1-b)M$$

$$-(1-b)M\leq x''\leq (1-b)M$$ $$x-bM\leq x''\leq x+ bM$$

$$-(1-b)M\leq y'\leq (1-b)M$$ $$y-bM\leq y'\leq y+ bM$$

$$-bM\leq y''\leq bM$$ $$y-(1-b)M\leq y''\leq y+ (1-b)M$$

$$z_1=x'+y'$$ $$z_2=x''+y''$$ $$z_1\leq z_2.$$

Is there anything simpler than this?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You do not need $x'$ and $y'$: $$x - 2bM \leq z_1 \leq x + 2bM$$ $$y - 2(1-b)M \leq z_1 \leq y + 2(1-b)M$$ $$x - 2(1-b)M \leq z_2 \leq x + 2(1-b)M$$ $$y - 2bM \leq z_2 \leq y + 2bM$$ $$z_1 \leq z_2.$$ Depending how the minimum and maximum are used, you may not need a binary variable. For example: $$\max\{x,y\} \leq z$$ is equivalent to: $$x \leq z$$ $$y \leq z.$$

$\endgroup$
5
  • $\begingroup$ So in this case $b=0$ means $x\leq y$ and $b=1$ means $x\geq y$? $\endgroup$ Commented Sep 6, 2020 at 17:00
  • $\begingroup$ I want exact assignment and so $x\leq z$ and $y\leq z$ will not work. $\endgroup$ Commented Sep 6, 2020 at 17:00
  • $\begingroup$ Why $2b$ and $2(1-b)$ and not just $b$ and $(1-b)$ respectively? $\endgroup$ Commented Sep 6, 2020 at 17:02
  • $\begingroup$ @1.. yes @ interpretation of $b$. You need the factor $2$ because $2M$ is the largest absolute difference between $x$ and $y$. For example, $y-2(1-b)M \leq z_1$ is tight whenf $x=-M$ and $y=M$. $\endgroup$ Commented Sep 6, 2020 at 17:14
  • $\begingroup$ @1.. please mark this question as answered if you are satisfied $\endgroup$ Commented Oct 31, 2020 at 17:49

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.