About soft conflicts

Started by Liviu Lalescu, April 04, 2008, 05:46:46 PM

Previous topic - Next topic

0 Members and 2 Guests are viewing this topic.

Liviu Lalescu

QuoteOne more thing....I've notice that If you generated new time table.... some results had soft conflicts in it. Maybe after couple of times regenerate the time table.... FINALLY it shows 0 soft conflicts.... It means that FET can make no soft conflicts if u try many times... I'm just wondering, but why don't FET shows only the result for 0 soft conflicts. Maybe FET can optionally shows result that have some soft conflicts in it... Any suggestions??

There is a little misunderstanding here: each time you generate, you start a new process, not depending on the previous process. It is by chance that you obtain 0 or more conflicts. FET just generates a timetable  satisfying the 100% constraints and satisfying about 95% of constraints with weight 95% and so on. FET adjusts to the weights, meaning that if a constraint has weight 99% and it can only be respected in about 90% of cases, FET might obtain a solution, respecting 90% the constraint.

If you want a timetable with 0 soft conflicts, you either generate more times and choose a 0 soft conflicts timetable (if you get any, by chance), or you make all constraints have weight 100% (as a particular case, you can see that you can modify all weights of constraints min n days between activities by a simple click).

kdsayang

Quote
There is a little misunderstanding here: each time you generate, you start a new process, not depending on the previous process

Yes... that part I understand. But wouldn't it better if FET can generate only 0 soft conflicts?? I have a suggestion. Maybe FET can be instructed to generate the time table UNTIL it can generate output of 0 soft conflicts in a certain amount of time like in the "generate multiple variants".... If it fail.... then we know that it is impossibly to achieve 0 soft conflicts.... Maybe after that FET can be instructed to find the remaining weight soft conflicts... For example below 3.0, below 1.5 etc.... Lower the weight figure, lower the soft conflicts in the time table right???  just a suggestion....

u know the best... tq

Volker Dirr

Problem:
- There are so many constraints and FET doen't know what constraint should be reduced first. FET can't never know your preference.
- It may much to long to solve the 100% timetable. Maybe it take 1 day. Maybe 10, Maybe 100. I never tested the new algorithm with more then 1 day, because i cancel it.

I recommend to:
Add constraints step by step with 100%.
Each time you added a new 100% constraint you can try to solve the timetable.
If FET is still able to solve, add the next constraint.
IF FET can't solve anymore, then you know it is not possible and you can maybe add constraint with less then 100%.



Liviu Lalescu

Quote
Yes... that part I understand. But wouldn't it better if FET can generate only 0 soft conflicts?? I have a suggestion. Maybe FET can be instructed to generate the time table UNTIL it can generate output of 0 soft conflicts in a certain amount of time like in the "generate multiple variants".... If it fail.... then we know that it is impossibly to achieve 0 soft conflicts.... Maybe after that FET can be instructed to find the remaining weight soft conflicts... For example below 3.0, below 1.5 etc.... Lower the weight figure, lower the soft conflicts in the time table right???  just a suggestion....

u know the best... tq

Of course you are right, but only theoretically. There are timetables where generation takes hours. And there are timetables with ~50 soft conflicts.

The best method is to generate, then strengthen one or more constraints, then try again, then again raise the weights to some constraints, until impossible to generate a new timetable, then go back one step.

The FET algorithm does not permit better approaches. I know another timetabling tool which has no weight for constraints, but I do not know how do they do it.

kdsayang

Quote
The best method is to generate, then strengthen one or more constraints, then try again, then again raise the weights to some constraints, until impossible to generate a new timetable, then go back one step.

Yes.... u can try to change this and that. But the way I see is like this, FET generate randomly according to the constraints right? For the first run , let say u got 3.0 soft conflicts and u made some adjusments. On the 2nd run, it changes everything because FET generate randomly...

What I'm trying to say that becoz of FET generate randomly, sometimes the change we made before that doesn't change the output/outcome... Isn't it???


Quote
I know another timetabling tool which has no weight for constraints

which one?? do you have their name and website?

Quote
but I do not know how do they do it.

just ask them... hehe  ;D


Liviu Lalescu

#5
QuoteYes.... u can try to change this and that. But the way I see is like this, FET generate randomly according to the constraints right? For the first run , let say u got 3.0 soft conflicts and u made some adjusments. On the 2nd run, it changes everything because FET generate randomly...

What I'm trying to say that becoz of FET generate randomly, sometimes the change we made before that doesn't change the output/outcome... Isn't it???

I am sorry, but I do not understand. If you raise the weights, then probably the timetable will have less conflicts, but not always. But you can generate again.

Quote
Quote
I know another timetabling tool which has no weight for constraints

which one?? do you have their name and website?


I have heard of aSc Timetables, please Google for it. I am not sure whether I am allowed to talk about them. Also, many others might permit automatic adjustment of weights like that.

Quote
Quote
but I do not know how do they do it.

just ask them... hehe  ;D


It is proprietary closed software, expensive.

kdsayang

Quote

I am sorry, but I do not understand. If you raise the weights, then probably the timetable will have less conflicts, but not always. But you can generate again.

I would like to see FET generate the time table in

1. certain amount of time for each time table
2. with some setting about the remaining weight soft conflicts
3. generate multiple variants

For example
(A) rules are
(i) the user select to generate 10 minutes time limit for each time table
(ii) user set 0 for remaining weight soft conflicts
(iii) the user select 10 variants

the outcome
(B)
(i) the time table finished and it has generate 10 time table that concur with 0 remaining soft conflicts for each time table
(ii) the time table finish and it only manage to get 5 variants from 0 remaining weight soft conflicts
(iii) the time table finish BUT it don't manage to generate any variants with 0 remaining weight soft conflicts

refer to (B)(iii)

the user can change
(i) longer run time to generate time table (with crossing finger) hehe... Others setting is not change
(ii) longer run time to generate time table with increasing value for remaining soft conflicts (0.5, 1.0, 1.5 etc)

As u can see in timetable --> generate multiple variants, features in (A)(i) and (A)(iii) are already there. I hope that u

can figure it out on how to implement the feature in (A)(ii). It would be marvelous.

TQ



Liviu Lalescu

#7
I added that in the TODO, but I am not sure if a solution exists.

Edit: it is impossible. FET cannot generate a solution with maximum say 2 (or 10) soft conflicts. The solution is generated gradually and it is impossible for the algorithm to do that. If it were a way, I would have done it a long time ago.

kdsayang

QuoteI added that in the TODO, but I am not sure if a solution exists.

Edit: it is impossible. FET cannot generate a solution with maximum say 2 (or 10) soft conflicts. The solution is generated gradually and it is impossible for the algorithm to do that. If it were a way, I would have done it a long time ago.

no worries mate.... hehe

just read the mail that I send to u....

Volker Dirr

#9
Quote(ii) longer run time to generate time table with increasing value for remaining soft conflicts (0.5, 1.0, 1.5 etc)

I think that is not a good idea.
Reason:
A user might increase the value for remaining soft conflicts and he might be unhappy about the results (if he ever get it. Think about a user that add low weights and low remaining soft conflicts, that guys will NEVER get a solution, because it will restart every few minutes without a result.)
The problem is, that a user might not understand, that he can increase the weight to get a perfect timetable.
So users that don't understand this mixed weight and value for remaining soft conflicts will get bad or even no timetable.

Only the value for remaining soft conflicts (without weight) is bad, because a user can't affect single constraints anymore.

kdsayang

Quote

I think that is not a good idea.
Reason:
A user might increase the value for remaining soft conflicts and he might be unhappy about the results (if he ever get it. Think about a user that add low weights and low remaining soft conflicts, that guys will NEVER get a solution, because it will restart every few minutes without a result.)
The problem is, that a user might not understand, that he can increase the weight to get a perfect timetable.
So users that don't understand this mixed weight and value for remaining soft conflicts will get bad or even no timetable.

Only the value for remaining soft conflicts (without weight) is bad, because a user can't affect single constraints anymore.

I think I got your point.... Just ignore this suggestion tooo....hehe