Originally posted by: 90WP_Grégory_Marlière

Dear all,

I have difficulties to obtain a model which allow a good propapagtion when I use chained optional intervals.

I've made a simple example in order to explain the problem :

 

 

 

- in this graph, the arrows mean "startAtEnd"

- all intervals have a constant duration of 10.

- 4 intervals are optional (dotted in the graph) : they represent 2 alternatives alt1(i1 OR i2)  , alt2(i21 OR i22)

- according to the graph, alt2 is optional

- the startMin of i0 is 100

- the endMax of i4 is 200

- allowed paths are : [i0->i1->i3->i4], [i0->i2->i21->i3->i4], [i0->i2->i22->i3->i4]

 

With the initial propagation, I obtain these domains:

i0[1: 100..IloIntervalMax-20 -- 10 --> 110..IloIntervalMax-10]
i1[0..1: 110..170 -- 10 --> 120..180]
i2[0..1: 110..IloIntervalMax-10 -- 10 --> 120..IloIntervalMax]
i21[0..1: 0..170 -- 10 --> 10..180]
i22[0..1: 0..170 -- 10 --> 10..180]
i3[1: 0..180 -- 10 --> 10..190]
i4[1: 10..190 -- 10 --> 20..200]

 

The expected propagation is:

i0[1: 100..160 -- 10 --> 110..170]
i1[1: 110..170 -- 10 --> 120..180]

i2[1: 110..160 -- 10 --> 120..170]

i21[1: 120..170 -- 10 --> 130..180]

i22[1: 120..170 -- 10 --> 130..180]

 

 

 

i3[1: 120..180 -- 10 --> 130..190]
i4[1: 130..190 -- 10 --> 140..200]

 

 

You can find attached the ".cpo" file which can be replayed with the attached cpp code.

Do you have any idea for improving this model?

 

Regards,

Grégory Marlière

 

 

 

 

 

 

 

 

#CPOptimizer
#DecisionOptimization

Originally posted by: Petr Vilím

Hello,

to make this propagation the precedences must know about the allowed paths. Unfortunately allowedAssignments does not pass this information to the precedences.

CP Optimizer stores all precedence constraints in "time net" and propagate them together. The propagation also takes into account information from "logical network" that stores logical relations between interval variables (implications, logical ORs, equivalence etc). For details see paper "Laborie, Rogerie: Reasoning with Conditional Time Intervals". 

So the first trickery is to abandon allowedAssignments and replace it by logical constraint:

presenceOf(i2) == presenceOf(alt2);

It improves the propagation quite a lot but still startMin of i3 is not good. The reason is that CP Optimizer doesn't see that either i1 or alt2 will be present and therefore at least on of the precedences will be active. To add the missing propagation we can create additional technical interval variable "i3pre" and alternative constraint:

i3pre = intervalVar();
alternative(i3pre, [i1, alt2]);
startAtEnd(i3, i3pre);

And then we can remove the following precedences:

startAtEnd(i3,i1,0);
startAtEnd(i3, alt2,0);

The trick is that alternative constraint will compute correct endMin of i3pre that will be propagated on i3.

It is a very interesting example that shows how the propagation works! And nice picture.

 

Best regards, Petr

#CPOptimizer
#DecisionOptimization

Originally posted by: 90WP_Grégory_Marlière

Thank you very much, that help a lot my understanding of the problem.

For my real case study, the third parameter of startAtEnd is not constant ( z ==  distance end(b)-start(a) ) : 

In this case, we cannot group as it is done before.

 

So I've haded this difficulty to my previous example, with some values of z indicated near the arrows:

 

You can find attached: 

- model_minimal_brut.cpo, the model without any extra constraints and with a really bad propagation

- model_minimal_pres.cpo, my try for improving the propagation. If there is a choice before or after a node:

   - create an alternative group with all the choices and put an extra constraint: endBeforeStart with this alternative and with z= -  max z of the intervals alternatives.

   - if the node presence is optionnal, also add:  presenceOf(alternative group) == presenceOf(node).

 

Solving to optimality with these 2 variants (full logs attached) :

	model_minimal_brut	model_minimal_pres
Variables	7	10
Constraints	9	16
Best Objective	137	137
Best bound	19	135
Number of branches	10	6
Number of fails	6	3
Search speed	1000	600

 

I think it's not the best way because the propagation is improved, but not optimal and we need to add a lot of constraints and variables,

so if you have any idea...

Thank you very much,
Grégory

 

#DecisionOptimization

Originally posted by: Petr Vilím

Hello,

I attach a .cpo file with a model that should have a complete propagation. There are 6 additional interval variables, but maybe some of the original intervals could be eliminated now from the model (depending how they are used outside of this example).

The main idea is to model by an interval variable a "cover" that includes the delays (the length of the precedences) before and after the interval. Note that in your model the delays are negative (e.g. i1 starts 1 time unit before i0 ends). So I kept it this way in my model.

Using those cover intervals it is possible to create alternative constraints that also takes into account the length of the precedences. For example when we choose between i21 and i22 we actually choose from paths of length 10-1-2=7 through i21 or length 10-2-3=5 through i22. So the alternative constraint is on top of cover intervals with lengths 5 and 7 instead on original i21 and i22 intervals that have both length 10.

Note also that search type DepthFirst is not particularly smart. It creates the schedule chronologically always preferring an interval that could start first. So it chooses i2 because i2 can start at 8 (and i1 at 9). Therefore the first solution found by DepthFirst will be suboptimal. If you keep the default search then it goes directly to the optimal solution in this case. There are still some number of fails, but those are rather technical fails that ends certain internal strategies.

Best regards, Petr

#CPOptimizer
#DecisionOptimization