Turbo Selector

Pendant mon alternance, un collègue développait une application de composition d’équipes pour Sorare, un jeu de fantasy basé sur de vrais joueurs NBA. Son back-end PHP mettait plus de trois secondes à trouver la meilleure équipe, et je lui ai proposé de faire mieux.

C’est une API FastAPI en Python, typée avec Pydantic, qui s’appuie sur PuLP et le solveur CBC. Elle tourne dans une image Docker multi-étapes, avec un utilisateur non root, un healthcheck et quatre workers, derrière nginx avec des limites de CPU et de mémoire. Chaque version est taguée et chaque ticket a sa branche.

L’API reçoit les joueurs de l’utilisateur avec leur coût, leur score et leur statut d’« étoile ». Elle construit un programme linéaire en variables binaires qui maximise le score total en respectant le budget, le nombre de joueurs, un minimum d’étoiles et les joueurs que l’utilisateur veut absolument garder.

Pour renvoyer plusieurs compositions, elle relance le calcul en interdisant à chaque fois les solutions déjà trouvées. Pour ça, elle ajoute une contrainte qui oblige la nouvelle équipe à différer d’au moins un joueur de chaque équipe précédente.

Tout tenait dans la règle du MVP. Le joueur le plus cher de l’équipe ne compte pas dans le budget, et « le plus cher » n’est pas une contrainte linéaire. Je l’ai donc modélisé autrement. Une variable binaire désigne le joueur offert, qui doit faire partie de l’équipe et coûter au moins autant que n’importe quel autre joueur retenu. Son coût est ensuite retiré du budget.

Mes premières heuristiques tournaient en 60 ms en local, mais dépassaient deux secondes une fois toutes les règles ajoutées. La programmation linéaire a réglé le problème, avec en plus la garantie d’obtenir le meilleur résultat possible.

J’ai appris à reconnaître un problème d’optimisation et à le modéliser proprement au lieu de tâtonner. Mon collègue l’a testé une semaine en production, avec moins de 500 ms pour 8 équipes, quatre fois moins de CPU et 20 % de mémoire en moins sous forte charge.