Certains d’entre vous connaissent probablement le jeu Tower Bloxx sur téléphone portable. Pour résumer, le jeu consiste à construire une petite agglomération en plaçant des immeubles sur une grille carrée de taille n x n. Chaque immeuble est créé en empilant un à un les étages à l’aide d’une grue qui balance d’un bout à l’autre de l’écran. A chaque fois qu’un étage est ajouté, des habitants viennent peupler l’immeuble. Plus les étages sont alignés, plus l’immeuble abrite d’habitants et moins l’immeuble balance pour placer de nouveaux étages. Il existe plusieurs types d’immeubles (m), avec un nombre de points et une population croissants : résidentiel (bleu), commercial (rouge), industriel (vert) et hôtel de luxe (jaune). Les règles de placement des immeubles sont les suivantes :

• Un immeuble bleu peut être placé partout.
• Un immeuble rouge doit posséder au moins un immeuble bleu dans son voisinage.
• Un immeuble vert doit posséder au moins un immeuble bleu et rouge dans son voisinage.
• Un immeuble jaune doit posséder au moins un immeuble bleu, rouge et vert dans son voisinage.

On considère ici un voisinage en 4-connexités. Dans le jeu original, il est possible de détruire des tours voisines afin de placer davantage de tours de plus grande importance (loophole). Dans un souci de simplicité, j’ignore ici cette possibilité. L’image ci-dessous donne un exemple d’agglomération qui respecte les règles énoncées précédemment.

Exemple d'agglomération

Outre l’aspect divertissant du jeu, une question plus profonde a rapidement taraudé mon esprit : quelle est la configuration optimale des immeubles qui maximise le nombre d’immeubles de plus grande importance ?

Très vite, on devine que le problème d’optimisation combinatoire sous-jacent posé doit facilement pouvoir s’exprimer sous la forme d’un programme linéaire en nombres entiers (PLNE). Algorithmiquement, la résolution d’un PLNE est autrement plus difficile qu’un PL mais il existe des algorithmes (par exemple branch-and-bound) performants et éprouvés. Ces algorithmes se basent sur la relaxation continue du PLNE (sans les contraintes d’intégrité) et permettent d’éviter une énumération exhaustive des solutions.

Après avoir écrit sur papier la fonction objectif et les contraintes associées, je me suis donc mis en quête d’un solveur gratuit et disponible sous GNU/Linux. Ne connaissant pas en détail les différents solveurs, mon choix s’est porté sur le premier venu : GLPK. Etant novice, l’écriture du programme linéaire m’a demandé quelques refléxions préalables pour généraliser le problème pour un couple de paramètres (n, m) donné.

A partir de ce problème, on peut aussi imaginer diverses extensions :

• Transposer le problème sous la forme d’un graphe et généraliser.
• Généraliser le problème en dimension N : cela implique notamment de définir précisément la notion de voisinage en dimension quelconque.
• Utiliser d’autres règles de dépendances entre immeubles : on pourrait alors imaginer des graphes de dépendance beaucoup plus complexes.
• Utiliser d’autres types de voisinages dans le cas de graphes à « grille ».

Comme bien souvent, la question initiale en appelle plusieurs autres : est-ce que ce problème a déjà été traité dans la littérature (éventuellement présenté sous une autre forme) ? Si oui, quelle est sa complexité pour un m fixé ? Le parallèle sur la coloration de graphes vient presque spontanément. Néanmoins, le problème qui nous occupe est différent et a priori plus simple. On peut tout de même se poser la question pour m=2, m=3 et m>=4. En particulier, il serait intéressant de savoir d’une part, s’il existe un algorithme polynomial pour m=2 et d’autre part, savoir si le problème est NP-Difficile pour m>=4.

D’un point de vue plus technique, cela consiste simplement en un programme linéaire écrit en GMPL pour le solveur GLPK. Les contraintes entre immeubles sont générées à l’aide d’un simple script. Le script écrit le programme linéaire dans un fichier, lance le solveur, affiche les résultats sous la forme d’un tableau et donne le score correspondant.

Finalement, j’ai pu résoudre mon problème initial pour l’instance (n=5, m=4) en une à deux heures de calcul. Il est sûrement possible de diminuer le temps de calcul au niveau de l’algorithme de branch-and-bound, en passant les options adéquates au solveur. Lorsque j’aurai davantage de temps, j’aimerai aussi pouvoir résoudre le même problème avec loophole. Have fun