Originally posted by: AndyHam

Hi IBM,

I am new to CP with just 6 months' experience. I simply tried to execute the example called "Batch scheduling" to understand the stateFunction, but I got a following error:

Exception in presolve: Transition matrix for state function does not satisfy the triangle inequality (path 1->0->2)..

I did not change any single character, but the error occurs. 

Can you please tell me why I am having this error and how to fix it?

ps - I just copy & paste the codes in below.

Thanks,

Andy

 

 

/***********************************************************
* CP Optimizer Training - Batch Scheduling SOLUTION 4 Data *
************************************************************/
 
numberProducts = 5;
preparationTime = 30;

steps = [
{<1, 30, 1>, <2, 30, 2>, <3, 30, 3>},                 // <stepNumber, duration, temperatureCode>
{<1, 45, 2>, <2, 45, 3>, <3, 45, 4>, <4, 45, 1>},
{<1, 30, 1>, <2, 30, 4>, <3, 30, 3>},
{<1, 45, 4>, <2, 45, 1>, <3, 45, 2>},
{<1, 30, 4>, <2, 30, 3>, <3, 30, 2>}
];

orders = [12, 16, 14, 18, 13];

numberOvens = 3;
ovenCapacity = [4, 4, 4];

transitionTimes = {                                 // <code1, code2, transitionTime>
<1, 1, 0>, <1, 2, 5>, <1, 3, 10>, <1, 4, 15>, 
<2, 1, 5>, <2, 2, 0>, <2, 3, 5>, <2, 4, 10>, 
<3, 1, 10>, <3, 2, 5>, <3, 3, 0>, <3, 4, 5>, 
<4, 1, 15>, <4, 2, 10>, <4, 3, 5>, <4, 4, 0>
};

 

/******************************************************
 * CP Optimizer Traning - Batch Scheduling SOLUTION 4 *
 *                                                    *
 ******************************************************/
 
using CP;

/*******
* Data *
********/

int numberProducts = ...;
int preparationTime = ...;
range products = 1..numberProducts;

tuple productStepT {
   key int stepNumber;
   int duration;
   int temperatureCode;
}; 
{productStepT} steps[products] = ...;

int orders[p in products] = ...;

tuple taskT {
  key int productId;
  key int stepNumber;
  key int orderId;
  int duration;
  int temperatureCode;
};
{taskT} allTasks = {<p, s.stepNumber, o, 
                     s.duration, s.temperatureCode> 
                    | p in products, s in steps[p], o in 1..orders[p]};
                    
int numberOvens = ...;
range ovens = 1..numberOvens;

int ovenCapacity[ovens] = ...;

tuple transitionTimeT {
  key int code1;
  key int code2;
  int transitionTime;
};
{transitionTimeT} transitionTimes = ...;

int maxTime = sum(t in allTasks)(t.duration + preparationTime);

dvar interval tasks[t in allTasks] in preparationTime..maxTime size t.duration;
dvar interval taskOvenAlts[t in allTasks][o in ovens] optional;

cumulFunction ovenUsage[o in ovens] = sum(t in allTasks) pulse(taskOvenAlts[t][o], 1);
stateFunction ovenTemperature[o in ovens] with transitionTimes;

minimize max(t in allTasks) endOf(tasks[t]);

/**************
* Constraints *
***************/

constraints {

  // 30 minutes preparation is required between steps for each product order  
  forall(t1,t2 in allTasks : t1.productId == t2.productId &&
                             t1.stepNumber + 1 == t2.stepNumber &&
                             t1.orderId == t2.orderId) {
     endBeforeStart(tasks[t1], tasks[t2], preparationTime);
  }

  // for each oven, ovenUsage cannot exceed oven capacity
  forall(o in ovens)
    ovenUsage[o] <= ovenCapacity[o];  
 
  // each task can be executed on at most one oven
  forall(t in allTasks) 
    alternative(tasks[t], all (o in ovens) taskOvenAlts[t][o]);
  
  // the temperatureCode on an oven should correspond to the temperature of the task scheduled on the oven at any point in time
  forall(t in allTasks, o in ovens)
    alwaysEqual(ovenTemperature[o], taskOvenAlts[t][o], t.temperatureCode);  
  
}

int usedCapacity = sum(t in allTasks) t.duration;
int availPower = sum(f in ovens) ovenCapacity[f];

execute {
  writeln("Shortest possible makespan = " + (preparationTime + usedCapacity / availPower));
} 

#CPOptimizer
#DecisionOptimization

Originally posted by: PhilippeLaborie

Hi Andy,

It is because CP Optimizer is now more strict and checks that the state function satisfies the triangular inequality (which is a requirement for the state function). In the example, as mentioned in the error, the state transition 1 -> 0 -> 2 does not satisfy it since tt(1,0)=tt(0,2)=0 (these transitions are not mentioned in the transition times tuple set so they are 0 by default) whereas tt(1->2)=5. In fact the state 0 is not used in the example so I think the best way to fix the problem is to re-index the temperature codes so as to use {0,1,2,3} instead of {1,2,3,4}. 

I'll need to have a deeper look what changed in OPL/CPO as this example was working some versions ago.

Philippe

 

#CPOptimizer
#DecisionOptimization

Originally posted by: AndyHam

Dear Philippe, Thanks for your help. After I changed the index starting 0, it works!

#CPOptimizer
#DecisionOptimization