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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.