Originally posted by: Mintch Zulitch

We all know that it is possible to recall optimization information during MIP, but is it possible to use callback structure in CP using java API's ? It should be noted that I'm working on a paper declaring that if 50 job are scheduled on one machine then that machine should be marked as out-of-service for changing tools for 1 hour.

Thanks in advance.

Originally posted by: rdumeur

Hi,

In CP you don't need callbacks because you can access earch intermediate solution using startNewSearch(), next() and endSearch() on the CP object. If you need to express a constraint, you should be able to express it using the modeling language.  Especially for temporal constraints that can be, in CP optimizer, applied to interval variables.

For instance, our experts say that the following model:

using CP;

int n=100;
int Q = 100;
int D = 10;
// Generate random data
int q[i in 1..n] = 1+rand(Q div 5);
int d[i in 1..n] = 1+rand(D);

int m = n;
int horizon = 100000;

execute {
  writeln("Quantities: ", q);
  writeln("Durations: ", d);
}

dvar interval production[i in 1..n] in 0..horizon size d[i];
dvar interval maintenance[j in 1..m] optional in 0..horizon size 10;
dvar sequence machine in
  append(all(i in 1..n) production[i],
          all(j in 1..m) maintenance[j]);

cumulFunction level =
  sum(i in 1..n) stepAtStart(production[i], q[i]) -
  sum(j in 1..m) stepAtEnd (maintenance[j], 1, Q);

execute {
  var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(production));
}

minimize max(i in 1..n) endOf(production[i]);
subject to {
  noOverlap(machine);
  level <= Q;
  forall(j in 1..m-1) {
    endBeforeStart(maintenance[j], maintenance[j+1]);
    presenceOf(maintenance[j+1]) => presenceOf(maintenance[j]);
  }
}  
 

show that by using scheduling cumul function on interval variables, propagation (if side constraints aren't too complex) is able to place interval so that the cumul function constraint is always honored.

I hope this helps.

Cheers,

Originally posted by: Mintch Zulitch

Thanks for your help. Can you verbally explain your concept? Is there any way to model the problem without deploying Cumulative function?

Originally posted by: rdumeur

Hi,

The concept of cumulative function is well described here:

http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.ide.help%2FContent%2FOptimization%2FDocumentation%2FOptimization_Studio%2F_pubskel%2Fps_opl_Starting_kit327.html

the presented model rely on the cumulative function to ensure maintenance interval presences.  the (level <= Q) express the fact production steps must be compensated by maintenance tasks. If you look at the definition of "level" you'll see that the positive term corresponds to production steps and that maintenance steps will contribute to reduce the "level" value, maintaining it below Q.

Originally posted by: Mintch Zulitch

Hi,
Some people suggest me to use "forbidstart" in combination of "Stepfunction". But I don't know how to use it.
Also in your code you have used "rand" function. But there is no need to randomize,
since the problem explicitly states that after processing 50 jobs on a machine, tool change is needed with duration of 1 hour.
Also, I implemented your strategy using Cumulative function but it didn't return desired result. And this is my Code in Java syntax:

IloIntervalVar tool_interval = CP_fms.intervalVar(1);
IloCumulFunctionExpr[] tool = new IloCumulFunctionExpr[50];
for (int i = 0; i < nbJobs; i++) {
 for (int j = 0; j < 50; j++) {
  tool[j] = CP_fms.sum(tool[j],
  CP_fms.stepAtEnd(job, 1));
  CP_fms.le(tool[j], 50);
  if (i == j) {
   CP_fms.add(CP_fms.endBeforeStart(job, tool_interval));
   tool[j] = CP_fms.sum(tool[j],
   CP_fms.stepAtStart(job, -51));
   machine.add(tool_interval);
   ends.add(CP_fms.endOf(tool_interval));
  }
 }

}

In other words, I didn't return following result:

(Picture file in attachment)

Originally posted by: rdumeur

Dear 0372_Mintch_Zulitch

The rand() function was used in the model provided as an example to generate production activities with random durations and output quantities. It wasn't meant to solve exactly your problem, but as said, to illustrate how the cumul function could be used to control the presence of maintenance activities.

Now, modifying the above model by setting a constant duration (1) for production and maintenance intervals and 50 for the level at which you want a maintenance interval, you get the following model:

using CP;

int n=100;
int Q = 50;
int m = n;
int horizon = 100000;
dvar interval production[i in 1..n] in 0..horizon size 1;
dvar interval maintenance[j in 1..m] optional in 0..horizon size 1;
dvar sequence machine in
  append(all(i in 1..n) production[i],
          all(j in 1..m) maintenance[j]);

cumulFunction level =
  sum(i in 1..n) stepAtStart(production[i], 1) -
  sum(j in 1..m) stepAtEnd (maintenance[j], 1, Q);

execute {
  var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(production));
}

minimize max(i in 1..n) endOf(production[i]);
subject to {
  noOverlap(machine);
  level <= Q;
  forall(j in 1..m-1) {
           endBeforeStart(maintenance[j], maintenance[j+1]);
           presenceOf(maintenance[j+1]) => presenceOf(maintenance[j]);
   }
}  
 

That produce the level function, the image of which is attached. One can see very clearly the time at which the maintenance intervals are inserted, which correspond to the  "level == 0" state.

Please feel free to adjust the maintenance & production interval duration to reflect your own problem data.

I hope it helps.

Cheers,

Originally posted by: rdumeur

Hi,

Some comments about your java code: as it doesn't correspond to the OPL model I provided, I guess it is normal to have different results.
Please first replicate the OPL model in C++. You don't need to use an array of cumul function, but use the += and -= operators to model the cumul function you need. Please have a look at the documentation:

http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.ide.help%2Frefcppopl%2Fhtml%2Fclasses%2FIloCumulFunctionExpr.html

and at the sched_cumul.cpp example which illustrates how cumul functions are manipulated :

http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cpo.help%2FCP_Optimizer%2FGetting_started%2Ftopics%2Fschedcumul_program.html

Your final C++ model should be very similar to the OPL one.

I hope this helps.

Cheers,

Originally posted by: Mintch Zulitch

Thanks for your help,
I coded the problem according to your instruction in JAVA environment and it surprisingly returned desired sequence. But I think there exists a problem...
You have mentioned neither any relationship between maintenance and production variables nor the relationship between production intervals in the Constraints set. And another problem is that when I removed the constraints "endBeforeStart" and "presenceOf", it returned the same result !!!
Also, I want to know that whether it is possible to generalize the code to more than one machine. Should we declare more than one cumulFunction in the model ?

Originally posted by: rdumeur

Dear Mitch,

There is actually nothing to be  surprised of. There is indeed a relation between maintenance and production: the cumul expression precisely. The "level <= Q" constraints ensures that the cumul expr doesn't go above a given amount. It does so by propagating on the execution status of maintenance intervals.

The endBeforeStart and PresenceOf constraints are there to order maintenance intervals so that the ones with lower indices are placed first.

If you want to generalize to more than one machine, you indeed need to associate one cumul function to each machine.

Cheers,

Originally posted by: Mintch Zulitch

Thank you very much, your model is actually smart and intuitive.
Conceptually, the constraints "PresenceOf" and "endBeforeStart" must be imposed on the model, but there is no obligation to consider them in run-time, since the result with or without them is the same. To be precise, since all maintenance intervals have equal duration of one hour, the interval (i) or (i+1) can be taken after 50 jobs.

Originally posted by: rdumeur

Dear Mitch,

Indeed, but if you remove these constraints, because all the maintenance intervals are equivalent, the solver is left to decide which one of these interval must be actually used, which can lead to combinatorial explosion. So such symmetry-breaking constraints, removing the need for the solver to choose between maintenance intervals, greatly contribute to search efficiency!

Cheers,