Mixed-Integer Programming

Aussi appelé: MIP, MILP, MIQP, MICP
Catégorie: Planning & manipulation › Trajectory optimisation
Mots-clés: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

Optimisation dans laquelle certaines variables doivent prendre des valeurs entières, souvent 0 ou 1, ce qui permet à un même problème de combiner des choix discrets et des grandeurs continues.

Définition

Programmation en nombres entiers mixtes (mixed-integer programming, MIP) : optimisation portant sur un mélange de variables continues et de variables restreintes à des entiers, le plus souvent des variables binaires qui prennent la valeur 0 ou 1. Les variables binaires encodent des décisions discrètes : quelle région un chemin traverse, quel pied se pose ensuite, si un contact est actif, quel robot prend quelle tâche. Les variables continues portent le reste, comme les positions, les vitesses et les forces. Les classes courantes sont nommées d'après la forme du problème restant : programmes linéaires en nombres entiers mixtes (MILP), programmes quadratiques en nombres entiers mixtes (MIQP) et, plus généralement, programmes convexes en nombres entiers mixtes (MICP).

Ces problèmes sont NP-difficiles en général, mais les solveurs modernes traitent bien de nombreuses instances pratiques. Ils utilisent la séparation et évaluation (branch and bound) : résoudre la relaxation continue en abandonnant les exigences d'intégralité, choisir une variable qui est sortie fractionnaire, séparer en deux sous-problèmes qui la forcent vers le bas ou vers le haut, et élaguer toute branche dont la relaxation est déjà moins bonne que la meilleure solution entière trouvée. Des plans de coupe resserrent la relaxation en cours de route. Des solveurs commerciaux comme Gurobi et CPLEX et des solveurs libres comme SCIP, HiGHS et CBC mettent en œuvre ces méthodes.

La manière d'écrire un problème compte autant que le choix du solveur. Les conditions logiques sont souvent encodées par des contraintes big-M (big-M constraints), qui activent ou désactivent une contrainte à l'aide d'une variable binaire et d'une grande constante ; une constante trop grande affaiblit la relaxation et cause des problèmes numériques. Les formulations à relaxation serrée se résolvent beaucoup plus vite, ce qui est l'une des raisons pour lesquelles des approches structurées comme les graphes d'ensembles convexes sont conçues pour que leur relaxation soit proche du vrai problème.

Pourquoi c'est important

De nombreux problèmes de planification robotique sont en partie discrets : passer à gauche ou à droite d'un obstacle, choisir une séquence de contacts, attribuer des tâches. La programmation en nombres entiers mixtes traite ces choix exactement au sein d'une seule optimisation, souvent avec une borne sur l'écart entre la réponse et l'optimum, au lieu de s'appuyer sur des heuristiques faites à la main ou sur l'échantillonnage.

Applications principales

Planification des appuis et des séquences de contact pour les robots à pattes
Planification de trajectoires à travers des régions convexes pour drones et bras
Attribution de tâches et ordonnancement pour flottes de robots
Commande prédictive hybride avec modes discrets
Planification de tâches et de mouvements avec choix d'actions discrets

En pratique

Une équipe qui planifie les pas d'un humanoïde sur des pierres de gué représente la surface praticable de chaque pierre par un polygone convexe. Pour chacun des prochains pas, elle ajoute des variables binaires qui choisissent le polygone sur lequel le pied se pose, avec des contraintes actives uniquement pour le polygone choisi, plus des variables continues pour les positions des pieds et des limites sur la longueur des pas et la rotation. Le coût récompense la progression vers le but et pénalise les pas maladroits. Un solveur en nombres entiers mixtes renvoie une séquence de pas, généralement dans une limite de temps fixée pour la replanification, ainsi que l'écart entre la meilleure solution trouvée et la meilleure borne. Si les temps de résolution sont trop longs, l'équipe réduit le nombre de pas planifiés à la fois, resserre les valeurs de big-M ou démarre à chaud à partir du plan précédent.

Idées reçues

Les programmes en nombres entiers mixtes sont toujours trop lents pour la robotique — des problèmes petits et bien formulés peuvent se résoudre assez vite pour la replanification en ligne
Arrondir la relaxation continue donne la solution entière optimale — l'arrondi peut être infaisable ou loin de l'optimum si la relaxation n'est pas serrée
N'importe quelle grande valeur de M convient dans les contraintes big-M — des valeurs excessives affaiblissent la relaxation et causent des difficultés numériques
Un solveur qui s'arrête à sa limite de temps a échoué — il renvoie généralement la meilleure solution trouvée jusque-là et un écart d'optimalité qui indique sa qualité

Qui devrait le savoir

Ingénieurs en planification de mouvement et d'appuis
Développeurs d'ordonnancement de flottes et d'attribution de tâches
Chercheurs en commande fondée sur l'optimisation
Étudiants en robotique qui étudient l'optimisation

Technologies associées

Séparation et évaluation (Branch and Bound)
Gurobi
SCIP
HiGHS
Programmation linéaire (Linear Programming)
Optimisation convexe (Convex Optimization)

Termes associés

Projets associés

Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
GTSAM: Factor-graph optimization library powering many modern SLAM backends
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization

Vidéos

Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

Wikipédia

Optimisation linéaire en nombres entiers