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 resolve this issue? Or is it any simple way to solve minimax problems in cplex?
I will appreciate any ideas!
Thank you in advance!
#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: SystemAdmin

Assuming that Z is a range of values for the z variable, I think you are already on the right track. There is no direct minimax function in CPLEX and linearizing the formulation like you have, would be the way to go. You could change the forall statement so that it uses a local variable instead of z and then use that in the function F. You would then need to have an additional constraint to set the z variable to the appropriate value as well. The pseudo code could look like the following:

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

Here's a trivial model in OPL implementing this approach:

range X=1..4; range Y=3..15; range Z=7..10; dvar int+ x in X; dvar int+ y in Y; dvar int+ z in Z; dvar 

float C; minimize C; subject to
{ forall(zIndex in Z)
{ 4*x - 3*y + 5*zIndex <= C; 
} 4*x - 3*y + 5*z == C; 
}

Ofcourse, for the above model, a simpler formulation exists as such:

range X=1..4; range Y=3..15; range Z=7..10; dvar int+ x in X; dvar int+ y in Y; dvar int+ z in Z; minimize 4*x - 3*y + 5*z; subject to
{ z==max(zElements in Z)zElements; 
}

That said, for models with a certain formulation, OPL does allow the user to specify minimax problems in the objective function itself. I would suggest you to go through sched_cumul example (under <opl>\examples\opl\sched_cumul) which provides you with one such example using the CP (and not CPLEX) engine. More about this example can be found in the following documentation link:
http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r3/index.jsp?topic=%2Filog.odms.ide.help%2FContent%2FOptimization%2FDocumentation%2FOptimization_Studio%2F_pubskel%2Fps_opl_Starting_kit327.html
#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Robop

Dear AbhishekRaman,
great thanks for your help!!!

However I have such an objective function which is independent from z directly:

int a,b,c,d;
range Z= 7..10;
range Y= 2..8;

dvar int x;
dvar int+ x1;
dvar int- x2;
dvar int y in Y;
dvar int z in Z;

min_{x,y} max_{z} (a*y + b*x1 + c*x2);
subject to{
d + y == z + x;
x1 >= 0;
x1 >= x;
x2 >= 0;
x2 >= -x;
}

Would it be right if I just make my program like this:

int a,b,c,d;
range Z= 7..10;
range Y= 2..8;

dvar int x;
dvar int+ x1;
dvar int- x2;
dvar int y in Y;
dvar int z in Z;
dvar float C;

minimize C; (a*y + b*x1 + c*x2)
subject to{
d + y == z + x;
x1 >= 0;
x1 >= x;
x2 >= 0;
x2 >= -x;
forall(zIndex in Z){
a*(zIndex + x - d) + b*x1 + c*x2 <= C;
}
a*y + b*x1 + c*x2 == C;
}

Will this work correctly?
Here I just put to the goal function an expression from restrictions instead of y variable. Is it sufficient? Other variables are also connected with z through other restrictions.
#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: SystemAdmin

What you have looks right except for some syntactic errors. Here's a modified version of what you have that runs without errors. I donot know about the model's application and hence will not be able to validate the results. I would thus suggest you to run some tests with some small ranges and see if the outputs are per your expectations:

//int a,b,c,d;//need to initialize them separately 

int a=1;
//dummy #s for a,b,c,d 

int b=2; 

int c=3; 

int d=4; range Z= 7..10; range Y= 2..8;   dvar 

int x; dvar int+ x1; 
//dvar int- x2;//do you mean x2 is an integer <= 0?? dvar 

int x2; dvar 

int y in Y; dvar 

int z in Z; dvar 

float C;   minimize C; 
//(a*y + b*x1 + c*x2) subject to
{ d + y == z + x; x1 >= 0; x1 >= x; 
//x2 >= 0; //commented, should this be x2<=0 instead?? x2 >= -x; forall(zIndex in Z)
{ a*(zIndex + x - d) + b*x1 + c*x2 <= C; 
} a*y + b*x1 + c*x2 == C; 
}

If all you want to do is choose z such that it is set at the maximum value of its range, you could simplify the above to:

//int a,b,c,d;//need to initialize them separately 

int a=1;
//dummy #s for a,b,c,d 

int b=2; 

int c=3; 

int d=4; range Z= 7..10; range Y= 2..8;   dvar 

int x; dvar int+ x1; 
//dvar int- x2;//do you mean x2 is an integer <= 0?? dvar 

int x2; dvar 

int y in Y; dvar 

int z in Z;   minimize (a*y + b*x1 + c*x2); subject to
{ d + y == z + x; x1 >= 0; x1 >= x; 
//x2 >= 0; //commented,should this be x2<=0 instead?? x2 >= -x; z==max(zElements in Z)zElements; 
}

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Robop

I have implemented such a solution for a little bit more complictaed 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 for 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 tried to implement the proposed apparoach).
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.

Any ideas how to model the proposed problem in ILOG?
#DecisionOptimization
#OPLusingCPLEXOptimizer