[gecode-users] First step in constraint progamming

[Philippe K]

Hello Everybody,

First of all, my apologize if I've posted this message in the wrong place. 
Apologies also for my poor english level.

I just start in constraint programming and I have difficulties getting the 
right approach, the good reasoning, to pose my first problem (both
mathematically and with geocode).

Please, allow me to expose this quite interesting (and fun ?) problem.


Given :
--------

- A set of CPU
- 'Prioritized' tasks  (a priority of 1 is the highest priority)

And knowing that :
-------------------

- A CPU can treat in parallel N tasks
- A CPU can only runs certain tasks

We have to distribute theses N tasks among these CPU such that we maximize 
the number of allocated tasks.A distribution is invalid if there exist an 
allocated task T and an unallocated task T' that have priority.

Example 1 :
-----------

              TASK1               TASK2           MAX // TASKS
Priority        2                   1
---------------------------------------------------------------
CPU1        affectable           affectable        1
---------------------------------------------------------------


CPU1 : { TASK1 }       is an invalid distribution since TASK2 has priority
                       but is not affected.
CPU1 : { TASK1 TASK2 } is an invalid distribution since the max number of 
                       parallel tasks is 1
CPU1 : { TASK2 }       valid distribution
CPU1 : {  }            Means 'no distribution', Not considered since we  
                       have a non empty valid distribution

=> CPU1 : { TASK2 }


Example 2 :
-----------


              TASK1               TASK2        MAX // TASKS
Priority        2                   1
-------------------------------------------------------------
CPU1        affectable           affectable       1
CPU2        not affectable       affectable       2
-------------------------------------------------------------



CPU1: { }            , CPU2: { TASK1 TASK2 }: invalid distribution, Task 1 
                                              not affectable to CPU2
CPU1: { TASK1 }      , CPU2: { TASK2 }      : valid distribution
CPU1: { TASK2 }      , CPU2: { TASK1 }      : invalid distribution, 
                                              Task 1 not affectable to CPU2
CPU1: { TASK1 TASK2 }, CPU2: { }            : invalid distribution, only 1 
                                              tasks affectable to CPU1
CPU1: { }            , CPU2: { }            : Not considered since we have
                                              a non empty valid distribution


Example 3 :
-----------

Now let's take this final example and refine it step by step.


              TASK1           TASK2     MAX // TASKS
Priority        2               1
-----------------------------------------------------
CPU1        affectable       affectable     2
CPU2        affectable       affectable     2
-----------------------------------------------------

CPU1: { }            , CPU2: { TASK1 TASK2 } : valid distribution
CPU1: { TASK1 }      , CPU2: { TASK2 }       : valid distribution
CPU1: { TASK2 }      , CPU2: { TASK1 }       : valid distribution
CPU1: { TASK1 TASK2 }, CPU2: { }             : valid distribution
CPU1: { }            , CPU2: { }             : Not considered since we have
                                               a non empty valid 
                                               distributions.

---------------------------------------------------------------------------
If we have multiple valid distributions, we prefer the one where the
"Task (+ pending task) per CPU" is "well balanced" across CPUs

for instance, with 3 CPU, the 'balance' of a distribution is :

|(nbAffectations(CPU1)+nbPendingTask(CPU1))-
(nbAffectations(CPU2)+nbPendingTask(CPU2))| +

|(nbAffectations(CPU1)+nbPendingTask(CPU1))-
(nbAffectations(CPU3)+nbPendingTask(CPU3))| +

|(nbAffectations(CPU2)+nbPendingTask(CPU2))-
(nbAffectations(CPU3)+nbPendingTask(CPU3))|
---------------------------------------------------------------------------

              TASK1           TASK2     MAX // TASKS NB_PENDING_TASK
Priority        2               1
-----------------------------------------------------------------------
CPU1        affectable       affectable     2               0
CPU2        affectable       affectable     2               0
-----------------------------------------------------------------------

CPU1: { }          , CPU2: { TASK1 TASK2 } : rejected, not the best balance
                                             |0+0 - 2+0| = 2
CPU1: { TASK1 }    , CPU2: { TASK2 }       : best balance|1+0 - 1+0| = 0
CPU1: { TASK2 }    , CPU2: { TASK1 }       : best balance : |1+0 - 1+0| = 0
CPU1: { TASK1 TASK2 }, CPU2: { }           : rejected, not the best balance
                                             |2+0 - 0+0| = 2

----------------------------------------------------------------------------
But since we have more than one potential distribution, we prefer the one 
where the "global affinity" is maximized. The "global affinity" of a 
distribution could be expressed as :

Sum(CPUi) (Sum(Taskj) (isAffected(CPUi,Taskj)*Affinity(CPUi,Taskj)))
----------------------------------------------------------------------------
                   TASK1                       TASK2           MAX // TASKS
Priority             2                          1
----------------------------------------------------------------------------
CPU1        affectable, affinity = 3    affectable, affinity = 1      2
CPU2        affectable, affinity = 2    affectable, affinity = 4      2
----------------------------------------------------------------------------

CPU1: { TASK1 } , CPU2: { TASK2 } : affinity= (1*3 + 0*1) + (0*2 + 1*4) = 7 
CPU1: { TASK2 } , CPU2: { TASK1 } : affinity= (0*3 + 1*1) + (1*2 + 0*4) = 3

Final solution : CPU1 : { TASK1 } , CPU2 : { TASK2 } 
----------------------------------------------------------------------------

To speak honestly, I've absolutely no idea of how to express this problem in 
a 'programming constraint' way. Is this can be expressed using geocode ? 
Any help would be greatly appreciated to prototype this.

Philippe