Un mobile est un arbre binaire dont chaque feuille est associée à un poids. Des exemples concrets peuvent être trouvés dans l'art moderne (Calder) ou au dessus des berceaux et des lits d'enfant.

Pour chaque nœud interne $u$ d'un mobile, on peut définir le déséquilibre de $u$ comme la différence $\delta(u)$ (en valeur absolue) entre la somme des poids des feuilles du sous-arbre gauche de $u$ e la somme des poids des feuilles du sous-arbre droit de $u$.

Le déséquilibre $\Delta(M)$ d'un mobile $M$ est alors la somme des désequilibres de tous ses nœuds. Si $\Delta(M)=0$, le mobile est parfaitement équilibré (comme c'est le cas pour les oeuvres de Calder et pour les mobiles pour distraire les bébés).

Le problème MobilesEquilibrés consiste à détérminer, pour un (multi-)ensemble de poids $p_1, p_2, \ldots, p_n$, le mobile $M$ dont les feuilles portent les poids $p_1, p_2, \ldots, p_n$ (dans un ordre quelconque) et dont les déséquilibre $\Delta(M)$ est le plus petit possible.

Ce problème est, dans un certain sens, la généralsation du problème bien connu qui consiste à déterminer le meilleur parenthesage pour calculer le produit ligne par colonne d'une suite de matrices (resolu polynomialement par programmation dynamique).

Bien que la question sur la complexité du problème reste ouverte (on ne sait pas s'il est NP ou si une solution polynomiale existe), nous présenterons certains algorithmes pour sa résolution, dont certains à complexité polynomiale qui résolvent le problème dans des cas particuliers, ainsi que d'autres ayant complexité exponentielles (dont un basé sur la programmation linéaire à variables entières) et qui résolvent le problème dans tous les cas. Les approches adoptées sont souvent fortément combinatoires.

Travail avec Yacine Hamoudi et Sophie Laplante.