Linearizing a Max Function in the constraint - not working

Question

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?

Answer 1

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.

Answer 2

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?

Answer 3

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)