Originally posted by: DeFersen

Hi,

I'm working on the University Course Tabling Problem and i have made a model which has 5 differents objectives (as i mentionned it in previous topic).

I have tried some types of agregation and the lexicographic order gave me really good results. So i have a question about the search method of this approach :

I tried to solve 5 successives mono-objective versions of my model (one for each objectives) using starting point and adding every time a new constraint stating that the previous objectives could'nt be degraded. I have executed each of them on the same duration than one in lexicographic order but at the end, this latter find me better solution that the one i got with this 'mono objective' strategy.

So could you give me some information about the search method of the lexicographic order (because i don't think it the same method than the strategy i explained) ?

More over, i would like to try different way of weighted sum (with normalized score) and i gave me really worse results than the lexicographic order (i can compare it by calculating the same weighted sum for the resultat that the lexicographic order give me).

Howewer, I tried to stop solving when it seemed that a limit were reached and i saved the solution. After using this one in the same model (the weighted sum) using a starting point, the score was quickly improved and this "limit' was overpassed. Can you explain me this phenomenon ? Is this way near that what you call Multi Point ?

Thanks,

DeFersen.

Originally posted by: PhilippeLaborie

I tried to solve 5 successives mono-objective versions of my model (one for each objectives) using starting point and adding every time a new constraint stating that the previous objectives could'nt be degraded. I have executed each of them on the same duration than one in lexicographic order but at the end, this latter find me better solution that the one i got with this 'mono objective' strategy.

You say that if you run the lexico objective with a time-limit T, in your goal programming approach, you run each iteration with a time limit T, so resulting of a total solve time of n.T, and that the results are worse than the lexico objective? This is a bit surprising and I think that in order to draw a conclusion, you should run it on several instances of problem and/or on several random seeds. 

So could you give me some information about the search method of the lexicographic order (because i don't think it the same method than the strategy i explained) ?

A possible explanation could be that some of the criterions are positively interfering (improving one may tend to improving the other) and that because the lexico search handles all objectives at the same time, it exploits very early the fact that, a criterion j>i (j less prioritary than i) can be more easily improved than i but helps improving i. Indeed in the goal programming approach, when you optimize on j, it may also improve i but you will not keep these improvements.

More over, i would like to try different way of weighted sum (with normalized score) and i gave me really worse results than the lexicographic order (i can compare it by calculating the same weighted sum for the resultat that the lexicographic order give me).

Yes, this is quite common. In case of lexico objective (so when you have very different coefficients in the sum), it is often better to avoid the weighted sum and keep the objective separated (in lexico objective or by doing some goal programming and working sequentially on the objectives). One reason is that the weighted sum does not propagate well in CP.

Howewer, I tried to stop solving when it seemed that a limit were reached and i saved the solution. After using this one in the same model (the weighted sum) using a starting point, the score was quickly improved and this "limit' was overpassed. Can you explain me this phenomenon ? Is this way near that what you call Multi Point ?

Yes this is a bit surprising. Could you send us the 2 models (exported .cpo file): the initial one without starting point that seems to get stuck at some point, and the second one with the solution as starting point? 

No it is not what the MultiPoint search is about. The MultiPoint search is a Genetic Algorithm that evolves a population of solutions.

Originally posted by: DeFersen

Hi,

Thanks for this answer.

so resulting of a total solve time of n.T, and that the results are worse than the lexico objective? Exactly.

A possible explanation could be that some of the criterions are positively interfering (improving one may tend to improving the other). It is exactly the case so i have my answer !

One reason is that the weighted sum does not propagate well in CP. Understood.

Could you send us the 2 models (exported .cpo file): the initial one without starting point that seems to get stuck at some point, and the second one with the solution as starting point?

Ok. I give you the 2 cpo.file of both model, the first one trying to minimize the weight sum on 2 hours (and reaching a score between 45 and 48 on my computer), the second one taking the solution given by the precedent execution as a starting point and quickly improving the score to reach a final score of 29 after 2 hours. I hope that i have made no mistakes on both file.

The MultiPoint search is a Genetic Algorithm that evolves a population of solutions. Ok. I have also tried it on the lexicographic order but it didn't gave better results than the normal one. Maybe it can improve the score i obtain on the weighted sum ?

Regards,

DeFersen.

Originally posted by: PhilippeLaborie

I think that the 2 models are the same. Make sure that you call exportModel after setting the starting point, just before the call to cp.solve().

You can also use the ILC_MODEL_DUMP_FILE environment variable for this. Set this variable to a name of a file with extension .cpo (including path if you want). When CP Optimizer solves a problem and the variable is set then it dumps the model into the file before the solve starts.

Originally posted by: DeFersen

Hi,

Ok. Is it better like this ?

Thanks,

DeFersen.

Originally posted by: PhilippeLaborie

It seems that the search phase plays against the automatic search here and is counterproductive. If you just remove the search phase and let the fully automatic search run, it quickly finds a solution with a cost less than 21.

Philippe

Originally posted by: DeFersen

Hi,

Thanks. it effectively find a really much better solution in a shorter period of time. Could i ask you some last questions about that because i have to present my results and so to explain this phenomenon :

1. In my search phase, i have just introduced a value selector (which is important for the quality of the solution, as i mentionned it in another topic) and Random Variable selector (because i have a priori no requirement about this but i think i have to create a variable selector to respect the cp.searchPhrase(...) signature). So, Is the value selector causing trouble or this random variable selector ?
2. How the Random Variable Selector works if i have fixed a Random Seed thanks to the random Seed Parameter ? Is the random Selector is based on the order planned by the random Seed or not ?
3. Finally, if i have no Random Seed, how the variable are selected step by step ? Is there a dynamic way to choose them or is a random order is fixed before solving, as the Random Seed do it ?

Regards,

DeFersen.

Originally posted by: Philippe_Refalo

It's difficult to determine precisely what can cause the problem in your phase. The point is that, having only a phase on "cours" variables make the search start by those ones and they have a larger domain than the others. In general, it's important to start with variables having the smallest domain first and this is probably the case for this model. 

At each node of the search tree, the random variable selection simply pick an uninstantiated variable randomly chosen in the variable array of the phase and uses for that the actual random seed. This always uses a random seed and it is set to 0 by default. 

Originally posted by: DeFersen

Thank you very much. I think that i'm now able to explain my results.

DeFersen.

PS : Just for my curiosity, do you have an idea of the reason why using starting point worked as well (improving quickly the solution), even with my search phase ?

Originally posted by: Philippe_Refalo

I don't have any clear explanation for now. It's weird and we are investigating. 

Philippe

Originally posted by: Philippe_Refalo

For our knowledge and if you have time to test this : if you remove the phase, what model converges more rapidly ? The model with the multi-objective function or the one with objectives aggregated to a single one with weights ?  

Thanks.

Philippe

Originally posted by: DeFersen

Ok. After 2 hours of solving (without search phase), i obtain a score of 20,6 with the normalized weight sum while i obtain 21,6 (on the indicator of the same weighted sum, which is not the objective function) with a lexicographic order that works well (relatively to my observations).

Note that this last agreggation respect an order of the objective so the solution that it give me has nothing to see with the one the weighted sum regarding to other indicators (for example the sum of penalities of the five score that i put in the lexicographic order). However, when i use solving with search phase, lexicographic order always give me better solution for all indicators (even the weighted sum).

Could it be effectively a problem with the value selector that i introduced in my search phase which provoke "ties" (as you mentionned it in the manual) with the weighted sum aggregation ?

DeFersen.