Originally posted by: rNeo

Hello, I am getting an interesting error when using the stepwise function as an objective function (in ILOG CPLEX Opt Studio 12.6). The code was written in OPL. The model consists of an assignment problem with an objective of minimizing total cost of assignments. The cost function is stepwise - if a resource is assigned to more than a certain quantity, an add-on cost is incurred in addition to the basic cost. 

The problem is this, the value returned by the OPL objective function expression and cplex.getObjValue( ) API do not match - all the problems are solved to optimality. The objective function expression is as follows:

dexpr float TotalCost = 
    sum (i in Resources)
                stepwise { 0 -> 1;
                       (Cost[i]) -> 20;
                       (Cost[i] + 848) -> 71 ;
                           (Cost[i] + 1696) -> 141 ;
                           (Cost[i] + 2544) -> 211 ;
                           (Cost[i] + 3392) -> 281 ;
                           (Cost[i] + 4240) -> 351 ; 10000} Z[i];

 

Where Z[ i ] is a count variable that measures the number of tasks a resource is assigned to:

forall (i in Resources)
  sum (j in Tasks)
    X[i][j] == Z[i];  

When I output the objective function expression as follows: writeln(thisOplModel.TotalCost) it is different from cplex.getObjValue( ) and cplex.getBestObjValue( ); To verify, I wrote a script to query the decision variables and calculate the cost - which matches with the objective function expression.  

I do not understand what is going on. This happened only when I added stepwise objective function - a linear objective function did not cause this issue. Any light shed on this will be greatly appreciated! Thank you.

 

 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

is cost solution value at a breakpoint of the stepwise ?

With MIP within CPLEX, the stepwise value can be either before or after the breakpoint, which may explain what you see.

Do not hesitate to post your entire model.

Regards

http://www-01.ibm.com/support/knowledgecenter/?lang=en#!/SSSA5P_12.2.0/ilog.odms.cplex.help/Content/Optimization/Documentation/CPLEX/_pubskel/CPLEX653.html

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: rNeo

Hi Alex, thanks for your reply. Here is my model:

// SETUP THE MATH MODEL

// Big M for Constraint 3
int M = nRP;                                                                                                            

// Indicate if Resource[i] is assigned to Task[j]
dvar int+ X[DPs][RPs] in 0..1;                                                                          

// Indicate if Resource[i] selected for pairing 
dvar int+ Y[DPs] in 0..1;                                                                                       

// Indicates how many times Resource[i] has been used                   
dvar int+ Z[DPs];  



dexpr float TotalCost = 
        sum (i in DPs)
                stepwise { 0 -> 1;
                       (TotalCost[i]) -> 20;
                       (TotalCost[i] + 848) -> 71 ;
                           (TotalCost[i] + 1696) -> 141 ;
                           (TotalCost[i] + 2544) -> 211 ;
                           (TotalCost[i] + 3392) -> 281 ;
                           (TotalCost[i] + 4240) -> 351 ; 10000} Z[i];
minimize (TotalCost);                                                                                  

subject to 
{

// (C1) Assign 1 Resource to each Task
ct1:                                                                                                                            
forall (j in RPs)
  sum (i in DPs)
    X[i][j] == 1;   

    
// (C2) Indicate if Resource[i] has been selected for pairing using Big M    
ct2:                                                                                                                           
forall (i in DPs)
  sum(j in RPs)
    X[i][j] <= M * Y[i];  
    

// (C3) Constraint the Number of Resources to be used    
ct3:                                                                                                                          
sum(i in DPs)
        Y[i] <= K;       
        
        
// (C4a-b) Meet bounds from Previous Models
ct4a:                                                                                                                            
        sum (i in DPs, j in RPs) 
        (RMDistanceClass[i][j] * X[i][j]) <= RMClassBoundUB; 


ct4b:   
        sum (i in DPs, j in RPs)
          IBDvalue[i][j] * X[i][j] >= IBDLB; 
          

// (C5) If IBD Value is missing, then set X = 0 for that pair               
ct5:                                                                                                                            
forall (i in DPs, j in RPs)
  if (IBDvalue[i][j] == -9)
        X[i][j] == 0;     
        
        
// (C6) Count the # of Times Each Resource has been assigned    
ct6:                                                                                                                            
forall (i in DPs)
  sum (j in RPs)
    X[i][j] == Z[i];   
    
  }  

I do not understand your question: the cost solution value is the solution of the entire problem. Also, this happens for some Knapsack sizes only (see ct3 in model) and for other Knapsack sizes, the values match. Thank you for any help you may offer.

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

let me explain with your example.

Take

int nRP=10;

range RPs=1..1;

range DPs=1..1;

 

int M = nRP; // Big M for Constraint 3

 

dvar int+ X[DPs][RPs] in 0..1; // Indicate if Resource[i] is assigned to Task[j]

dvar int+ Y[DPs] in 0..1; // Indicate if Resource[i] selected for pairing

dvar int+ Z[DPs]; // Indicates how many times Resource[i] has been used

 

float TotalCostC[i in DPs]=i*i*10;

 

　

dexpr float TotalCost=

sum (i in DPs)

stepwise { 0 -> 1;

(TotalCostC[i] + 848) -> 71 ;

(TotalCostC[i] + 1696) -> 141 ;

(TotalCostC[i] + 2544) -> 211 ;

(TotalCostC[i] + 3392) -> 281 ;

(TotalCostC[i] + 4240) -> 351 ; 10000} Z[i];

minimize (TotalCost); // Minimize Total Donor Cost

 

subject to

{

 

ct1: // (C1) Assign 1 Resource to each Task

forall (j in RPs)

sum (i in DPs)

X[i][j] == 1;

 

ct2: // (C2) Indicate if Resource[i] has been selected for pairing using Big M

forall (i in DPs)

sum(j in RPs)

X[i][j] <= M * Y[i];

 

 

 

// (C6) Count the # of Times Each Resource has been assigned

ct6:

forall (i in DPs)

sum (j in RPs)

X[i][j] == Z[i];

}

 

 

 

execute

{

writeln("TotalCost=",TotalCost)

writeln("obj=",cplex.getObjValue())

}

 

which gives

TotalCost=858

obj=0

Why do we have this discrepancy ?

Because during the solve,

stepwise { 0 -> 1;

(TotalCostC[i] + 848) -> 71 ;

means that if Z==1 then the value of the  stepwise is either 0 or 848

Since we have a minimization model, 0 will be chosen

When evaluated, the stepwise will take the right value as said in

IDE and OPL > Optimization Programming Language (OPL) > Language Quick Reference > OPL keywords > stepwise

stepFunction f=stepwise {0->3; 2};

assert f(-1)==0;
assert f(3)==2;
assert f(3.1)==2;

This is the reason why you got surprised.

Now, in your case a workaround, not to have this discrepancy would be to write

float epsilon=0.001;

and then

stepwise { 0 -> 1+epsilon;

and then the model gives

TotalCost=0

obj=0

regards

 

 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: rNeo

Hello Alex,

Thanks for your explanation. So I followed your notes but still have a problem. Now the objective function expression and the CPLEX GetObjValue API matches BUT when I query the decision variables to get the total overall cost, that value differs from objective function expression and the CPLEX API. 

I guess I am misinterpreting how to use the stepwise function. To give you a better idea, this is what I am trying to do:

The problem is a resource allocation type (knapsack problem). There are resources of different types. Each resource type has a specific base usage cost. There are 5 resource types in the problem and their base costs are:

Resource Type	Assumed Cost
1	$6827.84
2	$872.39
3	0
4	0
5	0
6	$6827.84

There are a total of 110 resources, each of which fits into a specific resource type mentioned above. There is an additional cost incurred (the step function) when a resource is assigned to more than a specific number of tasks. Additional usage cost is calculated the following way:

• No additional cost is incurred if a resource is assigned to less than 20 tasks
• Add $848 to base cost if a resource is assigned to anywhere between 20 - 70 tasks
• if more than 70 tasks then add $848 for each additional 70 tasks (i.e., 71-140 increase cost is $848 *2, etc.) 

I have modeled this using the following code:

dexpr float TotalCost=
sum (i in DPs)
stepwise { 0 -> 1;
(TotalCostC[i] + 848) -> 71 ;
(TotalCostC[i] + 1696) -> 141 ;
(TotalCostC[i] + 2544) -> 211 ;
(TotalCostC[i] + 3392) -> 281 ;
(TotalCostC[i] + 4240) -> 351 ; 10000} Z[i];

minimize (TotalCost); // Minimize Total Donor Cost

Is this a correct use of the stepwise function? Thanks again for all your help.

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: rNeo

Thanks again. Re-reading your explanation, after using the workaround that you suggested, why is the objective value 0 (in your example)? Shouldn't it be 10 as specified by your cost in float TotalCostC[i in DPs]=i*i*10;

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: rNeo

Hello Alex,

Sorry to bother you but can you please take a look at this. I think the stepwise function is not working correctly. Can you just let me know if the following use of the stepwise function is correct? I am trying to figure out if it is something I am doing wrong. There is a base cost of using a resource and there is an additional usage cost when a resource is assigned to more than a specific number of tasks. Additional usage cost is calculated the following way:

• No additional cost is incurred if a resource is assigned to less than 20 tasks
• Add $848 to base cost if a resource is assigned to anywhere between 20 - 70 tasks
• if more than 70 tasks then add $848 for each additional 70 tasks (i.e., 71-140 increase cost is $848 *2, etc.) 

I have modeled this using the following code:

dexpr float TotalCost=
sum (i in DPs)
stepwise { 0 -> 1;
(TotalCostC[i] + 848) -> 71 ;
(TotalCostC[i] + 1696) -> 141 ;
(TotalCostC[i] + 2544) -> 211 ;
(TotalCostC[i] + 3392) -> 281 ;
(TotalCostC[i] + 4240) -> 351 ; 10000} Z[i];

minimize (TotalCost); // Minimize Total Donor Cost

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

let me share a small example to help you test your ideas:

using CP;

int TotalCostC=1000;


stepFunction f=

stepwise { 0 -> 1;
(TotalCostC + 848) -> 71;
(TotalCostC + 1696) -> 141 ;
(TotalCostC + 2544) -> 211 ;
(TotalCostC + 3392) -> 281 ;
(TotalCostC + 4240) -> 351 ; 10000};

execute
{
writeln(f(0));
writeln(f(70));
writeln(f(280));
}


 

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: rNeo

Hi Alex, thank you for your example. It helped me solve the issue. Your approach was on the right track but not correct. For this to work, the epsilon value had to be subtracted, not added, as follows:

 

dexpr float TotalDonorCost = 
    sum (i in DPs)
                stepwise { 0 -> 1-epsilon;
                       (DonorStageCost[i]) -> 20-epsilon;
                       (DonorStageCost[i] + 848) -> 71-epsilon ;
                           (DonorStageCost[i] + 1696) -> 141-epsilon ;
                           (DonorStageCost[i] + 2544) -> 211-epsilon ;
                           (DonorStageCost[i] + 3392) -> 281-epsilon ;
                           (DonorStageCost[i] + 4240) -> 351-epsilon ; 10000} Z[i];
minimize (TotalDonorCost);                                             

To give context, the following stepwise function is what was needed:

 

 

Thanks again for your patience and all your help!

#DecisionOptimization
#OPLusingCPLEXOptimizer