# 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 ? Commented Mar 31, 2021 at 17:35
• For this linearization to work, you need cost > 0. Is that true here? Commented Mar 31, 2021 at 17:46
• Yes all the costs are >= 0. Commented Mar 31, 2021 at 17:59
• Are you sure you are returning the value of $Z$, and not the value of the objective function ? Commented Mar 31, 2021 at 18:27
• $\ge 0$ is not sufficient. The costs need to be $>0$. Commented Mar 31, 2021 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. Commented Apr 1, 2021 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. Commented Apr 1, 2021 at 13:31
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 22, "wp-katex-eq": 0, "align": 2, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://or.stackexchange.com/questions/6035/linearizing-a-max-function-in-the-constraint-not-working", "fetch_time": 1723563456000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-33/segments/1722641079807.82/warc/CC-MAIN-20240813141635-20240813171635-00717.warc.gz", "warc_record_offset": 329421302, "warc_record_length": 32719, "token_count": 1120, "char_count": 3795, "score": 3.640625, "int_score": 4, "crawl": "CC-MAIN-2024-33", "snapshot_type": "latest", "language": "en", "language_score": 0.8418080806732178, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00017-of-00064.parquet"}