Difficulté des problèmes linéaires à variables mixtes: application au problème de planification d'unités de production

[PROJET ATTRIBUE]

* Pré-requis:
Connaissances en algorithmique et programmation linéaire
Goût pour la programmation (langage C, C++, java)
Goût pour l'étude théorique de problème combinatoire

* Cadre:

On appelle programme linéaire à variables mixtes (PLM) un programme linéaire contenant à la fois des variables continues (à valeurs dans R) et des variables discrètes (à valeurs dans Z). Comme cette catégorie de problèmes contient les programmes linéaires à variables discrètes, résoudre un PLM est un problème NP-difficile. Toutefois, il apparaît que, dans de nombreux cas pratiques, ces PLM sont faciles à résoudre à l'aide de solveurs entiers basés sur des algorithmes de branchement. On appelle ici difficulté à résoudre un PLM le fait que soit un algorithme de branchement simple, soit un solveur entier, échouent à résoudre rapidement un PLM.

Outre la taille des PLM en nombre de variables et d'inégalités, la principale difficulté connue est appelée symétrie: on dit qu'une instance présente de fortes symétries lorsque l'espace de ses solutions contient des lots de solutions ayant même coût et telles que l'on passe d'une solution à l'autre en permutant la valeur de certaines variables. Face à la présence de symétrie, les algorithmes de branchements et les solveurs entiers doivent explorer un grand nombre de solutions, ralentissant la résolution de manière exponentielle.

Dans ce projet, nous nous focaliserons sur les PLM issus du problème de planification d'unités de production, en anglais Unit Commitment Problem (UCP). Ce problème consiste à décider des marches et arrêts d'unités sous la contrainte de satisfaire la demande de production sur un horizon de temps discret (journalier) en respectant des contraintes techniques fortes. Ainsi la résolution de l'UCP est un enjeu majeur pour les producteurs d'électricité comme EDF. Ce cas particulier de PLM possède exactement la structure nécessaire à notre étude avec des décisions de marche/arrêt, correspondant à des variables discrètes, mais aussi du niveau de production d'une unité, correspond donc à des variables continues. Il est à noter qu'une instance de l'UCP limitée à un seul pas de temps est une instance du problème de sac-à-dos mixtes. Pour le problème du sac-à-dos entier, on sait par exemple produire des instances présentant de fortes symétries. On s'appuiera sur ces résultats pour les étendre à l'UCP en général.

L'objectif de ce projet est de concevoir des outils informatiques pour mesurer la difficulté des instances de l'UCP et d'en déduire les catégories d'instances que l'on peut qualifier ou non difficiles. Ce travail permettra d'évaluer la difficulté des instances de l'UCP provenant de l'industrie. Un autre objectif plus large est d'étudier les propriétés structurelles induisant qu'un PLM est difficile ou non. En effet, même si un PLM est théoriquement aussi difficile à résoudre qu'un PLNE, résoudre un PLM par algorithme de branchement s'avère plus facile, par exemple, lorsque les coûts sont portés uniquement par les variables continues.

*Travail à effectuer:

Plusieurs tâches informatiques sont nécessaires à cette caractérisation des instances de l'UCP:
- à partir des instances de la littérature scientifique de l'UCP, construire un outil de visualisation des solutions entières et fractionnaires.
- créer un algorithme de branchement simple et mettre en oeuvre un solveur pour résoudre ces instances.
- construire des instances de l'UCP de manière à créer plusieurs classes d'instances possédant des caractéristiques propres.
- en parallèle, tester expérimentalement leurs difficultés à être résolues par les deux procédés mis en oeuvre.

Ces différents outils et instances vont permettre peu à peu d'identifier les grandes catégories de PLM faciles ou difficiles. Il est probable que cette étude expérimentale mène à une étude théorique des caractéristiques de ces catégories d'instance.