3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

| improve this 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.