Originally posted by: stevedwards

Hi team,

Just had a reasonably general question about how a search phase over a sequence variable works.

I see in the docs here that if a search phase is specified over a sequence variable then search aims to find a totally ordered sequence of present interval variables. Can you tell me more about how the search works? Does it mimic the search over interval variables where in general intervals are scheduled (or in this case sequenced) based on earliest start and end times? Do the initial heuristics take connect components into account? Or is it more of an arbitrary search?

Also how would you best ensure that the first variable in the sequence starts at time 0? The problem I am working on is similar to the job shop problem with time lags. I have a lot of negative time lags so if I can force the first activity in the sequence to start at the beginning this will constrain my problem much better - however there doesn't seem to be a natural way to constrain this. Currently searching over the specific intervals is much better than the sequence but I was just interested to see whether I could improve the search over the sequence if I understood it a bit better.

Thanks in advance,

Steven

Originally posted by: PhilippeLaborie

Hi Steven

> Can you tell me more about how the search works? 

> Does it mimic the search over interval variables where in general intervals are scheduled (or in this case sequenced) based on earliest start and end times? 

> Do the initial heuristics take connect components into account? Or is it more of an arbitrary search?

Search phases over sequence variables will fix the sequence variables in the phase one by one. Fixing a sequence variable means deciding the order of the intervals in the sequence (but not deciding the start/end value of the interval variables; this type of decision is done later on, when the interval variables are fixed). For fixing the ordering of a sequence variable, the search phase selects the interval variables (typically based on earliest start/end times) and tries to schedule them on the head of the sequence that is currently being built (so the sequence is built chronologically); in case of backtrack, another interval is selected.

The initial heuristics indirectly take connected components into account through the start/end max of interval variables but this is used for fixing the interval start/end values, not for fixing the sequence variables (ordering) in case of search phases on sequence variables.

> Also how would you best ensure that the first variable in the sequence starts at time 0?

> The problem I am working on is similar to the job shop problem with time lags. I have a lot of negative time lags so if I can force the first activity in the sequence to start at the beginning this will constrain my problem much better - however there doesn't seem to be a natural way to constrain this. Currently searching over the specific intervals is much better than the sequence but I was just interested to see whether I could improve the search over the sequence if I understood it a bit better.

You could create a dummy interval variable O that is fixed (e.g. length=0, start end finishes at 0) and used in your sequences and post constraints like startOfNext(seq,O,0)==0. Though, CP Optimizer will naturally tend to fix the interval variables at their smallest value so I'm not sure this is really necessary; maybe it can reduce the search space for optimality proofs …