# Linearizing a Max Function in the constraint - not working

I have a minimization function which is in its simplest form looks like below. I am including the index of the variables.

min cost * Z

S.t.

Z >= max(a1, a2, a3,....aN)


where Z and a's are variables. Since this is a minimization, I wrote a constraint in AMPL, that goes through the index of these variables and enforces the following.

Z >= a1

Z >= a2

......

Z >= aN


However, Z is set to a value that is greater than the maximum of a1, a2,....., aN. Please let me know how can I optimize this formulation so that Z is set to exactly the value of the max (a1, a2,....,aN). Do I need to use big-M formulation to do that? If yes, how do I do that?

• Looks good to me. Maybe you can show the AMPL code ? Mar 31 '21 at 17:35
• For this linearization to work, you need cost > 0. Is that true here? Mar 31 '21 at 17:46
• Yes all the costs are >= 0. Mar 31 '21 at 17:59
• Are you sure you are returning the value of $Z$, and not the value of the objective function ? Mar 31 '21 at 18:27
• $\ge 0$ is not sufficient. The costs need to be $>0$. Mar 31 '21 at 18:39

If you want $$z=\max(a_1,\dots,a_n)$$, you can first enforce $$z\ge\max(a_1,\dots,a_n)$$ via linear constraints: \begin{align} z &\ge a_i &&\text{for all i} \tag1 \end{align} If you cannot rely on the objective to also enforce $$z\le\max(a_1,\dots,a_n)$$, let $$M$$ be a small constant upper bound on $$z$$, let $$\ell_i$$ be a constant lower bound on $$a_i$$, introduce binary variables $$x_i$$, and impose linear constraints: \begin{align} \sum_i x_i &\ge 1 \tag2 \\ z - a_i &\le (M - \ell_i)(1-x_i) &&\text{for all i} \tag3 \end{align} Constraint $$(2)$$ enforces $$x_i = 1$$ for some $$i$$. Constraint $$(3)$$ enforces $$x_i = 1 \implies z \le a_i$$. Alternatively, replace $$(3)$$ with an indicator constraint.

You could try fudging the objective function by replacing any zero cost with a cost of $$\epsilon > 0$$, where $$\epsilon$$ is chosen small enough not to cause the selection of a suboptimal solution but large enough that $$\epsilon * (z-\max_i a_i)$$ does not look like rounding error to the solver. Selecting $$\epsilon$$ is a bit of an art form, but if this works it avoids the $$M$$ constant and extra binary variables in Rob's approach.

Another possibility: Can you just solve your model as it currently is and then post-process the solution, adjusting $$z$$ downward as needed?

• Post-processing isn't an option in my case. However, I will try the first solution you propose. I would like to avoid binary variables if possible. Apr 1 '21 at 13:58

Some modeling languages allow max and then you do not need to use big M.

With CPLEX in OPL you can write

int nbKids=300;

{int} buses={30,40,50};

dvar int+ nbBus[buses];
dvar int maxNbOfBusesGivenSize;

minimize maxNbOfBusesGivenSize;

subject to
{
maxNbOfBusesGivenSize==max(i in buses) nbBus[i];
sum(i in buses) i*nbBus[i]>=nbKids;
}

execute DISPLAY_After_SOLVE
{
writeln("The max number of buses is ",maxNbOfBusesGivenSize);
writeln("nbBus = ",nbBus);
}


and in python docplex

from docplex.mp.model import Model

mdl = Model(name='buses')

nbKids=300;
buses=[30,40,50]

#decision variables
mdl.nbBus = {b: mdl.integer_var(name="nbBus"+str(b)) for b in buses}

# Constraint
mdl.add_constraint(sum(mdl.nbBus[b]*b for b in buses) >= nbKids, 'kids')

# Objective
mdl.minimize(mdl.max(mdl.nbBus[b] for b in buses))

mdl.solve(log_output=True,)

mdl.export("c:\\temp\\buses.lp")

for v in mdl.iter_integer_vars():
print(v," = ",v.solution_value)

• Yes, minimizing the max does not require big-M, and SAS also automates the linearization in that case. But the OP has a different objective. Apr 1 '21 at 13:31