Originally posted by: WeeLoon

I am modelling a scheduling problem using CP optimizer. There is a very weird behaviour.

Occasionally, the model will deliver a incredibly bad result. Here is the situation:

Same model, same data, time limit 60s:

1. running on intel i3, no matter i set the workers to -1, 1 or 4, the result is good, in fact even if i set the time limit to 5s, the result is good enough.

2. running on a much powerful intel xeon, when i set the workers to 4, the result is incredibly bad. If I set the workers to -1, the result is good.

I have no explanation for this case. One of my suspected reason is the mix of int and float in staticLex function.

Is it we cannot mix int and float in staticLex function? Will it affect the result? 

My staticLex function has like 8 objectives. This weird behavior seems to start happen occasionally after I change my objetives from 6 int to 6 int + 2 float.

Any suggestion or idea is much appreciated. Thanks.

Originally posted by: ChrisBr

Hello,
It might be possible that mixing integers and floats causes a problem in some cases.
Could you send us your model with that we'll be able to investigate the issue and try to find a workaround?
Thanks,
Chris.

Originally posted by: WeeLoon

Hi Chris,

Here is my model. Thanks for taking precious time to help me.

Hi,

have you tried with cplex 12.9 ?

and do not hesitate to share data.txt if you want anybody to try.

regards

Originally posted by: WeeLoon

It is 12.9 indeed. I will share the data on Monday, as I have no access now.

Originally posted by: PhilippeLaborie

Hello. Could you be a bit more precise about the results being "good" or "bad": could you attach the search log corresponding to the two situations?

Beside a data file, could you also post a .cpo file corresponding to your problem instance?

As the model uses floating point expressions, there is no guarantee that the resolution behaves the same on different platforms. So it could be either that there is indeed an issue in CPO or that the resolution of this problem instance is very unstable and a small change in the search (like running on different machine) have a huge impact on performance in the end. One thing that you should try is running the same instance on the same machine (for instance intel i3) on a large number of different random seeds (parameter RandomSeed) to see if there is some variability in the results. We even provide a tool (runseeds) for doing that.

Looking at your model, I noticed that there are many ways to improve the formulation because yours does not exploit enough the scheduling concepts of CP Optimizer and in particular the concept of "optionality" which could avoid many composite constraints in your model. In fact, if I don't mistake, your problem almost looks the same as the one described as introduction to this CP Optimizer tutorial: http://ibm.biz/icaps2017-tut (slides 3-14). A CP Optimizer model formulation for the problem is described on slides 168-176. But it can be interesting for you to go through all the material of this tutorial. There is also an "article" version of the tutorial with similar content that you may find easier to read (http://ibm.biz/Constraints2018), though in the article, the full formulation of this semiconductor problem is omitted.

The bottom line is that you should use "alternative" constraints as soon as, in your scheduling problem, you have anything that is related with the allocation of the activities to some resource/machines. You should use "noOverlap" constraints as soon as you need to model a resource that can perform only one activity at a time. And you should think of "state functions" as soon as you want to model a resource that executes the activities by "batches" (like in your case). In the end, (in general, of course there may be a few exceptions), a good formulation of a scheduling problem in CP Optimizer has a size that grows linearly with the size of the data (no quadratic sets of constraints like: for(i in ...) for(j in ...) overlapLength(itv[i],itv[j])==0) and no need for composite constraints like: presenceOf(x) && presenceOf(y) => ...

Let us know if you have questions regarding the formulation of your particular model.

But please, also send us a .cpo file as it may be that there is also something else in the CP Optimizer engine.

Originally posted by: WeeLoon

Hi Philippe,

Thanks for your advice.

Could you give me a simple example based on my model, how to avoid the following?

a good formulation of a scheduling problem in CP Optimizer has a size that grows linearly with the size of the data (no quadratic sets of constraints like: for(i in ...) for(j in ...) overlapLength(itv[i],itv[j])==0) and no need for composite constraints like: presenceOf(x) && presenceOf(y) => ...

I suspect that my problem is due to the fact that my model grows exponentially with the data.

Thank you. 

Originally posted by: PhilippeLaborie

Did you have a look at the model in the tutorial? Is it a similar scheduling problem you want to solve?

I will only take one example in your model:

forall(e in HTOEqps)
    forall (a_pre in Assignments: a_pre.eqp == e)
      forall (a_post in Assignments: a_post.eqp == e) 
        if (a_pre.task != a_post.task && a_pre.task.recipe != a_post.task.recipe)
          overlapLength(assignment[a_pre], assignment[a_post]) == 0;  

You seem to iterate over all pairs of interval variables that use the same equipment e and are of a different recipe. This way you create a quadratic number of constraints that will be propagated individually and will result in a very weak pruning of the search space. Whereas you could formulate these constraints using a state function. As illustrated in the example of the tutorial.

Originally posted by: WeeLoon

Hi Philippe,

I replaced overlapLength == 0 with stateFunction and the performance increased significantly.

I am trying to improve this composite constraint:

presenceOf(task1) && presenceOf(task2) =>  endOf(task1) + delay >= startOf(task2);

I studied the tutorial you suggested, and I found out that:

endBeforeStart(task1, task2, delay) imply presenceOf(task1) && presenceOf(task2) => endOf(task1) + delay <= startOf(task2);

which is opposite to what I intended to do.

Any idea how to improve the above composite constraint?

Thank you.

Originally posted by: PhilippeLaborie

startBeforeEnd(task2, task1, -delay)