ACTIONS
Un problème juridique ...
Un exemple de programme en AMPL
var b1 binary; var b2 binary; ... var b10 binary;
minimize EX:
b1 + b2 + b3 + b4 + bs + b6 + b7 + b8 + b9 + b10;
subject to
n : b1*b2 + b3*b4 >= 1;
r2 : b5*b6*b7 + b4*b8*b9 >= 1;
r3: b1*b6*b7 + b2*b4*b10 >= 1;
r4: b2*b5*b6*b7 + b1*b4*b8*b9 >= 1;
L'algorithme approché RAND*
Entrées : ensemble de K règles r k contenant q prédicats
distincts P;
nombre de passes N
Sortie : meilleur ensemble de valeurs de vérité P; trouvé
Variables: p_optimal, un tableau de q booléens
x, une variable de type entier
l. Mettre à VRAI toutes les valeurs de p_optimal;
2. Pour compteur allant de 1 à N faire
3. Mettre toutes les valeurs de P; à FAUX
4. Pour k allant de 1 à K faire
5 .
x - une valeur aléatoire comprise entre l
et le nombre de disjonctions dans r k
6 .
Pour j allant de 1 au nombre de prédicats dans la
J!
111
• disjonction de r k faire
7 .
mettre à VRAI la valeur du prédicat P;
correspondant à b k.xj
8.
FinPour
9 . FinPour
10. Si le nombre de prédicats P; mis à VRAI est plus petit que
le nombre de prédicats p_optimal; mis à VRAI, alors
11 .
Pour i allant de 1 à q faire
12.
p_optimal; - P;
13.
FinPour
14. FinSi
15 . FinPour
16. Retourner la liste des p_optimal;
c'est-à-dire teste r to utes les so luti o ns
poss ibles : il y e n a très exacte me nt 2
booléens du problè me. Le coût de cette
mé th ode est do nc haute me nt pro hibiti f.
Une au tre manière de fa ire est d' uti li -
ser un o util de réso luti o n exact de probl è mes d'o ptim isati o n . Le prob lème
do it alors être écrit da ns un langage partic u I ie r : le la ngage A MPL ( la ngage de
modé li sati o n po ur la progra mm ati o n
mathé matique), qui perme t d · exp ri me r
une fo nc ti o n à minimi ser pa r rapport à
un ensemble de vari ables (ic i les prédicats
booléens) et de contra intes (ic i les règles).
U n exe m p le d ' un te l progra m me est
donné en encadré. Les contraintes contienne nt des multipli cati o ns, ce qu i re nd le
p ro bl è m e no n- lin éa ire. Ta nt qu e le
no mbre de variables n'est pas trop important (di sons une centa ine), ce programme
peut être résolu par des logic ie ls comme
Coue nne (po ur Co nvex over and un der
e nve lo pes fo r no n- linea r es tim atio n .
di spo nibl e e n li g ne e t open -source).
Une de rniè re approc he est de pro poser
des a lgorithmes de compl ex ité po lynomiale, et donc fac iles et rapides à calculer,
pe rmettant de trouve r un résultat approc hé de la so luti o n . L'encadré qui suit
do nne l'exemple d ' un a lgorithme a léato ire, no mmé RAND *, très s impl e, qui
pe rme t de ca lcule r une soluti o n acceptable au problè me, e n généra nt a léato ire me nt N solutio ns acceptabl es, pui s en
c ho is issa nt la me ill e ure . To utefo is, la
minima lité de la so luti o n n'est auc un eme nt garantie !
Le lecte ur est in vité à c he rche r d 'autres
a lgorithmes po ur résoudre le problè me
de mani ère approchée, et à comparer, à
te mps de calcul égal, le ur qua lité avec
l' algorithme naïf RAND*. A insi, on voit
que le problè me de limite r la collecte
de do nnées est compliqué, pui sque la
simple identification d' une donnée potenti e ll e me nt util e est un pro bl è me in fo rmatique di ffic il e et coûte ux e n te mps !
N.A.&B. N.
Tangente Hors-série n°52. Mathématiques & informatique
Un problème juridique ...
Un exemple de programme en AMPL
var b1 binary; var b2 binary; ... var b10 binary;
minimize EX:
b1 + b2 + b3 + b4 + bs + b6 + b7 + b8 + b9 + b10;
subject to
n : b1*b2 + b3*b4 >= 1;
r2 : b5*b6*b7 + b4*b8*b9 >= 1;
r3: b1*b6*b7 + b2*b4*b10 >= 1;
r4: b2*b5*b6*b7 + b1*b4*b8*b9 >= 1;
L'algorithme approché RAND*
Entrées : ensemble de K règles r k contenant q prédicats
distincts P;
nombre de passes N
Sortie : meilleur ensemble de valeurs de vérité P; trouvé
Variables: p_optimal, un tableau de q booléens
x, une variable de type entier
l. Mettre à VRAI toutes les valeurs de p_optimal;
2. Pour compteur allant de 1 à N faire
3. Mettre toutes les valeurs de P; à FAUX
4. Pour k allant de 1 à K faire
5 .
x - une valeur aléatoire comprise entre l
et le nombre de disjonctions dans r k
6 .
Pour j allant de 1 au nombre de prédicats dans la
J!
111
• disjonction de r k faire
7 .
mettre à VRAI la valeur du prédicat P;
correspondant à b k.xj
8.
FinPour
9 . FinPour
10. Si le nombre de prédicats P; mis à VRAI est plus petit que
le nombre de prédicats p_optimal; mis à VRAI, alors
11 .
Pour i allant de 1 à q faire
12.
p_optimal; - P;
13.
FinPour
14. FinSi
15 . FinPour
16. Retourner la liste des p_optimal;
c'est-à-dire teste r to utes les so luti o ns
poss ibles : il y e n a très exacte me nt 2
booléens du problè me. Le coût de cette
mé th ode est do nc haute me nt pro hibiti f.
Une au tre manière de fa ire est d' uti li -
ser un o util de réso luti o n exact de probl è mes d'o ptim isati o n . Le prob lème
do it alors être écrit da ns un langage partic u I ie r : le la ngage A MPL ( la ngage de
modé li sati o n po ur la progra mm ati o n
mathé matique), qui perme t d · exp ri me r
une fo nc ti o n à minimi ser pa r rapport à
un ensemble de vari ables (ic i les prédicats
booléens) et de contra intes (ic i les règles).
U n exe m p le d ' un te l progra m me est
donné en encadré. Les contraintes contienne nt des multipli cati o ns, ce qu i re nd le
p ro bl è m e no n- lin éa ire. Ta nt qu e le
no mbre de variables n'est pas trop important (di sons une centa ine), ce programme
peut être résolu par des logic ie ls comme
Coue nne (po ur Co nvex over and un der
e nve lo pes fo r no n- linea r es tim atio n .
di spo nibl e e n li g ne e t open -source).
Une de rniè re approc he est de pro poser
des a lgorithmes de compl ex ité po lynomiale, et donc fac iles et rapides à calculer,
pe rmettant de trouve r un résultat approc hé de la so luti o n . L'encadré qui suit
do nne l'exemple d ' un a lgorithme a léato ire, no mmé RAND *, très s impl e, qui
pe rme t de ca lcule r une soluti o n acceptable au problè me, e n généra nt a léato ire me nt N solutio ns acceptabl es, pui s en
c ho is issa nt la me ill e ure . To utefo is, la
minima lité de la so luti o n n'est auc un eme nt garantie !
Le lecte ur est in vité à c he rche r d 'autres
a lgorithmes po ur résoudre le problè me
de mani ère approchée, et à comparer, à
te mps de calcul égal, le ur qua lité avec
l' algorithme naïf RAND*. A insi, on voit
que le problè me de limite r la collecte
de do nnées est compliqué, pui sque la
simple identification d' une donnée potenti e ll e me nt util e est un pro bl è me in fo rmatique di ffic il e et coûte ux e n te mps !
N.A.&B. N.
Tangente Hors-série n°52. Mathématiques & informatique