Dépannage avancé de la page de destination

Malgré la maturité de la technologie LP, certains cas d'utilisation nécessitent des techniques plus avancées. Par exemple, un certain nombre d'implémentations et d'algorithmes de page de destination sont disponibles, chacun présentant ses points forts et ses points faibles. De plus, en raison d'une instabilité numérique, les résolveurs peuvent ralentir ou échouer à résoudre certains modèles.

Ce guide présente les concepts et fournit des exemples pour vous aider à optimiser les performances et la fiabilité de ces solutions.

Concepts

Cette section présente les concepts clés d'une utilisation avancée des résolveurs LP. Nous partons du principe que les lecteurs connaissent bien le concept de dualité dans LP.

Familles d'algorithmes LP

Les classes d'algorithmes suivantes pour LP sont accessibles via OR-Tools.

  1. L'algorithme simplex, qui est le premier algorithme pratique LP, reste le plus populaire. L'algorithme marche le long des sommets (points d'angle) de la région réalisable, améliorant de manière itérative la valeur de la fonction objectif jusqu'à atteindre une solution optimale. Il existe deux types d'algorithmes simplex:

    1. Le mode simplex primaire effectue des étapes le long des sommets de la région réalisable primaire. Cette variante est particulièrement efficace pour résoudre une séquence de problèmes de page de destination avec différentes fonctions objectives, c'est-à-dire lorsque la région primaire est fixe.
    2. Le double simplex effectue des étapes le long des sommets de la double région faisable. Cette variante est particulièrement efficace pour résoudre une séquence de problèmes de LP où la double région réalisable est fixe, par exemple lorsque seules les limites des variables changent. C'est pourquoi le double simplex est largement utilisé dans les résolveurs MIP.

  2. Les méthodes barrière ou point intérieur représentaient la deuxième famille pratique d'algorithmes pour la page de destination. Dans la pratique, les méthodes de barrière associent des garanties théoriques de convergence efficace (en temps polynomial) à des performances fiables. Ils complètent l'algorithme simplex lorsqu'il fonctionne mal. Par exemple, certains résolveurs proposent d'exécuter à la fois simplex et barrière en parallèle, en renvoyant la solution de l'algorithme qui termine en premier.

  3. Les méthodes de premier ordre sont une famille d'algorithmes qui utilisent exclusivement des informations de gradient (c'est-à-dire des dérivées de premier ordre) pour guider les itérations. La descente de gradient est un exemple bien connu. Ces méthodes sont populaires pour l'optimisation non linéaire et le machine learning. En ce qui concerne la page de destination, les méthodes de premier ordre peuvent s'adapter à des problèmes plus importants que le simplex et la barrière, et peuvent également avoir des besoins en mémoire beaucoup plus faibles. En revanche, ils sont plus sensibles aux problèmes numériques et peuvent avoir du mal à obtenir des solutions très précises.

Le tableau ci-dessous liste les résolveurs de page de destination disponibles dans les outils OR et indique laquelle des trois familles d'algorithmes est implémentée dans chaque solution.

Solveur Simplex Barrière Premier ordre
Applaudissement X X
CPLEXL X X
GlopG X
GLKK X X
GurobiL X X
Protection contre la perte de donnéesG X
XpressL X X

G indique que le résolveur est développé par Google. L indique que le résolveur nécessite une licence délivrée par le développeur tiers correspondant.

Consultez la page Recommandations pour obtenir des suggestions sur les résolveurs et les algorithmes à utiliser.

Que signifie résoudre réellement ?

Pour exploiter tout le potentiel des solutionneurs de pages de destination, il est important de comprendre ce qui est implicite lorsqu'un résolveur prétend avoir trouvé une solution à un problème. Cette section aborde les principes de base nécessaires pour répondre à cette question, en particulier compte tenu de l'imprécision numérique et du caractère non unique des solutions.

Tolérances

Les résolveurs LP utilisent presque toujours l'arithmétique à virgule flottante, ce qui expose leurs solutions à une imprécision numérique. Pour tenir compte de cela et améliorer les performances en évitant d'effectuer des efforts sur des solutions déjà satisfaisantes, les résolveurs acceptent des solutions (et prétendent avoir résolu un problème) lorsque ces solutions répondent aux conditions jusqu'à certaines tolérances.

Envisager le problème de programmation linéaire

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

et le double problème correspondant

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Cette paire de problèmes a une solution primaire optimale unique de $ x_1 = 1, x_2 = 0 $ et une double solution $ y = -2 $. Quelles solutions pourraient être acceptées comme optimales par un résolveur ? Pour répondre à cette question, nous définissons les quantités suivantes:

  • L'écart de dualité correspond à la différence entre la valeur d'objectif primaire et la valeur d'objectif double, dans ce cas, $ |(-2x_1 - x_2) - y| $.
  • Les infaisables primaires sont les violations des contraintes primaires, dans ce cas, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • La double infaisabilité correspond aux violations des contraintes doubles, dans ce cas, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Un résolveur déclare une solution comme optimale si l'écart de dualité, les infaisabilités primaires et les doubles inexactitudes sont inférieurs à une tolérance donnée1.

En particulier, l'application des tolérances varie pour des raisons naturelles et idiosyncratiques selon les résolveurs et les algorithmes. Par exemple, l'écart de dualité dans l'algorithme simplex n'est motivé que par l'imprécision numérique, tandis que les infaisabilités primaires et doubles sont présentes, même en arithmétique exact. Certaines méthodes appliquent directement les contraintes liées aux contraintes $ x_1 \ge 0, x_2 \ge 0, $ et $ y \le 0 $, tandis que d'autres traitent les violations des contraintes linéaires différemment des violations des contraintes linéaires telles que $x_1 + x_2 \le 1$. Pour certains résolveurs, les valeurs primaires ou égales des problèmes sont considérées comme des tolérances relatives $ et les solutions d'échelle ;

Pour obtenir un exemple de l'effet des tolérances, considérez une tolérance absolue de $ \epsilon = \frac{1}{2} $ appliquée à la paire primal-double ci-dessus. La solution $ x_1 = 1,5, x_2 = 0, y = -3 $ présente un écart de dualité nul et des infamilités inférieures ou égales à $ \epsilon $.Par conséquent, un résolveur peut déclarer cette solution comme "optimale". Pourtant, sa valeur d'objectif (-3) diffère de 1 de la valeur d'objectif optimale réelle de -2. Les valeurs par défaut typiques de $ \epsilon $ sont comprises entre $10^{-6}$ et $10^{-8}$, ce qui rend ces exemples extrêmes rares, mais pas impossibles.

Types de solutions

Les problèmes de LP peuvent avoir plusieurs solutions optimales, et encore plus en ce qui concerne les tolérances. Nous discutons brièvement des propriétés des solutions renvoyées par les trois familles différentes d'algorithmes LP présentées ci-dessus.

Les algorithmes simplex renvoient toujours les sommets ou les points d'angle de la région réalisable. Ces solutions sont privilégiées dans certaines situations, car elles ont tendance à être plus disparates.

Les méthodes de barrière et de premier ordre ne renvoient généralement pas de sommets. (La théorie fournit des caractérisations supplémentaires qui sortent du cadre de ce guide.)

Pour des raisons historiques et parce que les solutions de sommets présentent des propriétés attrayantes, les résolveurs appliquent souvent par défaut une procédure de crossover pour passer à un sommet optimal à partir d'une solution trouvée par un algorithme de barrière. Le crossover n'est actuellement pas proposé pour les solutions trouvées par des méthodes de premier ordre.

Recommandations

Nous formulons les recommandations suivantes pour une utilisation avancée des solutionneurs de pages de destination.

Mise à l'échelle des données problématiques

Les résolveurs peuvent rencontrer une convergence lente ou des échecs sur les modèles en raison de problèmes numériques. De tels problèmes peuvent survenir pour de nombreuses raisons. Voici un exemple.

Il est courant que des constantes numériques très petites ou grandes apparaissent dans les modèles LP. Dans la continuité de l'exemple ci-dessus, si \(x_1\) et \(x_2\) représentent la fraction des clients affectés au "fournisseur 1" ou au "fournisseur 2", et si nous voulons maximiser les avantages du service à ces clients, nous pouvons écrire la fonction d'objectif suivante :

$$ \min -c_1x_1 - c_2x_2 $$

où :

  • $ c_1 $ profite à l'attribution de clients au fournisseur 1
  • $ c_2 $ profite de l'avantage de l'affectation de clients au fournisseur 2

Les duaux répondant aux contraintes suivantes seraient considérés comme réalisables avec une tolérance absolue $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

Si les unités des avantages de $ c_1 $ et $ c_2 $ sont de petites valeurs fractionnaires qui se situent sur la même échelle que $ \epsilon $, la double condition de faisabilité devient plutôt faible. Par conséquent, un primaire primale très non optimal peut être déclaré comme optimal.

Si, en revanche, les unités de bénéfices sont des "microdollars" (1 000 000 microdollars = 1 dollar), les très grandes valeurs absolues qui en résultent demandent une très grande précision dans la solution, qui peut être exagérément élevée étant donné les limites des nombres à virgule flottante. Les résolveurs peuvent ne pas parvenir à converger si le problème est formulé de cette manière. Lorsqu'ils formulent un problème bien posé, les créateurs de modèles avancés doivent déterminer si les données du problème sont mises à l'échelle de manière à respecter les tolérances de leur résolveur.

En plus d'éviter les défaillances numériques, les tolérances peuvent être ajustées pour améliorer les performances. Les méthodes simplex et barrière ne sont pas trop sensibles aux tolérances, mais peuvent parfois bénéficier de tolérances plus importantes si les progrès sont constatés au ralenti en fin de résolution. En revanche, les méthodes de premier ordre sont généralement beaucoup plus sensibles. Les utilisateurs de méthodes de premier ordre peuvent bénéficier de solutions plus rapides en assouplissant les tolérances, selon le contexte.

Pour les tolérances de Glop, consultez primal_feasibility_tolerance, dual_feasibility_tolerance et solution_feasibility_tolerance dans GlopParameters. Notez que primal_feasibility_tolerance et dual_feasibility_tolerance sont utilisés dans l'algorithme, tandis que solution_feasibility_tolerance est vérifié après la résolution pour signaler les problèmes numériques. Pour la protection contre la perte de données, consultez eps_optimal_absolute et eps_optimal_relative.

Pour en savoir plus sur ces types de problèmes, consultez les Consignes de Gurobi pour les problèmes numériques. Bien que ces consignes s'adressent aux utilisateurs de Gurobi, nombre d'entre elles s'appliquent de manière générale.

Choix de résolveurs et d'algorithmes

Nous commencerons par un exemple de l'ampleur de l'impact du choix des résolveurs et des algorithmes, puis nous vous présenterons un guide pour choisir les solutions LP.

La variabilité dans la pratique

Pour illustrer la variabilité des performances entre les algorithmes et les résolveurs de pages de destination, nous comparons les temps de résolution d'une sélection d'instances utilisées par Hans Mittelmann pour l'analyse comparative des solutions de pages de destination. Les instances sont explicitement choisies pour montrer les extrêmes des performances relatives et ne sont pas nécessairement représentatives d'un comportement typique.

Les méthodes primale et double simplex de Glop sont comparées à la méthode de barrière de Gurobi (avec et sans croisement, qui permet de trouver une solution de sommet) et à PDLP, une méthode de premier ordre, avec une précision élevée et faible. Les rapports du tableau ci-dessous résolvent les temps en secondes, avec une limite de 20 minutes (1 200 secondes).

Instance Glop
primaire simplex		 Glop
Dual Simplex		 Barrière Gurobi
avec Crossover		 Barrière Gurobi
sans crossover		 PDLP
Haute précision		 PDLP
basse précision
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3e >1200 252.8 144,6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
wide15 >1200 20,8 >1200 >1200 916,4 56.3
bâtimenténergie 178.4 267.5 12,8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
Version du résolveur OR-Tools 9.3 OR-Tools 9.3 Gurobi 9.0 Gurobi 9.0 OR-Tools 9.3 OR-Tools 9.3
solver_specific_parameters (par défaut) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

De ces résultats, nous concluons ce qui suit.

  • Les performances relatives des algorithmes et des résolveurs peuvent varier par ordre de grandeur sur une seule instance.
  • Aucun algorithme et outil de résolution unique n'est uniformément meilleur que les autres.
  • Le crossover (activé par défaut) augmente le temps de résolution, parfois de manière significative.
  • La protection contre la perte de données peut atteindre une précision faible, parfois 10 fois plus rapide, qu'une précision élevée.

Guide rapide pour choisir des solutions de page de destination

Étant donné qu'aucun algorithme ou solution de page de destination unique n'est adapté, nous vous recommandons de suivre les étapes suivantes pour identifier la solution la mieux adaptée à votre cas d'utilisation. Commencez par la première étape et passez à la suivante si les performances ne sont pas suffisantes.

  1. Essayez Glop. Pourquoi ? Glop est l'implémentation interne des méthodes primaire et double simplex par Google. Glop est une solution Open Source de confiance pour les charges de travail de production de Google.
    • Si la configuration par défaut (simplex primaire) ne fonctionne pas correctement, essayez de passer au double simplex à l'aide de use_dual_simplex: true.
  2. Si une licence est disponible, essayez un résolveur commercial (CPLEX, Gurobi ou Xpress). Expérimentez les méthodes simplex et barrière. Pourquoi ? Ces résolveurs sont standards dans l'industrie et hautement optimisés. De plus, les méthodes de barrière complètent les algorithmes simplex proposés par Glop.
    • Si vous utilisez une barrière, désactivez le "crossover" si vous n'avez pas besoin d'une solution de sommet.
  3. Essayez la protection contre la perte de données. Ajustez les tolérances de convergence en fonction de votre application. Pourquoi ? La protection contre la perte de données est conçue pour les problèmes les plus importants, lorsque les méthodes simplesx et barrière atteignent les limites de mémoire ou sont trop lentes. La protection contre la perte de données offre de meilleurs résultats lorsqu'une solution approximative, mais rapide, est préférable à une solution exacte, mais lente.
  4. Si vous êtes arrivé jusqu'ici, vous êtes désormais un utilisateur LP de haut niveau ! Veuillez consulter les options d'assistance OR-Tools pour obtenir de l'aide.

  1. Cette méthode est souvent plus complexe que cela. Les résolveurs vérifient généralement ces conditions sur une version transformée/simplifiée du problème, appelée "problème présolu". Dans certains cas, une solution au problème résolu peut être très éloignée de la solution au problème d'entrée. Cette situation peut entraîner des états inhabituels tels que OptimalInfeas de CPLEX ou IMPRECISE de Glop.↩