2
$\begingroup$

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?

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

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – S_Scouse
    Apr 1, 2021 at 13:58
1
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Apr 1, 2021 at 13:31

Your Answer

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

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