Show simple item record

dc.contributor.advisorClautiaux, François
dc.contributor.authorGUILLOT, Gaël
dc.contributor.otherBeaumont, Olivier
dc.contributor.otherDemassey, Sophie
dc.contributor.otherKedad Sidhoum, Safia
dc.contributor.otherDetienne, Boris
dc.contributor.otherAbsi, Nabil
dc.date2021-03-05
dc.identifier.urihttp://www.theses.fr/2021BORD0063/abes
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-03542005
dc.identifier.nnt2021BORD0063
dc.description.abstractDans cette thèse, nous nous intéressons à des problèmes pouvant se formuler sous la forme d’un programme dynamique et de contraintes linéaires additionnelles. Pour résoudre ces problèmes, des méthodes itératives d’agrégation de l’espace d’états ont été utilisées dans la littérature. Nous proposons un formalisme générique pour ces méthodes. Nous avons identifié une structure commune aux différentes méthodes, et mis en avant leurs ingrédients principaux. Le but de ce formalisme est d’unifier ces méthodes et de montrer les points clés pour que ces méthodes puissent être développées plus facilement pour de nouveaux problèmes. Pour permettre à ces méthodes d’être compétitives, plusieurs problématiques doivent être résolues : quelle relaxation choisir, quel espace d’état, comment raffiner la relaxation à chaque itération, quelle méthode de résolution choisir pour les relaxations, ... La difficulté de ces problématiques réside dans le fait que ces choix dépendent fortement du problème. Nous proposons des éléments qui peuvent être utilisés de manière générique, et d’autres spécifiques aux problèmes étudiés. Pour valider notre approche, nous avons appliqué l’une d’elles sur le problème de sac-à- dos temporel. La méthode Successive Sublimation Dynamic Programming a montré des résultats compétitifs avec la littérature, notamment grâce à un choix de dimension basé sur l’évolution du réseau, une énumération partielle des décisions possibles à chaque état et différents tests de dominances et de faisabilités. Nous comparons dans un deuxième temps les performances de notre implémentation générique avec une implémentation spécialisée sur ces problèmes. Enfin, ces méthodes ont été confrontées à un problème industriel moins classique : un problème d’utilisation de traitements phytosanitaires sur des vignes dans lequel les sous-problèmes peuvent être formulés comme des programmes dynamiques de grande taille.
dc.description.abstractEnIn this thesis, we are interested in problems that can be formulated in the form of a dynamic program and additional linear constraints. To solve these problems, iterative methods of state space aggregation have been used in the literature. We propose a generic formalism for these methods. We identified a common structure for the different methods, and highlighted their main ingredients. The aim of this formalism is to unify these methods and to show key points so that these methods can be developed more easily for new problems. To allow these methods to be competitive, several problems must be solved: which relaxation choose, which state space, how to refine relaxation at each iteration, which solving method to choose for the relaxations, ... The difficulty of these problems is in the fact that these choices strongly depend on the problem. We propose elements that can be used in a generic way, and others specific to the problems studied. To validate our approach, we applied one of them to the temporal knapsack problem. Successive Sublimation Dynamic Programming method has shown competitive results with the literature, notably thanks to a choice of dimension based on the evolution of the network, a partial enumeration of possible decisions at each state and different tests of dominance and feasibility. In a second step, we compare the performance of our generic implementation with a specialised implementation on these problems. Finally, these methods have been confronted with a less classical industrial problem: a problem of using phytosanitary treatments on vines in which the sub-problems can be formulated as large dynamic programmes.
dc.language.isofr
dc.subjectProgrammation linéaire en nombres entiers
dc.subjectProgrammation mathématique
dc.subjectProgrammation dynamique
dc.subject.enInteger programming
dc.subject.enCombinatorial optimization
dc.subject.enMathematical programming
dc.titleMéthodes d’agrégation et désagrégation de programmes linéaires en nombres entiers
dc.title.enAggregation and disaggregation of integer linear programs
dc.typeThèses de doctorat
dc.contributor.jurypresidentBeaumont, Olivier
bordeaux.hal.laboratoriesInstitut de mathématiques de Bordeaux
bordeaux.hal.laboratoriesRealopt
bordeaux.hal.laboratoriesInstitut national de recherche en informatique et en automatique (France). Centre de recherche Bordeaux - Sud-Ouest
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.type.institutionBordeaux
bordeaux.thesis.disciplineMathématiques appliquées et calcul scientifique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2021BORD0063
dc.contributor.rapporteurDemassey, Sophie
dc.contributor.rapporteurKedad Sidhoum, Safia
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=M%C3%A9thodes%20d%E2%80%99agr%C3%A9gation%20et%20d%C3%A9sagr%C3%A9gation%20de%20programmes%20lin%C3%A9aires%20en%20nombres%20entiers&rft.atitle=M%C3%A9thodes%20d%E2%80%99agr%C3%A9gation%20et%20d%C3%A9sagr%C3%A9gation%20de%20programmes%20lin%C3%A9aires%20en%20nombres%20entiers&rft.au=GUILLOT,%20Ga%C3%ABl&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record