Originally posted by: Robop

Hi,

I'm just starting with cplex. Sorry for such a formulas, but plain text doesn't work for some reason.

I have an optimization problem of such kind:
var x,y,z;
min_{x,y} max_{z in Z} sum F(x,y,z)

Since I was not able to find an existing function for minimax problems in cplex by default, I reformulated my problem in a following way:

var x,y,z,C;
min_{x,y} C
subject to:
forall (z in Z)
sum F(x,y,z) <= C;

The problem is that I can't use variables in forall statement(for variable z). But I have NO idea how to program my model in other way!
How can I model this issue? Or is it any simple way to solve minimax problems in cplex?
I will appreciate any ideas!
Thank you in advance!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Are you talking about writing down your problem in OPL?
In that case you could just write

range Z = 0..10;
dvar int z in Z;

provided that Z is some sort of range of numbers. The above will restrict z to values between 0 and 10. Is that what you want to do?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you are trying to solve (in the general case that you stated) is a bilevel program. This is much more complicated than a mixed integer program, and CPLEX can only solve the latter.

In some special cases, bilevel programs can be modeled as integer programs, though, but I guess that most of the meaningful bilevel programs cannot.

Your approach with using the auxiliary C variable should work, so it seems that currently you are facing an OPL modeling problem. But you should be aware of the fact that your approach requires one constraint for every single value in the domain of Z. So, the approach will only be practical if Z is small, in particular finite. Therefore, z cannot be continuous, must be bounded, and if z is a vector instead of a single variable, then it should better be of small dimension to avoid the combinatorial explosion in the domain.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Robop

Dear Daniel and Tobias,
thank you for the answers!

Daniel, my problem is a little bit different. I describe it below.

Tobias, do you have any hints - how this bilevel models could be modeled and solved?

I have tried to implement a solution for a little bit more complicated problem (tiny even though) and find out that it does not work in my case(works incorrectly).
Imagine, there is a warehouse and I have to decide about orders of different products at the beginning of each period.
I have ordering and holding costs. However, demand is not known exactly - only upper and lower bounds are given.
My goal is to optimize the worst case - to solve the minimax problem.

I attached the SmallModel file wich contains the initial model and modified one below(here I have tried to implement the proposed apparoach with additional variable C).
Problem is that I want to check all possible combinations of demands in each period, when each of them changes in fixed borders (borders could be different). The proposed approach works incorrectly however: it just finds the maximal possible value of demand through all periods and takes it as a value in all planning periods.

Another guess is that even if I implement the approach, I can't simply check all possible combinations of demands in each planning period, because this is a tremendous amount depending on problem size(as it has been already said by Tobias). So I need some optimizational algorithm to find the inner maximum.

But I can't believe that this tiny study example could not be solved by the ILOG - the proffessional optimization software. I guess that I just do not know how to do this. =)

So once again:
Any ideas how to model the proposed problem in ILOG?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Unfortunately, it is true that CPLEX does not solve minimax problems. CPLEX can only deal with convex sets plus integrality, but minimax problems do not necessarily have this property.

What should be possible is to use a cutting plane approach (Bender's decomposition), where you introduce a new auxiliary variable for the objective of the inner maximization problem. Then, when CPLEX presents you a solution for the outer variables, you solve the inner maximization problem and find the value for the auxiliary objective variable.

But I am not sure whether this would really give a useful solver for larger problems. You should really look into the literature and try to find out which of the existing approaches suits your needs.

For example, the paper "A Branch-and-cut Algorithm for Integer Bilevel Linear Programs" of Scott DeNegre and Ted Ralphs (http://www.optimization-online.org/DB_HTML/2008/06/1997.html) should give you a good starting point. They implemented a solver, which is available in the COIN-OR repository.
Tobias
#CPLEXOptimizers
#DecisionOptimization