3

The problem is described as follows: considering $n$ variables which are continuous and bounded such that $$L_i \le x_i \le U_i\quad \forall i=1,2,\dots,n.$$

How can i define a set of mixed integer linear inequalities such that the feasible solution will be

$$y = \max(x_1,x_2,\dots,x_n).$$

I am not certain of my approach but this is what i have so far

constraint 1: $y \ge x_i$;

constraint 2: $y \ge x_i + (U_i-L_i)w$;

where $w\in\{0,1\}$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
george
  • 135
  • 4

1 Answers1

5

Constraint 1 is fine. It imposes $y \ge \max(x_1,x_2,\dots,x_n)$. For constraint 2, you need to reverse the inequality and also introduce binary variable $w_i$ (with the interpretation that $w_i=1$ implies that $x_i$ is the maximum): $$y \le x_i + M_i (1 - w_i).$$ We want the constraint to be redundant if $w_i = 0$, so take $M_i = \max(U_1,\dots,U_n) - L_i$.

Now also impose $$\sum_{i=1}^n w_i=1.$$ (Alternatively, you can relax this to $\ge 1$.)

If $n=2$, this formulation reduces to the one given here.

RobPratt
  • 32,006
  • 1
  • 44
  • 84