[gecode-users] First step in constraint progamming

[Christian Schulte]

Hi Philippe,

Unfortunately I cannot really answer your question as this is a general
modeling question and not a dedicated Gecode question.

Best
Christian

--
Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Philippe K
Sent: Saturday, June 15, 2013 10:25 AM
To: users at gecode.org
Subject: [gecode-users] First step in constraint progamming

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







_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users