Pourquoi utiliser des plans de coupe en optimisation entière ?

L’optimisation entière intervient dès qu’une décision ne peut pas être fractionnée : ouvrir ou non un dépôt, affecter un véhicule, sélectionner un projet, fabriquer un nombre entier d’unités. Dans une programmation linéaire en nombres entiers (PLNE), cette contrainte rend la résolution nettement plus difficile qu’en programmation linéaire classique. Les plans de coupe constituent un levier majeur : ils rapprochent progressivement le modèle continu des décisions réellement admissibles, tout en préservant la possibilité de prouver l’optimalité.

Le défi central de l’optimisation entière : une relaxation trop éloignée de la solution réalisable

Une PLNE impose que certaines variables soient binaires ou entières. Or, les solveurs commencent généralement par résoudre la relaxation linéaire : les contraintes d’intégralité sont retirées et les variables peuvent prendre toute valeur réelle compatible avec les autres contraintes. Cette relaxation définit un polyèdre réalisable souvent plus vaste que l’ensemble des solutions entières. Elle peut ainsi proposer 2,4 camions, 0,6 entrepôt ou une sélection partielle de plusieurs projets. Ces résultats sont mathématiquement utiles, mais opérationnellement impossibles. Pour un problème de maximisation, la valeur de la relaxation fournit une borne duale : elle majore l’optimum entier. L’écart entre cette borne et la meilleure solution entière connue, appelée incumbent, est l’écart d’intégralité. Lorsqu’il est important, le solveur doit explorer beaucoup de combinaisons. Le mécanisme de branch-and-bound crée alors des sous-problèmes, ou nœuds, en fixant progressivement des décisions. Cette exploration peut devenir coûteuse si la relaxation initiale est faible.

Le principe des plans de coupe : exclure des solutions fractionnaires sans perdre les solutions entières

De l’inégalité valide à la réduction de l’espace de recherche

Un plan de coupe est une inégalité valide pour le problème entier : toutes les solutions réalisables entières la respectent. En revanche, la solution fractionnaire actuellement obtenue viole cette inégalité. Son ajout élimine donc une portion inutile du polyèdre de relaxation, sans écarter aucune décision admissible. L’objectif théorique est de se rapprocher de l’enveloppe convexe entière, le plus petit polyèdre qui contient exactement toutes les solutions entières réalisables. Il n’est généralement pas réaliste de décrire cette enveloppe complètement ; les coupes cherchent plutôt à en capturer les facettes les plus utiles. Une coupe de Chvátal-Gomory illustre ce principe : elle combine des contraintes existantes puis utilise un arrondi justifié par l’intégralité des variables. La notion de rang de Chvátal-Gomory mesure le nombre d’itérations de fermeture nécessaires pour faire apparaître certaines inégalités, mais elle reste surtout un outil théorique pour évaluer la force d’une formulation.

L’ajout itératif de coupes dans un solveur

Le processus est dynamique. Après avoir résolu la relaxation, le solveur effectue une séparation, c’est-à-dire qu’il cherche une inégalité valide violée par la solution courante. Il ajoute les coupes retenues, résout de nouveau la relaxation, puis recommence tant que cela améliore utilement la borne.

• Résolution de la relaxation au nœud courant ;
• détection d’une solution fractionnaire ;
• recherche de coupes violées par cette solution ;
• ajout des inégalités retenues et nouvelle optimisation ;
• branchement seulement si l’intégralité n’est toujours pas atteinte.

Cette association entre coupes et branchement est le branch-and-cut. Certaines coupes sont globalement valides, donc réutilisables dans tout l’arbre ; d’autres sont localement valides et ne s’appliquent qu’au nœud où des bornes de branchement ont été imposées.

Les bénéfices concrets des plans de coupe pour résoudre plus vite

Resserer la borne de la relaxation linéaire

Le premier gain est qualitatif : une relaxation plus proche de l’optimum entier donne une borne plus crédible. Dans un problème de maximisation, une borne duale abaissée réduit immédiatement l’écart avec l’incumbent. La résolution linéaire reste au cœur du procédé, héritière des méthodes comme le simplexe, mais les coupes adaptent le polyèdre au caractère discret du problème.

Réduire la taille de l’arbre de branchement

Une coupe efficace évite de devoir créer des branches pour distinguer des solutions qui auraient dû être éliminées dès la relaxation. Un nœud peut être écarté parce que sa borne devient moins bonne que l’incumbent, ou parce qu’il devient infaisable. Moins de nœuds signifie généralement moins de résolutions linéaires, donc un temps de calcul plus prévisible. Ce bénéfice est particulièrement important pour les modèles combinatoires, dont l’espace de recherche croît vite. Dans certains cas structurés, une complexité pseudo-polynomiale ou une programmation dynamique peut offrir une autre voie, mais les coupes restent essentielles dans les modèles riches mêlant capacité, affectation et logique métier.

Certifier plus efficacement l’optimalité

Trouver une bonne solution entière ne suffit pas : il faut aussi démontrer qu’aucune meilleure solution n’existe. Les coupes renforcent les bornes dans les nœuds ouverts et facilitent cette certification. Lorsque la borne duale rejoint la valeur de l’incumbent, l’optimalité est prouvée. Elles permettent donc d’améliorer simultanément la recherche d’une solution et la qualité du certificat associé.

Quelles familles de coupes utiliser selon la structure du problème

Structure du modèle	Famille de coupes pertinente	Effet recherché
PLNE générale	Gomory	Éliminer une base fractionnaire
Sac à dos, capacité	Couverture et lifting	Renforcer une contrainte surchargée
Réseau, tournées	Connectivité, sous-tours	Garantir une structure reliée

Coupes de Gomory pour les formulations générales

Les coupes de Gomory fractionnaires sont dérivées d’une ligne du tableau simplex associée à une solution de base non entière. Elles ont l’avantage d’être génériques : elles ne nécessitent pas de connaître la signification métier détaillée des variables. Leur efficacité varie toutefois avec la formulation et elles peuvent devenir nombreuses ; les solveurs les sélectionnent donc avec prudence.

Coupes couvrantes pour les problèmes de sac à dos

Dans une contrainte de capacité, un ensemble d’objets peut dépasser la limite s’il est choisi entièrement. Cet ensemble est une couverture. L’inégalité de couverture interdit alors de sélectionner simultanément tous ses éléments. Une couverture liftée ajuste aussi les coefficients d’autres variables, ce qui produit une contrainte plus forte. Ces coupes sont naturelles pour la sélection de projets, le chargement ou les budgets limités.

Coupes de connectivité et coupes valides pour les problèmes de réseau

Les problèmes de tournées, d’arbres ou de conception de réseaux demandent souvent que les éléments sélectionnés restent reliés. Les contraintes de connectivité empêchent la formation de composants isolés. Dans le voyageur de commerce, les coupes de sous-tours éliminent les cycles disjoints qui respectent les degrés locaux mais ne forment pas une tournée unique. Leur séparation peut être elle-même un problème algorithmique substantiel.

Limites et bonnes pratiques : ajouter des coupes utiles sans alourdir le modèle

Éviter un trop grand nombre de coupes faibles ou redondantes

Toutes les coupes valides ne sont pas bénéfiques. Une inégalité très dense, contenant beaucoup de coefficients non nuls, peut ralentir les résolutions linéaires. Des coupes presque redondantes augmentent la taille mémoire sans améliorer significativement la borne. L’efficacité se juge donc par un compromis : gain de borne, coût de séparation et impact sur le temps de résolution. Les solveurs limitent souvent le nombre de coupes par passage, privilégient celles qui sont fortement violées et peuvent supprimer des contraintes devenues inactives. Il ne faut pas assimiler « davantage de coupes » à « meilleure résolution ».

Renforcer d’abord la formulation et s’appuyer sur les coupes du solveur

La première étape reste une formulation forte : bornes serrées, variables bien définies, contraintes logiques explicites et coefficients raisonnablement calibrés. Le prétraitement peut fixer des variables, supprimer des contraintes dominées ou resserrer des domaines avant toute séparation. Les coupes automatiques des solveurs couvrent déjà de nombreuses familles. Des coupes métier sur mesure deviennent pertinentes lorsqu’une structure spécifique est mal capturée. Elles doivent être testées contre une référence, car une autre modélisation — voire une relaxation lagrangienne ou une programmation dynamique — peut parfois fournir un meilleur renforcement.

Vers des modèles plus faciles à résoudre

Les inégalités ajoutées au bon moment transforment une relaxation trop permissive en une approximation plus fidèle des décisions possibles. Leur intérêt ne tient pas à leur nombre, mais à leur capacité à resserrer la borne sans rendre les calculs inutilement lourds. Elles réduisent ainsi l’effort de branchement et facilitent la preuve qu’une solution entière est réellement optimale. La priorité reste néanmoins une formulation claire, avec des bornes cohérentes et des contraintes métier bien exprimées. Les mécanismes automatiques des solveurs constituent un point de départ solide ; des inégalités spécifiques ne se justifient que si la structure du problème l’exige. En pratique, il faut viser un compromis entre force du modèle et coût de résolution, puis mesurer l’effet des ajustements sur des instances représentatives.

Questions fréquentes

Les plans de coupe garantissent-ils toujours une résolution plus rapide ?

Non. Ils accélèrent la résolution lorsqu’ils améliorent suffisamment la borne pour compenser leur coût de calcul. Des coupes trop nombreuses, denses ou peu violées peuvent au contraire ralentir les résolutions linéaires. La qualité prime sur la quantité.

Peut-on ajouter un plan de coupe qui élimine une solution optimale ?

Pas si l’inégalité est valide. Par définition, une coupe valide est satisfaite par toutes les solutions entières réalisables, y compris l’optimum. Une erreur de modélisation ou de génération de la coupe peut toutefois rendre une contrainte invalide ; elle doit donc être vérifiée avec soin.

Quelle différence entre une coupe globale et une coupe locale ?

Une coupe globale reste valable pour l’ensemble du problème et peut être utilisée dans tous les nœuds de recherche. Une coupe locale n’est valide qu’après certaines décisions de branchement. Une coupe locale ne doit pas être réemployée hors de son contexte.

Faut-il programmer ses propres coupes avec un solveur moderne ?

Généralement, non au départ. Les solveurs disposent de générateurs robustes pour les coupes courantes. Des coupes personnalisées se justifient surtout lorsque le problème possède une structure métier particulière que la formulation standard exploite mal.