Parcours optimal de n-uplets

Jean-Armand Moroni

Bonjour
Voici un problème d'optimisation, qui revient dans différents cas pratiques (application : cf. plus bas). J'espère être dans le bon forum.

On se place dans l'ensemble des $n$-uplets de booléens (ou des sommets d'un hypercube à $n$ dimensions si vous préférez), notés $(a_i)_{i=1..n}$.
Soit $p < 2^n$. On souhaite choisir $p$ éléments de cet ensemble, de façon à optimiser $\sum_{i=1}^n c_i d_i$,
où $c_i$ est une suite décroissante de poids (réels positifs), et $d_i$ est la somme des nombres de valeurs différentes prises par chaque $i$-uplet de $a_j$ dans les $n$-uplets choisis.
Comment choisit-on les $n$-uplets ? Dans quelle mesure ce choix optimal dépend-il des $a_i$ ? Au cas où on ne connaît pas $p$ à l'avance, peut-on construire une suite de $n$-uplets qui soit constamment optimale, ou au moins "pas trop mauvaise" ?

Exemple avec $n = 3$ et $p = 4$ :
On choisit $(0,0,1), (1,0,0), (1,0,1), (1,1,0)$, ça donne
$d_1 = 6$ : $a_1$, $a_2$, $a_3$ prennent chacun les deux valeurs 0 et 1
$d_2 = 9$ : on a 9 couples de $a_i a_{j\neq i}$ sur les 12 possibles : $(0,0,-), (1,0,-), (1,1,-), (0,-,1), (1, -, 0), (1, -, 1), (-, 0,0), (-,0,1), (-,1,0)$.
$d_3 = p = 4$.

Application : on teste un logiciel. On suppose que le fonctionnement du logiciel dépend de $n$ booléens (configuration des modules optionnels, flags de compilation...). On peut effectuer $p$ tests. On souhaite les répartir de manière à maximiser la probabilité de détecter un bug. On suppose que le comportement du logiciel dépend principalement (coeff $a_1$) de chaque booléen, un peu moins de leurs combinaisons 2 à 2 (coeff $a_2$ inférieur à $a_1$), encore moins de leurs combinaisons 3 à 3 (coeff $a_3$ inférieur à $a_2$), etc.

J'ai aussi une autre application en tête, un peu longue à expliquer.
Je pourrai vous dire dans un prochain message comment je choisis les $n$-uplets, mais vous ne perdez rien, ça ne repose sur rien de rigoureux. :-)

rosab

Bonjour,

C'est le vaste domaine des "plans d'expérience" : https://fr.wikipedia.org/wiki/Plan_d'expériences
S'il n'y a pas d'interactions entre tes facteurs, tu peux penser aux matrices de Hadamard.

Jean-Armand Moroni

Merci !
Je ne connaissais pas l'expression "plans d'expérience", et donc je ne trouvais pas de référence.
Avec l'article Wikipedia et tout ce vers quoi il pointe, j'ai de la lecture. Parfait !