Le shape nesting est un problème d'optimisation combinatoire complexe que l'on retrouve couramment dans l'industrie manufacturière. Cela consiste à trouver l'agencement optimal de formes 2D quelconques lors d'usinage, pour rentabiliser chaque centimètre carré de matière brute.

L'espace des solutions possibles est souvent trop grand pour être explorer en un temps raisonnable. La rapidité de l'algorithme et du code ainsi que la stratégie d'exploration sont donc deux critères essentiels de réussite.

Réalisations :

• développement d'un algorithme comparable aux solutions commerciales disponibles

• Optimisation du code d'un facteur 100 entre la première itération et la dernière. Aujourd'hui des étapes aussi simple qu'une condition "if x > n" ont un impact significatif sur la vitesse d'exécution

Optimisations mises en place avec succès :

• caching de résultats intermédiaires

• utilisation d'integer plutôt que de float (+ rapide, + stable numériquement)

• utilisation de librairies externes uniquement codées en C et réputées stables et rapides

• profiling du code ligne à ligne

• refactoring permanent pour garder le code minimal et éviter les opérations superflues et/ou redondantes.

• emploi des types et fonctions built-in pour éviter des conversions vers et depuis des types de données externes

• comparaison de plusieurs approches, notamment pour la stratégie d'exploration (Algo génétique, heuristiques, Monte carlo tree search, ...)