Auswahl der wissenschaftlichen Literatur zum Thema „Programmation mathématique non linéaire en variables mixtes“

La programmation mathématique fournit un cadre pour l'étude et la résolution des problèmes d'optimisation contraints ou non. Elle constitue une branche active des mathématiques appliquées, depuis la deuxième moitié du XXème siècle.L'objet de cette thèse est la résolution d'un programme mathématique non convexe non linéaire en variables entières, sous contrainte linéaire d'égalité. Le problème proposé, bien qu'abordé dans cette étude uniquement pour le cas déterministe, trouve son origine en finance, sous le nom d'écoulement de larges blocs d'actifs, ou de liquidation optimale de portefeuille. Il consiste à vendre une (très large) quantité M donnée d'un actif financier en temps fini (discrétisé en N instants) en maximisant le produit de cette vente. A chaque instant, le prix de vente est modélisé par une fonction de pénalité qui reflète le comportement antagoniste du marché face à l'écoulement progressif.Du point de vue, de la programmation mathématique, cette classe de problème est NP-difficile résoudre d'après Garey et Johson, car la non-convexité de la fonction objectif impose d'adapter les méthodes classiques de résolutions (Branch and Bound , coupes) en variables entières. De plus, comme on ne connait pas de méthode de résolution générale pour cette classe de problèmes, les méthodes utilisées doivent être adaptées aux spécificités du problème.La première partie de cette thèse est consacrée à la résolution exacte ou approchée utilisant la programmation dynamique. Nous montrons en effet, que l'équation de Bellman s'applique au problème proposé et permet ainsi de résoudre exactement et rapidement les petites instances. Pour les moyennes et grandes instances, où la programmation dynamique n'est plus disponible et/ou performante, nous proposons des bornes inférieures via différentes heuristiques utilisant la programmation dynamique ainsi que des méthodes de recherche locale, dont nous étudions la qualité (optimalité, temps CPU) et la complexité.La seconde partie de la thèse s'intéresse à la reformulation équivalente du problème de thèse sous forme factorisée et à sa relaxation convexe via les inégalités de McCormick. Nous proposons alors deux algorithmes de résolution exacte du type Branch and Bound, qui fournissent l'optimum global ou un encadrement en temps limité.Dans une troisième partie, dédiée aux expérimentations numériques, nous comparons les méthodes de résolutions proposées entre elles et aux solvers de l'état de l'art. Nous observons notamment que les bornes obtenues sont souvent proches et mêmes parfois meilleures que celles des solvers libres ou commerciaux auxquels nous nous comparons (ex : LocalSolver, Scip, Baron, Couenne et Bonmin).De plus, nous montrons que nos méthodes de résolutions peuvent s'appliquer à toute fonction de pénalité suffisamment régulière et croissante, ce qui comprend notamment des fonctions qui ne sont pas actuellement pas prises en charge par certains solvers, bien qu'elles aient un sens économique pour le problème, comme par exemple les fonctions trigonométriques ou la fonction arctangente.Numériquement, la programmation dynamique permet de résoudre à l'optimum, sous la minute, des instances de taille N<100 et M<10 000. Les heuristiques proposées fournissent de très bonnes bornes inférieures, qui atteignent très souvent l'optimum, pour N<1 000 et M<100 000. Par contraste, la résolution du problème factorisé n'est efficace que pour N< 10, M<1 000, mais nous obtenons des bornes supérieures relativement bonnes. Enfin, pour les grandes instances (M>1 000 000), nos heuristiques à base de programmation dynamique, lorsqu'elles sont disponibles, fournissent les meilleures bornes inférieures, mais nous n'avons pas d'encadrement précis de l'optimum car nos bornes supérieures ne sont pas fines
Mathematical programming provides a framework to study and resolve optimization problems, constrained or not. It represents an active domain of Applied Mathematics, for the second half of the 20th century.The aim of this thesis is to solve an non convex, non linear, pure integer, mathematical program, under a linear constraint of equality. This problem, although studied in this dissertation only in the deterministic case, stems from a financial application, known as the large block sale problem, or optimal portfolio liquidation. It consists in selling a (very large) known quantity M of a financial asset in finite time, discretized in N points in time, while maximizing the proceeds of the sale. At each point in time, the sell price is modeled by a penalty function, which reflects the antagonistic behavior of the market in response to our progressive selling flow.From the standpoint of the mathematical programming, this class of problems is NP-hard to solve according to Garey and Johnson, because the non convexity of the objective function imposes on us to adapt classical resolutions methods (Branch and Bound, cuts) for integer variables. In addition, as no general resolution method for this class of problems is known, the methods used for solving must be adapted to the problem specifics.The first part of the thesis is devoted to solve the problem, either exactly or approximately, using Dynamic Programming. We indeed prove that Bellman's equation applies to the problem studied and thus enables to solve it exactly and quickly for small instances. For medium and large instances, for which Dynamic Programming is either not available and/or efficient, we provide lower bounds using different heuristics relying on Dynamic Programming, or local search methods, for which performance (tightness and CPU time) and complexity are studied.The second part of this thesis focuses on the equivalent reformulation of the problem in a factored form, and on its convex relaxation using McCormick's inequalities. We introduce two exact resolution algorithms, which belongs to the Branch and Bound category. They return the global optimum or bound it in limited time.In a third part, dedicated to numerical experiments, we compare our resolution methods between each other and to state of the art solvers. We notice in particular that our bounds are comparable and sometimes even better than solvers' bounds, both free and commercial (e.g LocalSolver, Scip, Baron, Couenne et Bonmin), which we use as benchmark.In addition, we show that our resolution methods may apply to sufficiently regular and increasing penalty functions, especially functions which are currently not handled by some solvers, even though they make economic sense for the problem, as does trigonometric functions or the arctangent function for instance.Numerically, Dynamic Programming does optimally solve the problem, within a minute, for instances of size N<100 and M< 10 000. Our heuristics provide very tight lower bounds, which often reach the optimum, for N<1 000 and M<100 000. By contrast, optimal resolution of the factored problem proves efficient for instances of size N<10, M<1 000, even though we obtain relatively good upper bounds. Lastly, for large instances (M>1 000 000), our heuristics based on Dynamic Programming, when available, return the best lower bounds. However, we are not able to bound the optimum tightly, since our upper bounds are not thin

L'objectif des travaux presentes dans ce memoire est de formuler et de resoudre le probleme de programmation non lineaire en variables mixtes dans l'environnement d'un simulateur modulaire. L'outil logiciel d'aide a la conception optimale des procedes ainsi realise permet alors l'optimisation simultanee du fonctionnement, du dimensionnement et de la structure d'un procede, et ce en utilisant des modeles de connaissance rigoureux. Dans une premiere partie nous revenons sur le probleme general de la synthese des procedes et proposons une classification des nombreux travaux effectues dans ce domaine. Nos travaux s'inscrivent dans le cadre de l'approche par selection algorithmique ce qui suppose la definition prealable d'une superstructure regroupant un nombre fini de procedes parmi lesquels sera choisi le procede optimal. Nous decrivons l'algorithme d'optimisation qui est mis en uvre. Dans la deuxieme partie nous decrivons la strategie generale de resolution dans l'environnement modulaire. Nous proposons une nouvelle formulation du probleme d'optimisation qui permet de traiter les relations implicites entre les variables, relations liees a l'environnement du simulateur modulaire. Cette formulation est fondee sur l'introduction d'un nouvel ensemble de variables d'optimisation et de contraintes: les pseudo-variables et les pseudo-courants coupes. Nous abordons, dans la troisieme partie, l'implantation de l'algorithme d'optimisation dans le simulateur modulaire. Nous decrivons les modifications dans l'architecture du simulateur qui ont ete necessaires ainsi que les choix et les hypotheses qui ont ete faits. Nous decrivons le mode d'utilisation du logiciel. La formulation et l'implantation sont enfin validees sur des exemples dont celui d'un procede d'hydrodesalkylation du toluene

Basés sur les outils théoriques et algorithmiques de la programmation DC et DCA, les travaux de recherche dans cette thèse portent sur les approches locales et globales pour l'optimisation non convexe et l'optimisation globale en variables mixtes entières. La thèse comporte 5 chapitres. Le premier chapitre présente les fondements de la programmation DC et DCA, et techniques de Séparation et Evaluation (B&B) (utilisant la technique de relaxation DC pour le calcul des bornes inférieures de la valeur optimale) pour l'optimisation globale. Y figure aussi des résultats concernant la pénalisation exacte pour la programmation en variables mixtes entières. Le deuxième chapitre est consacré au développement d'une méthode DCA pour la résolution d'une classe NP-difficile des programmes non convexes non linéaires en variables mixtes entières. Ces problèmes d'optimisation non convexe sont tout d'abord reformulées comme des programmes DC via les techniques de pénalisation en programmation DC de manière que les programmes DC résultants soient efficacement résolus par DCA et B&B bien adaptés. Comme première application en optimisation financière, nous avons modélisé le problème de gestion de portefeuille sous le coût de transaction concave et appliqué DCA et B&B à sa résolution. Dans le chapitre suivant nous étudions la modélisation du problème de minimisation du coût de transaction non convexe discontinu en gestion de portefeuille sous deux formes : la première est un programme DC obtenu en approximant la fonction objectif du problème original par une fonction DC polyèdrale et la deuxième est un programme DC mixte 0-1 équivalent. Et nous présentons DCA, B&B, et l'algorithme combiné DCA-B&B pour leur résolution. Le chapitre 4 étudie la résolution exacte du problème multi-objectif en variables mixtes binaires et présente deux applications concrètes de la méthode proposée. Nous nous intéressons dans le dernier chapitre à ces deux problématiques challenging : le problème de moindres carrés linéaires en variables entières bornées et celui de factorisation en matrices non négatives (Nonnegative Matrix Factorization (NMF)). La méthode NMF est particulièrement importante de par ses nombreuses et diverses applications tandis que les applications importantes du premier se trouvent en télécommunication. Les simulations numériques montrent la robustesse, rapidité (donc scalabilité), performance et la globalité de DCA par rapport aux méthodes existantes.

Cette thèse s’inscrit dans le domaine de la programmation mathématique appliquée à la séparation d’aéronefs stabilisés en altitude. L’objectif est le développement d’algorithmes de résolution de conflits aériens ; l’enjeu étant d’augmenter la capacité de l’espace aérien afin de diminuer les retards et d’autoriser un plus grand nombre d’aéronefs à suivre leur trajectoire optimale. En outre, du fait de l’imprécision des prédictions relatives à la météo ou à l’état des aéronefs, l’incertitude sur les données est une caractéristique importante du problème. La démarche suivie dans ce mémoire s’attache d’abord au problème déterministe dont l’étude est nettement plus simple. Pour cela, quatre modèles basés sur la programmation non linéaire et sur la programmation linéaire à variables mixtes sont développés en intégrant notamment un critère reflétant la consommation de carburant et la durée de vol. Leur comparaison sur un ensemble de scénarios de test met en évidence l’intérêt d’utiliser un modèle linéaire approché pour l’étude du problème avec incertitudes. Un champ de vent aléatoire, corrélé en temps et en espace, ainsi qu’une erreur gaussienne sur la mesure de la vitesse sont ensuite pris en compte.Dans un premier temps, le problème déterministe est adapté en ajoutant une marge sur la norme de séparation grâce au calcul d’une approximation des probabilités de conflits. Finalement, une formulation stochastique avec recours est développée. Ainsi, les erreurs aléatoires sont explicitement incluses dans le modèle afin de tenir compte de la possibilité d’ordonner des manoeuvres de recours lorsque les erreurs observées engendrent de nouveaux conflits
This thesis belongs to the field of mathematical programming, applied to the separation of aircraft stabilised on the same altitude. The primary objective is to develop algorithms for the resolution of air conflicts. The expected benefit of such algorithm is to increase the capacity of the airspace in order to reduce the number of late flights and let more aircraft follow their optimal trajectory. Moreover, meteorological forecast and trajectory predictions being inexact,the uncertainty on the data is an important issue. The approach that is followed focuses on the deterministic problem in the first place because it is much simpler. To do this, four nonlinear and mixed integer linear programming models, including a criterion based on fuel consumption and flight duration, are developed. Their comparison on a benchmark of scenarios shows the relevance of using an approximate linear model for the study of the problem with uncertainties.A random wind field, correlated in space and time, as well as speed measures with Gaussianerrors are then taken into account. As a first step, the deterministic problem is adapted by computinga margin from an approximate calculation of conflict probabilities and by adding it tothe reference separation distance. Finally, a stochastic formulation with recourse is developed.In this model, the random errors are explicitly included in order to consider the possibility of ordering recourse actions if the observed errors cause new conflicts

Presentation d'une procedure d'optimisation en variables mixtes pour la conception de procedes et l'identification de modeles de genie chimique. Developpement d'un algorithme de programmation mixte base sur un principe de decomposition, de projection et de relaxation permettant le traitement des problemes non lineaires a variables non necessairement separables. Presentation d'une procedure de decomposition de superstructure permettant de denombrer l'ensemble de toutes les variables discretes et continues du probleme. Illustration par deux exemples d'application: conception optimale d'un procede comportant un ensemble de reacteurs-separateurs et identification d'un modele de representation d'une operation de traitement d'effluents aqueux

Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions
In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features

Les travaux présentés dans cette thèse portent sur la conception d'une méthodologie d'ordonnancement/optimisation pour les systèmes de production à grande variété de produits et faible densité de flux appelés systèmes HVLV (High-Variety, LowVolume). Les caractéristiques de ces systèmes nous permettent d'appréhender la représentation des flux y circulant par un modèle discret. Le comportement discontinu des systèmes HVLV peut être caractérisé par la connaissance des dates de début et de fin des activités de production. L'algèbre (max, +) est utilisée pour représenter ce type de systèmes où les relations entre les dates de début des activités nécessitent l'utilisation des opérateurs maximum et addition. Afin d'utiliser l'algèbre (max, +) pour l'ordonnancement des systèmes HVLV, il est indispensable de résoudre un problème de conflit et d'optimisation sous contraintes dans cette algèbre. D'abord, nous avons développé dans ces travaux de recherche un modèle d'ordonnancement (max, +) pour les systèmes HVLV dans lequel des variables de décision ont été introduites afin de résoudre le problème de conflit entre les opérations exécutées sur les machines. Ensuite, nous avons amélioré le modèle proposé pour tenir compte de la maintenance préventive. Deux types de maintenance ont été considérés : Maintenance Périodique Répétitive (MPR) et Maintenance Flexible Périodique (MFP). Dans les deux cas, un problème d'ordonnancement non-linéaire sous contraintes a été résolu afin de minimiser certains critères de performance. Enfin, la méthodologie proposée a été validée par simulation, sur des systèmes HVLV complexes de type job-shop.