• Optimisation d'entiers

Les problèmes d'optimisation linéaire qui nécessitent que certaines variables soient des entiers sont appelés Programmes d'entiers mixtes (MIP).

Ces variables peuvent survenir de différentes manières:

• Variables entières qui représentent des nombres d'éléments, tels que des voitures ou des téléviseurs. Le problème consiste à décider de la quantité de chaque article à fabriquer afin de maximiser les bénéfices.
  Généralement, ces problèmes peuvent être configurés comme des problèmes d'optimisation linéaire standards, avec une exigence supplémentaire selon laquelle les variables doivent être des entiers. La section suivante présente un exemple de ce type de problème.

• Variables booléennes qui représentent les décisions avec des valeurs de 0 à 1.
  À titre d'exemple, prenons un problème qui implique l'affectation de nœuds de calcul à des tâches (voir la section Attribution). Pour configurer ce type de problème, vous pouvez définir des variables booléennes x_i,j égales à 1 si le nœud de calcul i est attribué à la tâche j, et à 0 dans le cas contraire.

Pour bien comprendre l'optimisation des nombres entiers, nous vous recommandons de consulter le livre de recettes sur la modélisation Mosek.

Outils

Google propose plusieurs façons de résoudre les problèmes MIP:

• MPSolver: wrapper pour plusieurs résolveurs MIP tiers, qui utilisent des techniques standards de branchement et de liaison.
• Résolution CP-SAT: résolveur de programmation de contraintes qui utilise des méthodes SAT (satisfiabilité).
• Solutionneur CP d'origine: résolveur de programmation de contraintes.

Remarque :Google propose également une API Cloud à un résolveur MILP via AI Workshop. Si vous souhaitez utiliser ce résolveur, vous pouvez demander l'accès.

Quel résolveur dois-je utiliser ?

Il n'existe aucune règle absolue pour décider s'il faut utiliser un résolveur MIP ou un résolveur CP-SAT. À titre indicatif:

• Les résolveurs MIP sont mieux adaptés aux problèmes pouvant être configurés comme une page de destination standard, mais avec des variables entières arbitraires, comme dans le premier exemple ci-dessus.
• Le résolveur CP-SAT est mieux adapté aux problèmes dans lesquels la plupart des variables sont booléennes, comme dans le deuxième exemple ci-dessus.

Pour les MIP classiques comportant à la fois des variables entières et booléennes, il n'y a souvent pas de différence de vitesse entre les deux résolveurs. Votre choix peut donc se résumer à vos préférences personnelles.

Pour obtenir des exemples utilisant à la fois les résolveurs MIP et CP-SAT, consultez la page Résoudre un problème d'attribution et les autres sections d'attribution.

Une autre façon de résoudre les problèmes de programmation sur les nombres entiers consiste à utiliser un résolveur de flux réseau.
Consultez l'exemple de la section Attribution en tant que problème de flux de coût minimal.
Pour un problème pouvant être configuré en tant que flux réseau, le résolveur de flux de coût minimal peut être plus rapide que les résolveurs MIP ou CP-SAT. Cependant, tous les MIP ne peuvent pas être configurés de cette manière.