FET generation algorithm - "recursive swapping"

[Benahmed Abdelkrim]

You are right.

I take care when computing the initial order of time and space constraints both.

Yes, the initial order has a very important impact on the good performance, and also on the speed of production.
Can we know how the algorithm calculates the initial order?

How do you know the algorithm that certain activities are difficult and ranked in the first order?
Is there an equation that helps to calculate the initial order?

I think this point needs to be lit up to better understand it

In some complex tables I make a simple change in the initial order, which improves program performance in terms of output speed. I think this is interesting! and It needs a deep interpretation.

[Volker Dirr]

you can read that in engine/generate_pre.cpp. Have a look at "sortActivities".

in fact there are 2 things:
a) number of free time slots. if the activity has got only a low number of free slots, than it must be first
b) number of conflicts to other activities. if an activity can't be placed with many ohter activities at the same time, than it must be first

currently it is a mix of a) and b). Sometimes a) is more highly needed but sometimes b) is highly needed.

you are right: the algorithm isn't always the best in that part. i noticed myself that a) is sometimes undervalued and i set it many first. but it is difficult to give a nice rule for this.

improving this is not just coding it. you need to check that with a lot of different datasets/constraints a lot of different times.
so i guess this is a work that need to least several weeks of testing to check if it is better or not than the current variant.

[xing]

In step 2 g) We have now 3 - 1 = 2 more activities to place...should it be 4-1=3 more activities to place in your example? You placed A_i to T_j, then 3 activities A_p, A_q, A_r will be unallocated and need to be placed latter.

[Liviu Lalescu]

Hmm, indeed! 

I wonder why nobody else found this bug until now.

I will correct for the next FET version and on the FET homepage.

[Liviu Lalescu]

No. It is correct 3-1=2, because I am referring to the difference between the initial state and the next state.

Here is an example: A1, A2, A3, A4, A5 placed, A6 to be placed (A6 is unallocated). Say A6 is placed and displaces A1, A3, and A4. Then these are placed: A2, A5, and A6, and unallocated: A1, A3, and A4. So there are 3 - 1 = 2 more activities to be placed compared to the initial situation.

[xing]

You are right, there are 2 more activities to be placed compared to the initial state. There are 3 activities need to be placed. I have got other questions about the generate.cpp. What are the functions of the following variables used in randomSwap:
1.swappedActivities.
Does swappedActivities[ai]=true mean activity ai has been allocated? If it does, "swappedActivities[permutation[added_act]]=true" in generate.cpp line 3007 (version-5.37.5) means that permutation[added_act] is allocated, but to my understanding, this activity has not been allocated to any time yet until this statement.

2.triedRemovals.
Does triedRemovals(i,j) mean how many times activity i has been allocated in timeslot j? What does this variable do in the randomSwap()?

Thanks a lot.

[Liviu Lalescu]

1. It means that the activity was already tried to be placed in another slot. If an activity is swapped, it cannot be displaced anymore (to try to avoid a kind of cycling). The activity permutation[added_act] cannot be placed and then displaced. Before randomSwap(permutation[added_act], 0) all activities are not swapped, without permutation[added_act], which is swapped. Then if in the recursive calls we displace some activities and place them in another slot, in the continuation of the recursive calls, with a greater level, the swapped activities cannot be displaced anymore. If we get back from this level, swappedActivities[a_p] becomes false again (I think in line 10286).

2. triedRemovals(i, j), if I remember correctly, means the number of times we deallocated activity i from slot j at level 0 in the last tabu_size = nInternalActivities*gt.rules.nHoursPerWeek. We will prefer the smallest number triedRemovals when choosing in which slot to place A_i at level 0 (step (2 g) ), to avoid cycling.