Optimisation primale en nombres entiers - Primal integer optimization

点击翻译按钮获取中文摘要

Mon objectif de recherche ultime est de résoudre efficacement et d'une façon exacte (optimale) des problèmes en nombres entiers de très grande taille par des méthodes primales, i.e, des méthodes permettant de passer d'une solution entière à une meilleure jusqu'à ce que l'optimalité soit prouvée. La présente demande entend propulser les développements théoriques et algorithmiques de cette filière méthodologique batisée `Primal Integer Optimization` (PIO). Ce genre de méthodes primales a l'avatange de générer en pratique plusieurs solutions de qualité au cours de la résolution au lieu d'une seule solution à la fin comme c'est souvent le cas des méthodes "duales" de type Branch & Cut. Après des progrès très intéressants dans la résolution des problèmes de partitionnement d'ensemble (problèmes binaires avec une structure particulière), je m'intéresse dans cette demande aux problèmes binaires plus généraux, ce qui peut être vu comme un pas de l'avant considérable vers la réalisation du but ultime.******De point de vue théorique, j'étudierais les propriétés polyhédriques permettant d'avoir des algorithmes primaux efficaces (avec une bonne complexité en pratique), notamment la quasi-intégralité. Cette propriété, nécessaire pour aller d'une solution entière à une autre adjacente améliorée, est présente dans les problèmes de partitionnement mais on la perd dans les problèmes binaires quelconques. Comment restituer cette propriété, même localement (moyennant des changements polyhédriques, quitte à augmenter la dimension du problème par l'ajout, par exemple, des variables agrégées appropriées) sera une question à étudier. J'étudierais aussi la caractérisation des solutions fractionnaires afin de les pénaliser en utilisant des normalisations qui pondèrent négativement les directions de descente vers celles-ci.***On les évitera ainsi d'une façon préventive, i.e., sans branchement et sans coupes! Ces développements théoriques seront réétudiés dans d'autres contextes d'intérêt comme la génération de colonnes ou la ré-optimisation en temps réel (après perturbation) selon un ou plusieurs critères.******De point de vue pratique, cette demande introduit un framework unifié où on peut utiliser, à chaque itération, des méthodes exactes ou heuristiques pour trouver en parallèle des directions de descente menant à des solutions entières améliorées. Ces méthodes seront combinées avec un "partial pricing" intelligent favorisant l'intégralité afin de converger plus rapidement. Résoudre optimalement ou presque des problèmes binaires complexes (en transport, mines et énergie) de plusieurs dizaines de milliers de contraintes et de millions de variables binaires dans des temps raisonnables (pour l'industrie) est un défi à relever. Un nouvel optimiseur PIO sera développé et mis à disposition de la communauté scientifique et l'industrie. C'est un jeune paradigme très prometteur en besoin de vitesse!