Minimizing a maximum

[Lance Noel]

Hello all!  

I have an objective function where I want to minimize the maximum value over a time period, e.g. min(max(y[i]+sum(x[i,j]))), where y is a parameter and x is a decision variable for i periods and j resources.  I've read online that Pyomo does not support the use of max (or similar) functions in objective rules.  Does anyone have advice on how to minimize a maximum in Pyomo?  Thanks in advance!

L

[David Woodruff]

There is a standard technique for this given in many places, e.g., page 14 of these notes:

https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut04.pdf

--
You received this message because you are subscribed to the Google Groups "Pyomo Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pyomo-forum...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Giorgio Balestrieri]

In short: create a (non-indexed!) auxiliary variable z with the constraint that z >= y[i]+sum(x[i,j]) for all i, then minimize z

[Lance Noel]

Thanks both for the quick replies.  I'm not sure I understand it completely (but starting to make sense), but I will research this a bit more - is there an agreed upon name for this technique?  

[Giorgio Balestrieri]

There probably is one but I'm not aware of it. In a nutshell, you can't use "max(<whatever expression>)", but you can define an auxiliary variable and make sure it's higher than all instances of <whatever expression> (say it's indexed on a given set). The catch is that, although z is hypothetically not upper bounded, the fact that you are minimizing it will ensure that the solver makes it has the minimum possible value.

In other words, z is guaranteed (by the constraint) to be larger or equal than all instances of <whatever expression>, and the lowest possible value it can have is effectively max(<whatever expression>).

In your case, if your expression if defined over time, you can imagine z as a horizontal line that has to be at least as large as the highest value of your expression. Your solver will push it down as much as possible, i.e. until it touches the "peak" of your expression.

I'm sure you can find a much better  definition somewhere, but I hope it helps.

[Lance Noel]

Ah, got it.  Your explanation at the end makes a lot of sense, thank you!  It's too bad the documentation of such techniques is not better though. 

[sand...@newsunroad.com]

I think I understand the general idea here, but I'm not quite sure how to apply it to my problem. Ideally I would like a hard constraint that ||x||_{\infty} == c, where the left hand side is the infinity norm of some vector and the right hand side is some scalar constant. Alternatively, I could see it as an additional objective.

[becker.ph...@gmail.com]

z has to be part of the objective function in order to minimize it and so push towards the border given by the inequality.