Dissertations / Theses on the topic 'Dynamiques d'optimisation'

Cette these est consacree a l'etude des proprietes dynamiques des modeles dilues. Ces derniers sont des systemes de physique statistique de type champ moyen, mais dont la connectivite locale est finie. Leur etude est notamment motivee par l'etroite analogie qui les relient aux problemes d'optimisation combinatoire, la K-satisfiabilite aleatoire par exemple. On expose plusieurs approches analytiques visant a decrire le regime hors d'equilibre de ces systemes, qu'il soit du a une divergence des temps de relaxation dans une phase vitreuse, a l'absence de condition de balance detaillee pour un algorithme d'optimisation, ou a une preparation initiale dans une configuration loin de l'equilibre pour un ferromagnetique. Au cours de ces etudes on rencontrera egalement un probleme de matrices aleatoires, et une generalisation du theoreme de fluctuation-dissipation aux fonctions a n temps.

La résolution de nombreux problèmes d'automatique n'est pas couverte par les techniques disponibles actuellement. Elle nécessite des développements algorithmiques importants en optimisation, dans le domaine des inégalités matricielles non-convexes. Cette thèse met en oeuvre plusieurs approches complémentaires dans ce contexte. En premier lieu, les méthodes "spectral SDP", baseés sur l'utilisation de Lagrangiens augmentés, nous conduisent à la conception d'un logiciel, specSDP, et à la résolution d'un grand nombre de problèmes en commande : synthèse multimodèle ou structurée, contrôle d'ordre réduit. Une étude de convergence locale est également menée pour le cas classique, présageant d'évolutions positives. La deuxième approche proposée s'inspire d'une formulation non-lisse des problèmes BMI et des techniques associées. Nous exhibons, pour cette méthode, des résultats numériques probants, obtenus sur des exemples de grande dimension, qui mettent en échec les rares méthodes existantes
This thesis research area belongs to the class of nonlinear semidefinite programming, an emerging and challenging domain in optimization which is of central importance in robust control and relaxation of hard decision problems. Our contribution addresses convergence of algorithms, practical implementations and testing on applications in the field of reduced-order output feedback control. Firstly, our augmented Lagrangian-type "spectral SDP" method has shown to be extremely efficient on a variety of middle-scale BMI programs, including simultaneous, structured, or mixed H2/Hinf synthesis problems. Local convergence properties of the algorithm were studied as well, as far as classical nonlinear programs are concerned. On the other hand, we then focused on nonsmooth strategies for large bilinear matrix inequalities. Problems with up to a few thousand variables were successfully handled through this method, where alternative approaches usually give failure

Les systèmes informatiques sont de plus en plus autonomes et couplés. Le contrôle de leur comportement nécessite le développement d'algorithmes dédiés prenant en compte simultanément les problèmes auxquels ceux-ci ont à faire face et l'architecture distribuée sous-jacente de ces systèmes. Ce domaine est celui de la coordination de systèmes multiagents. Les systèmes multiagents sont persistants, ouverts et doivent gérer des problèmes évoluant dynamiquement tout en garantissant leur comportement dans un contexte opérationnel incertain. En tant que système artificiel, il est souhaitable qu'une procédure de coordination garantisse l'optimalité des décisions. En tant que système réel, il est souhaitable qu'une solution soit trouvée le plus rapidement possible. En tant que programme informatique distribué, il est souhaitable que la procédure de coordination soit capable de s'adapter aux pannes. Dans cette thèse nous abordons le problème de la coordination modélisé en tant qu'un problème d'optimisation de contraintes distribué dynamique, et utilisons les modèles graphiques comme mécanismes de base pour résoudre ceux-ci. Notre démarche consiste à étendre ces approches pour les adapter aux contraintes d'exécution des systèmes multiagents. Nos deux principales contributions sont un algorithme approché avec garantie permettant de réaliser un compromis entre optimalité et décentralisation, et un algorithme adaptant la création du modèle graphique aux caractéristiques du système multiagents et à l'ordonnancement des calculs sur celui-ci.

Les problèmes d'optimisation continue sont nombreux, en économie, en traitement de signal, en réseaux de neurones, etc. L'une des solutions les plus connues et les plus employées est l'algorithme évolutionnaire, métaheuristique basée sur les théories de l'évolution qui emprunte des mécanismes stochastiques et qui a surtout montré de bonnes performances dans la résolution des problèmes d'optimisation continue. L’utilisation de cette famille d'algorithmes est très populaire, malgré les nombreuses difficultés qui peuvent être rencontrées lors de leur conception. En effet, ces algorithmes ont plusieurs paramètres à régler et plusieurs opérateurs à fixer en fonction des problèmes à résoudre. Dans la littérature, on trouve pléthore d'opérateurs décrits, et il devient compliqué pour l'utilisateur de savoir lesquels sélectionner afin d'avoir le meilleur résultat possible. Dans ce contexte, cette thèse avait pour objectif principal de proposer des méthodes permettant de remédier à ces problèmes sans pour autant détériorer les performances de ces algorithmes. Ainsi nous proposons deux algorithmes :- une méthode basée sur le maximum a posteriori qui utilise les probabilités de diversité afin de sélectionner les opérateurs à appliquer, et qui remet ce choix régulièrement en jeu,- une méthode basée sur un graphe dynamique d'opérateurs représentant les probabilités de passages entre les opérateurs, et en s'appuyant sur un modèle de la fonction objectif construit par un réseau de neurones pour mettre régulièrement à jour ces probabilités. Ces deux méthodes sont détaillées, ainsi qu'analysées via un benchmark d'optimisation continue
The problems of continuous optimization are numerous, in economics, in signal processing, in neural networks, and so on. One of the best-known and most widely used solutions is the evolutionary algorithm, a metaheuristic algorithm based on evolutionary theories that borrows stochastic mechanisms and has shown good performance in solving problems of continuous optimization. The use of this family of algorithms is very popular, despite the many difficulties that can be encountered in their design. Indeed, these algorithms have several parameters to adjust and a lot of operators to set according to the problems to solve. In the literature, we find a plethora of operators described, and it becomes complicated for the user to know which one to select in order to have the best possible result. In this context, this thesis has the main objective to propose methods to solve the problems raised without deteriorating the performance of these algorithms. Thus we propose two algorithms:- a method based on the maximum a posteriori that uses diversity probabilities for the operators to apply, and which puts this choice regularly in play,- a method based on a dynamic graph of operators representing the probabilities of transitions between operators, and relying on a model of the objective function built by a neural network to regularly update these probabilities. These two methods are detailed, as well as analyzed via a continuous optimization benchmark

En 2002, Marek Musiela et Thaleia Zariphopoulo ont introduit la notion de {\em forward utility}, c'est à dire une utilité dynamique, progressive, cohérente avec un marché financier donné. On peut voir ce processus comme un champ aléatoire $U(t,x)$ adapté à l'information disponible, qui a chaque instant est une utilité standard (donc en particulier à la date $0$, compatible avec une famille de stratégies données $(X^{\pi})$ au sens où pour tout $t,h>0$, $ \mathbb{E}(U(t+h,X^{\pi}_{t+h})|\mathcal{F}_t)\leq U(t,X^{\pi}_t)$ et il existe un portefeuille optimal $X^*$ pour lequel l'inégalité est une égalité.\\ Les auteurs ont fait plusieurs articles sur ce sujet, montrant en particulier comment les utilités classiques, puissance, exponentielle, etc doivent être modifiées pour être des utilités dynamique progressives. Une attention limitée a été portée à l'univers d'investissement. \noindent Dans mon travail de thèse, je considère un cadre beaucoup plus général. En effet, le marché est incomplet dans le sens où un investisseur est contraint, à chaque date $t\ge 0$, de choisir ces stratégies admissibles dans des cones convexes fermés, adaptés $\K_t (X_t)$ dépendent du niveau de sa richesse $X_t$. Je considère par la suite que les champs aléatoires $U(t,x)$ évoluent selon la dynamique \begin{equation}\label{eq:champ} dU(t,x)=\beta(t,x)+\Gamma(t,x) dW_t,~U(0,.)=u(.) (\text{donnée}) \end{equation} Comme dans l'optimisation classique, (dite rétrograde puisqu'on reconstruit l'information à partir de la fin), %je montre que le terme %$\beta(t,x)$ contient, contient nécéssairement, un terme de type hamiltonien classique %modifié par la présence de la dérivée de la volatilité %$\Gamma(t,x)$ de l'utilité progressive. Et par conséquent toute utilité progressive qui % satisfait les hypothèses de régularités du lemme d'Itô-Ventzell % satisfait je me propose d'étudier les équations de type Hamilton-Jacobi-Bellman que satisfait une utilités progressive $u(t,x)$. Pour mener cette étude, j'utilise une formule d'Itô généralisée apellée la formule de Ventzell-Friedlin, qui permet d'établir la décomposition de type Itô de la composée d'un champ aléatoire avec un processus d'Itô. Je montre alors que le terme $\beta(t,x)$ contient, nécéssairement, un terme de type hamiltonien classique modifié par la présence de la dérivée de la volatilité $\Gamma(t,x)$ de l'utilité progressive. Et par conséquent toute utilité progressive qui satisfait les hypothèses de régularités du lemme d'Itô-Ventzell satisfont l' équation différentielle stochastique suivante \begin{equation}\label{EDPSU} dU(t,x)=\Big\{-xU'_{x}\, r_t dt+ \frac{1}{2U''_{xx}(t,x)}\|\prod_{\K_t(x)\sigma_t}\big(U'_{x}(t,x) \eta_t+\Gamma'_x(t,x)\big) \|^2\Big\}(t,x)\,dt\>+\Gamma(t,x)\,dW_t. \end{equation} avec comme portefeuille optimal $X^*$ le processus associé à la stratégie $\pi^*$ donnée par \begin{equation} x\pi^*(t,x)\sigma_t=- \frac{1}{U''_{xx}(t,x)}\|\prod_{\K_t(x)\sigma_t}\big(U'_{x}(t,x) \eta_t+\Gamma'_x(t,x)\big)(t,x) \end{equation} \noindent où $r$ est le taux court, $\eta$ la prime de marché, $\sigma$ la matrice de variance covariance des actifs et $ \prod_{\K_t(x)\sigma_t}$ désigne l'opérateur de projection sur le cône $\K_t(x)\sigma_t$. \\ Ce point de vue permet de vérifier que le champ aléatoire, s'il existe est compatible avec l'univers d'investissement. Cependant, la question de la convexité et de la monotonie est complexe a priori, car il n'existe pas de théorèmes de comparaison pour les équations progressives (qui sont {\em forward}), contrairement au cas des équations rétrogrades. La question de l'interprétation et du rôle de la volatilité s'avère alors être centrale dans cette étude. Contrairement au cadre général que je considère ici, M.Musiela et T.Zariphopoulo, puis C.Rogers et al se sont restreint au cas où la volatilité de l'utilité est identiquement nulle. Le processus progressif $u(t,x)$ est alors une fonction déterministe satisfaisant une EDP non linéaire, que les auteurs ont transformé en solution harmonique espace temps de l'équation de la chaleur. \\ Mon choix a été d'étudire la question de la volatilité par des techniques de changement de numéraire; ainsi, je montre la stabilité de la notion d'utilité progressive par changement de numéraire. L'avantage considérable de cette technique, comparée à la méthode classique, % Comme dans le cas % classique, le problème est compliqué par le fait que l'espace des % contraites n'est pas invariant par changement de numéraire. est le fait qu'elle permet de se ramener toujours à un marché "martingale" ($r=0$ et $\eta=0$), ce qui simplifie considérablement les équations et les calculs. La dérivée de la volatilité apparaît alors comme une prime de risque instantanée que le marché introduit, et qui dépend du niveau de la richesse de l'investisseur. Ce point de vue nouveau permet de répondre à la question de l'interprétation de la volatilité de l'utilité. Dans la suite, j'étudie le problème dual et je montre que la transformée de {\em Fenchel} $\tU$ de la fonction concave $U(t,x)$ est un champ markovien lui aussi satisfaisant la dynamique \begin{eqnarray}\label{EDPSDuale'} d\tilde{U}(t,y)=\left[\frac{1}{2\tU_{yy}''}(\|\tilde{\Gamma}'\|^2-\|\prod_{\K_t(-\tU_y'(t,y))\sigma_t}(\tilde{\Gamma}^{'}_y-y\eta_t)\|^2) +y\tU_{y}' r_t\right](t,y)dt +\tilde{\Gamma}(t,y)dW_t,~~\tilde{\Gamma}(t,y)=\Gamma(t,\tU_y'(t,y)). \end{eqnarray} À partir de ce résultat je montre que le problème dual admet une unique solution $Y^*$ dans la volatilté $\nu^*$ est donnée par \begin{equation} y\nu^*(t,y)= -\frac{1}{\tU_{yy}''}\Big(\tilde{\Gamma}'+y\eta_t-\prod_{\K_t(-\tU_y')\sigma_t}(\tilde{\Gamma}^{'}_y-y\eta_t)\Big)(t,y). \end{equation} \noindent Ce ci permettra d'établir les identités clé suivantes: \begin{eqnarray} &Y^*(t,(U_x')^{-1}(0,x))=U'_x(t,X^*(t,x)) \label{A}\\ &(\Gamma'_x+U'_x\eta)(t,x)=(xU''(t,x)\pi^*(t,x)\sigma_t+\nu^*(U_x'(t,x))\label{B}. \end{eqnarray} % Remarquons que le terme $(\Gamma'_x+U'_x\eta)$ se décompose de manière unique sous forme % de sa projection sur le cone $\K\sigma$, qui est la stratégie optimale, et la projection sur le cone dual $\K^* \sigma$, % qui est la volatilité du processus optimal dual. Mais notre but est deux termes projétés su comme la projection % Á partir de la première identité nous savons que $U'_x(t,X^*(t,x))$ n'est autre que le processus optimal dual %Á ce stade rapellons que le but de cette étude est de carracteriser les utilités progressives. La question par la suite est la suivante: peut-on caractériser l'utilité $U(t,x)$ pour tout $x>0$ à partir de la première identité? Ceci peut paraître trop demander car nous cherchons à caractériser le champ $U$ connaissant seulement son comportement le long de l'unique trajectoire optimale $X^*$. Cependant, la réponse à cette question s'avère être positive et assez simple. En effet, notons par $\Y(t,x):=Y^*(t,(U_x')^{-1}(0,x))$, et supposons que le flot stochastique $X^*$ soit inversible, $\X$ désigne son inverse. Alors, en inversant dans (\ref{A}), je déduis que $U_x'(t,x)=\Y(t,\X(t,x))$. En intégrant par rapport à $x$, j'obtiens que $U(t,x)=\int_0^x\Y(t,\X(t,z))dz$, ce qui prouve le théorème suivant: \begin{theo} Sous des hypothèses de régularités et d'inversion du flot $X^*$, les processus $U$ définis par $U(t,x)=\int_0^x\Y(t,\X(t,z))dz$ sont des utilités progressives solutions de l'EDP stochastique (\ref{EDPSU}). \end{theo} % %\noindent Inversement, je montre le théorème d'EDP stochastique suivant: \begin{theo} Soit $U$ un champ aléatoire solutions de l'EDP stochastique (\ref{EDPSU}). En utilisant la décompostion (\ref{B}), si les EDS suivantes \begin{eqnarray*} & dX^*_t(x)=X^*_t(x)(r_tdt+\pi^*(t,X^*_t(x))\sigma_t(dW_t+\eta_tdt)),X^*_0(x)=x ~\\ & dY^*_t(y)=Y^*_t(y)(-r_tdt+\nu^*(t,Y^*_t(y))dW_t),~Y^*_0(y)=y \end{eqnarray*} admettent des solutions fortes unique et monotonnes, alors, en notant par $ \Y(t,x):=Y^*(t,(U_x')^{-1}(0,x))$ et par $\X$ le flot inverse de $X$, on obtient que $U(t,x)= \int_0^x\Y(t,\X(t,z))dz$. Si de plus $X^*$ et $Y^*$ sont croissants, $U$ est concave. \end{theo} \noindent %Dans ce travail, je considère toujours un marché incomplet, Dans une seconde partie de ce travail, je me place dans un cadre beaucoup plus général dans le sens où les actifs sont supposés être cadlag locallement bornés, et par conséquent la filtration n'est plus une filtration brownienne. Je remplace les contraintes de type cône convexe par des contraintes plus générales de type ensemble convexe. Le but de cette partie est de caractériser toutes les utilités progressives avec le minimum d'hypothèses, notamment avec moins d'hypothèses de régularités sur les champs aléatoires $U$. Je ne suppose plus que $U$ est deux fois différentiable et par conséquent je ne peut plus appliquer le lemme d'Itô-Ventzell. L'approche est alors différente: je commence par établir des conditions d'optimalité sur le processus de richesses optimale ainsi que le processus optimal dual, et ce en utilisant des méthodes d'analyse. En utilisant ces résultats je démontre, par des éléments d'analyse, la convexité ainsi que les conditions d'optimalités que toutes les utilités progressives générant une richesse croissante est de la forme $\int_0^x\Y(t,\X(t,z))dz$ avec $\Y$ : $\Y X$ est une surmartingale pour toute richesse $X$ et une martingale si $X=X^*$.

D'importants efforts de recherche ont été investis dans l'industrie automobile sur les nouveaux carburants et les nouvelles chaînes de traction hybride électrique afin de réduire les émissions de carbone des véhicules. La consommation de carburant de ces groupes motopropulseurs hybrides dépend des performances du convertisseur d'énergie utilisé, des besoins énergétiques du véhicule, ainsi que de la stratégie de gestion énergétique déployée à bord. Cette thèse examine le potentiel de nouveaux convertisseurs d'énergie comme substitut du moteur thermique à combustion interne (ICE). Les systèmes de turbines à gaz sont considérés comme des convertisseurs d'énergie potentiel pour les chaînes de traction hybride série (SHEV), car ils offrent de nombreux avantages intrinsèques à l'automobile, tels que la capacité de fonctionner avec plusieurs carburants, la compacité, la réduction du nombre de pièces mobiles, la réduction du bruit et des vibrations. Une analyse exergo-technologique explicite est proposée pour identifier les configurations thermodynamiques réalistes. Une étude préconceptionnelle a été réalisée pour déterminer les rapports puissance/poids de ces systèmes. Un modèle SHEV est développé et les composants du groupe motopropulseur sont dimensionnés en fonction des critères de performance du véhicule. Des simulations de consommation sont effectuées sur le cycle d’homologation WLTC, en prenant en compte les besoins en énergie électrique et thermique du véhicule en plus des besoins en énergie mécanique, et en utilisant une méthode innovante d'optimisation comme stratégie de gestion de l'énergie. Le cycle turbine à gaz (avec compression refroidie, régénérateur et réchauffe durant la détente (IRReGT)) est priorisé car il offre un rendement et une densité de puissance plus élevés ainsi qu'une consommation de carburant réduite par rapport aux autres systèmes investigués. De plus, un modèle dynamique a été développé et des simulations ont été effectuées pour tenir compte de la surconsommation de carburant pendant les phases transitoires du démarrage. Des essais ont également été mis en œuvre sur certains sous-systèmes du cycle IRReGT identifié. Les résultats montrent une amélioration de la consommation de carburant avec l'IRReGT comme groupe auxiliaire de puissance par rapport à l'ICE. Par conséquent, le système IRReGT sélectionné présente un potentiel, non négligeable, qui remplacerait le moteur thermique à combustion interne dans les futures chaînes de traction hybride électriques
Significant research efforts have been invested in the automotive industry on alternative fuels and new hybrid electric powertrain in attempt to reduce carbon emissions from passenger cars. Fuel consumption of these hybrid powertrains strongly relies on the energy converter performance, the vehicle energetic needs, as well as on the energy management strategy deployed on-board. This thesis investigates the potential of new energy converters as substitute of actual internal combustion engine in automotive powertrain applications. Gas turbine systems is identified as potential energy converter for series hybrid electric vehicle (SHEV), as it offers many automotive intrinsic benefits such as multi-fuel capability, compactness, reduced number of moving parts, reduced noise and vibrations among others. An exergo-technological explicit analysis is conducted to identify the realistic GT-system thermodynamic configurations. A pre-design study have been carried out to identify the power to weight ratios of those systems. A SHEV model is developed and powertrain components are sized considering vehicle performance criteria. Energy consumption simulations are performed on the worldwide-harmonized light vehicles test cycle (WLTC), which account for the vehicle electric and thermal energy needs in addition to mechanical energy needs, using an innovative bi-level optimization method as energy management strategy. The intercooled regenerative reheat gas turbine (IRReGT) cycle is prioritized, offering higher efficiency and power density as well as reduced fuel consumption compared to the other investigated GT-systems. Also a dynamic model was developed and simulations were performed to account for the over fuel consumption during start-up transitory phases. Tests were also performed on some subsystems of the identified IRReGT-system. Results show improved fuel consumption with the IRReGT as auxiliary power unit (APU) compared to ICE. Consequently, the selected IRReGT-system presents a potential for implementation on futur SHEVs

La théorie de la complexité distingue les problèmes que l'on sait résoudre en un temps polynomial en la taille des données (que l'on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l'état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l'on peut qualifier de déraisonnable). C'est pour cette raison que la communauté scientifique s'est tournée vers les algorithmes (polynomiaux) d'approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d'approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d'approximation de k si la taille de toute solution pouvant être retournée par l'algorithme est inférieure ou égale à k fois la taille de la solution optimale). Dans la littérature, on en vient à considérer qu'un algorithme est plus performant qu'un autre lorsqu'il possède un plus petit rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Mes travaux de thèse ont pour objet de mieux "capturer" le comportement des algorithmes d'approximation en allant plus loin que le simple rapport d'approximation en pire cas, et ce sur deux problèmes distincts : I. Le problème du Vertex Cover En montrant que les performances moyennes d'un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l'algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l'optimum lorsque n tend vers l'infini. En évaluant les performances moyennes d'un algorithme. Nous avons prouvé que l'algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d'approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n'importe quel graphe. Ce résultat, combiné à d'autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d'approximation en pire cas . En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies. On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation (fonction du degré max. du graphe). Tous ces résultats montrent que le rapport d'approximation en pire cas n'est pas toujours suffisant pour caractériser l'intégralité de la qualité d'un algorithme et que d'autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour. II. Le problème de la connexion de groupes dynamiques dans les réseaux Nous avons analysé un processus de mise-à-jour d'un arbre connectant dans un réseau un groupe que les membres peuvent rejoindre ou quitter à tout moment. Notre processus possède de bonnes propriétés : il est simple à implémenter et il garantit, après chaque opération d'ajout ou de retrait, que le diamètre de l'arbre est au plus 2 fois l'optimal. Cependant, pour obtenir cette garantie, nous devons autoriser la reconstruction totale de l'arbre lorsque le membre identifié comme sa racine quitte le groupe. Ces étapes de reconstruction sont très coûteuses et nous cherchons donc à en évaluer le nombre. Des travaux précédents montraient que dans le pire cas, il faut reconstruire (quasiment) à chaque étape pour conserver la garantie sur le diamètre. Nous montrons dans cette thèse (en utilisant les marches aléatoires, etc.) que, en fonction de certains paramètres du problèmes (comme les probabilités associées aux opérations d'ajout et de retrait), l'espérance du nombre de reconstructions est soit logarithmique en le nombre d'évènements (ajout ou retrait), soit constant. Ce résultat montre que le comportement moyen est très bon (malgré un pire cas très défavorable) et que notre processus de mise-à-jour peut être une solution viable en pratique.

Le design représente une étape indispensable à la conception, le déploiement et l'extension des réseaux radiomobiles. La nature dynamique de l'environnement des réseaux radiomobiles rend difficile l'établissement des critères de performance liés à la robustesse et à l'évolutivité des réseaux. La contribution de cette thèse se situe sur deux plans. Au niveau de la modélisation nous proposons plusieurs modèles de planification de fréquences tenant compte de l'évolution court et moyen terme du trafic. Comme nous présentons un modèle de planification des capacités cellulaires bi-critères. Sur un plan algorithmique, nous étudions plusieurs techniques d'optimisation dynamique et multicritère basées sur une hybridation des techniques de recherche tabou et d'algorithmes génétiques. Des tests sont effectués sur des réseaux fictifs et réels afin de valider les modèles et les techniques proposés
Cellular network design is a crucial task during the conception, the deployment and the extension of radio phone network. The dynamic aspect of cellular network environnent makes difficult the establishment of performance criteria related to the robustness and the upgradeability of networks. The contribution of this thesis is two folds. On the modelling level, we propose several models for frequency planning taking into account short, medium and long term traffic evolution. We present also a bi-criteria model for cell capacity planning. On the algorithmic level, we study several dynamic and multi-criteria optimization techniques based on hybridization of tabu search and genetic algorithm heuristics. Tests are carried out on both fictitious and real word problems in order to validate proposed models and techniques

Les procédés électrochimiques occupent une part non-négligeable dans l'industrie chimique. Des études préliminaires montrent cependant que le mode de fonctionnement traditionnel de ces procédés (à potentiel ou à courant constant) n'est pas toujours le meilleur. Elles encouragent à envisager l'amélioration du fonctionnement des procédés électrochimiques par l'utilisation des méthodes d'optimisation dynamique. L’étude présentée dans cette thèse propose une méthodologie de l'optimisation dynamique et de la commande optimale dans le cas des procédés électrochimiques discontinus. On cherche ainsi à formuler et résoudre les problèmes d'optimisation du fonctionnement dynamique des réacteurs électrochimiques, à analyser les différentes sensibilités des paramètres du modèle et à appliquer les profils optimaux de commande en boucle fermée dans des conditions expérimentales aussi réalistes que possibles. La méthodologie est appliquée à différents problèmes électrochimiques tels que la minimisation de la consommation d'énergie électrique, la maximisation du rendement, de la sélectivité ou encore la minimisation du temps opératoire. Toutes les méthodes d'optimisation utilisées sont fondées sur le principe du maximum. Un inventaire non exhaustif des techniques de résolution de problèmes d'optimisation dynamique et leurs principales caractéristiques sont ainsi présentées. En intégrant au problème, des contraintes physiques, ces méthodes fournissent des conditions optimales de fonctionnement réalistes. Les performances de l'optimisation dynamique sont comparées à celles résultant des meilleures conditions de fonctionnement statiques. Les améliorations entre le mode de fonctionnement optimisé et le meilleur mode usuel peuvent s'élever à plusieurs dizaine de pourcent. Différentes formes de l'analyse de la sensibilité des paramètres du modèle soulignent la validité des résultats optimaux dans des conditions opératoires qui diffèrent de celles idéalement représentée dans le modèle des réacteurs considérés. Pour la mise en œuvre de la commande optimale, des techniques de reconstruction de l'état et une loi de commande en boucle fermée ont été mis au point.

Les algorithmes convexes de résolution pour les régressions linéaires parcimonieuses possèdent de bonnes performances pratiques et théoriques. Cependant, ils souffrent tous des dimensions du problème qui dictent la complexité de chacune de leur itération. Nous proposons une approche pour réduire ce coût calculatoire au niveau de l'itération. Des stratégies récentes s'appuyant sur des tests d'élimination de variables ont été proposées pour accélérer la résolution des problèmes de régressions parcimonieuse pénalisées tels que le LASSO. Ces approches reposent sur l'idée qu'il est profitable de dédier un petit effort de calcul pour localiser des atomes inactifs afin de les retirer du dictionnaire dans une étape de prétraitement. L'algorithme de résolution utilisant le dictionnaire ainsi réduit convergera alors plus rapidement vers la solution du problème initial. Nous pensons qu'il existe un moyen plus efficace pour réduire le dictionnaire et donc obtenir une meilleure accélération : à l'intérieur de chaque itération de l'algorithme, il est possible de valoriser les calculs originalement dédiés à l'algorithme pour obtenir à moindre coût un nouveau test d'élimination dont l'effet d'élimination augmente progressivement le long des itérations. Le dictionnaire est alors réduit de façon dynamique au lieu d'être réduit de façon statique, une fois pour toutes, avant la première itération. Nous formalisons ce principe d'élimination dynamique à travers une formulation algorithmique générique, et l'appliquons en intégrant des tests d'élimination existants, à l'intérieur de plusieurs algorithmes du premier ordre pour résoudre les problèmes du LASSO et Group-LASSO
Applications in signal processing and machine learning make frequent use of sparse regressions. Resulting convex problems, such as the LASSO, can be efficiently solved thanks to first-order algorithms, which are general, and have good convergence properties. However those algorithms suffer from the dimension of the problem, which impose the complexity of their iterations. In this thesis we study approaches, based on screening tests, aimed at reducing the computational cost at the iteration level. Such approaches build upon the idea that it is worth dedicating some small computational effort to locate inactive atoms and remove them from the dictionary in a preprocessing stage so that the regression algorithm working with a smaller dictionary will then converge faster to the solution of the initial problem. We believe that there is an even more efficient way to screen the dictionary and obtain a greater acceleration: inside each iteration of the regression algorithm, one may take advantage of the algorithm computations to obtain a new screening test for free with increasing screening effects along the iterations. The dictionary is henceforth dynamically screened instead of being screened statically, once and for all, before the first iteration. Our first contribution is the formalisation of this principle and its application to first-order algorithms, for the resolution of the LASSO and Group-LASSO. In a second contribution, this general principle is combined to active-set methods, whose goal is also to accelerate the resolution of sparse regressions. Applying the two complementary methods on first-order algorithms, leads to great acceleration performances

Cette thèse explore certains problèmes liés aux grandes matrices aléatoires et aux statistiques en grande dimension, motivés par la nécessité d'améliorer notre compréhension de l'apprentissage profond. L'apprentissage des réseaux neuronaux profonds implique la résolution de problèmes d'optimisation non convexes, à grande échelle et en grande dimension, qui devraient être théoriquement intraitables mais sont étonnamment réalisables en pratique. Afin de comprendre ce paradoxe, nous étudions des modèles solvables qui concilient pertinence pratique et rigueur mathématique. Les matrices aléatoires et les statistiques en grande dimension jouent un rôle central dans ces travaux, en raison du grand volume de données et de la grande dimensionnalité inhérents à ces modèles. D'abord, nous considérons le modèle des "random features", un réseau neuronal à deux couches avec des poids fixes et aléatoires dans la première couche et des poids apprenables dans la deuxième. Notre étude se concentre sur le spectre asymptotique de la matrice du noyau conjuguée YY* avec Y= f(WX), où W et X sont des matrices aléatoires rectangulaires avec des entrées i.i.d., et f est une fonction d’activation non linéaire appliquée élément par élément. Nous étendons les résultats obtenus précédemment sur les distributions à queues légères pour W et X en considérant deux nouveaux contextes. Premièrement, nous étudions le cas du biais additif Y =f (WX + B), où B est une matrice aléatoire gaussienne indépendante de rang un, ce qui modélise de plus près les architectures de réseaux neuronaux rencontrées en pratique. Pour obtenir les asymptotiques de la densité spectrale empirique, nous utilisons la méthode du résolvant via l'expansion des cumulants. Deuxièmement, nous analysons le cas où W a des entrées à queues lourdes, X reste à queues légères, et f est une fonction lisse, bornée et impaire. Nous montrons que les poids à queues lourdes induisent des corrélations beaucoup plus fortes entre les entrées de Y, ce qui se traduit par un comportement spectral inédit. Cette analyse s’appuie sur la méthode des moments via la théorie des probabilités de trafic. Ensuite, nous abordons l’ACP tensorielle (analyse en composantes principales), un problème d’inférence en grande dimension qui étudie la difficulté computationnelle d’estimer un vecteur signal inconnu à partir d’observations tensorielles bruitées via le maximum de vraisemblance. L’ACP tensorielle sert de prototype pour comprendre l’optimisation non convexe en grande dimension via des méthodes basées sur le gradient. Cette compréhension peut être abordée sous deux angles : la complexité topologique du paysage d’optimisation et les dynamiques d’optimisation des méthodes du premier ordre. Concernant la complexité du paysage, nous étudions la "complexité annealed" des polynômes gaussiens aléatoires sur la sphère unitaire de dimensions N en présence de polynômes déterministes dépendant de vecteurs unitaires fixes et de paramètres externes. En utilisant la formule de Kac-Rice et les asymptotiques du déterminant pour une perturbation de rang fini des matrices de Wigner, nous dérivons des formules variationnelles pour les asymptotiques exponentielles du nombre moyen de points critiques et de maxima locaux. Concernant les dynamiques d’optimisation en grande dimension, nous analysons la descente de gradient stochastique (SGD) et le flux de gradient (GF) pour l’ACP tensorielle avec plusieurs directions cachées. Nous montrons que SGD atteint le même seuil computationnel que dans le cas r=1, mais GF nécessite plus d’échantillons pour récupérer toutes les directions. Les signaux sont récupérés via un processus d’"élimination séquentielle" où les corrélations croissent successivement selon un ordre déterminé par les conditions initiales et les rapports signal-bruit (SNR). Dans le cas matriciel (p=2), des SNR bien séparés permettent une récupération exacte, tandis que des SNR égaux mènent à la récupération du sous-espace engendré
This thesis explores some problems in random matrix theory and high-dimensional statistics motivated by the need to improve our understanding of deep learning. Training deep neural networks involves solving high-dimensional, large-scale, and nonconvex optimization problems that should, in theory, be intractable but are surprisingly feasible in practice. To understand this paradox, we study solvable models that balance practical relevance with rigorous mathematical analysis. Random matrices and high-dimensional statistics are central to these efforts due to the large datasets and high dimensionality inherent in such models. We first consider the random features model, a two-layer neural network with fixed random weights in the first layer and learnable weights in the second layer. Our focus is on the asymptotic spectrum of the conjugate kernel matrix YY* with Y = f(WX), where W and X are rectangular random matrices with i.i.d. entries and f is a nonlinear activation function applied entry-wise. We extend prior results on light-tailed distributions for W and X by considering two new settings. First, we study the case of additive bias Y = f(WX + B), where B is an independent rank-one Gaussian random matrix, closer modeling the neural network architectures encountered in practice. To obtain the asymptotics for the empirical spectral density we follow the resolvent method via the cumulant expansion. Second, we investigate the case where W has heavy-tailed entries, X remains light-tailed, and f is a smooth, bounded, and odd function. We show that heavy-tailed weights induce much stronger correlations among the entries of Y, resulting in a novel spectral behavior. This analysis relies on the moment method through traffic probability theory. Next, we address the tensor PCA (Principal Component Analysis) problem, a high-dimensional inference task that investigates the computational hardness of estimating an unknown signal vector from noisy tensor observations via maximum likelihood estimation. Tensor PCA serves as a prototypical framework for understanding high-dimensional nonconvex optimization through gradient-based methods. This understanding can be approached from two perspectives: the topological complexity of the optimization landscape and the training dynamics of first-order optimization methods. In the context of landscape complexity, we study the annealed complexity of random Gaussian homogeneous polynomials on the N-dimensional unit sphere in the presence of deterministic polynomials that depend on fixed unit vectors and external parameters. Using the Kac-Rice formula and determinant asymptotics for spiked Wigner matrices, we derive variational formulas for the exponential asymptotics of the average number critical points and local maxima. Concerning the optimization dynamics in high dimensions, we study stochastic gradient descent (SGD) and gradient flow (GF) for the multi-spiked tensor model, where the goal is to recover r orthogonal spikes from noisy tensor observations. We show that SGD achieves the same computational threshold than in the single-spike case. In contrast, GF requires more samples to recover all spikes, resulting in a suboptimal threshold compared to SGD. Our analysis shows that spikes are recovered through a "sequential elimination" process: once a correlation exceeds a critical threshold, competing correlations become sufficiently small, allowing the next correlation to grow and become macroscopic. The order of recovery depends on initial values of correlations and the corresponding signal-to-noise ratios (SNRs), leading to recovery of a permutation of the spikes. In the matrix case (p=2), sufficiently separated SNRs allow exact recovery of the spikes, while equal SNRs lead to recovery of the subspace spanned by the spikes

Dans le contexte climatique et énergétique actuel, des solutions doivent être trouvées pour remplacer progressivement l'usage des énergies fossiles. Le solaire thermique est une ressource disposant d'un fort potentiel encore trop peu exploité en France à l'échelle industrielle. Dans ce contexte, les grandes installations solaires thermiques sont de plus en plus étudiées. Actuellement, la majorité des études porte sur l'optimisation du dimensionnement des centrales en se basant sur des stratégies de pilotage standard. Le présent manuscrit propose une méthodologie de résolution mathématique pour la simulation et l'optimisation dynamique d'une centrale solaire thermique. Ce type d'optimisation permet de prendre en compte la dynamique de ce système, et en particulier la dynamique lente d'un stockage d'énergie thermique, et est réalisée en exploitant les degrés de liberté du problème tel qu'on le pose. Ainsi, en laissant libres certains paramètres de design, l'optimisation dynamique permet d'optimiser simultanément le fonctionnement et le dimensionnement de la centrale. Les différents éléments d'une centrale solaire thermique (champ solaire, échangeur de chaleur, stockage thermique, pompes, canalisations) sont modélisés et forment un système d'équations algébro-différentielles. Nous détaillons la méthode de collocation orthogonale sur éléments finis permettant de discrétiser ces équations et d'obtenir ainsi un système comprenant uniquement des équations algébriques. Différents modèles sont confrontés à des données expérimentales issues de la centrale de Condat-sur-Vézère et leur précision est quantifiée. Le développement d'une méthode par simulations et initialisations successives nous a permis de réaliser la simulation dynamique d'une centrale solaire thermique. Cependant, certaines contraintes de fonctionnement (règles de pilotage nécessaires pour saturer les degrés de liberté) sont difficiles à formuler de façon cohérente et implémentable dans le logiciel GAMS utilisé dans ces travaux. L'intérêt de l'optimisation dynamique est de tirer profit des degrés de liberté du problème afin de minimiser/maximiser une fonction objectif (en respectant les contraintes du problème) sans avoir à formuler des contraintes pour saturer les variables d'intérêt. Un premier problème d'optimisation dynamique a été formulé puis résolu suivant une stratégie orientée-équation. Sur un horizon de temps de cinq jours et avec un dimensionnement de centrale fixé, nous avons maximisé les bénéfices liés à la vente de chaleur solaire à un consommateur en optimisant le fonctionnement de la centrale. Cela a notamment fait ressortir des stratégies parfois contre-intuitives permettant une amélioration significative de la fonction objectif par rapport à des pilotages plus « classiques ». En particulier, l'utilisation d'une inclinaison dynamique des capteurs s'est montrée efficace, d'une part, pour augmenter l'énergie captée par le champ solaire et, d'autre part, pour gérer d'éventuelles surchauffes en défocalisant les capteurs par rapport à la trajectoire de captation maximale. L'utilisation d'un stockage thermique a également été utile pour permettre le déphasage entre la production et la demande. La formulation d'un second problème d'optimisation, sur un horizon de temps d'un an, a permis de minimiser le coût moyen de la chaleur solaire vendue au consommateur (sur la durée du projet) en déterminant le dimensionnement optimal de la centrale et les profils temporels optimaux des variables de fonctionnement en fonction de la courbe de charge. Des difficultés ont été rencontrées, notamment pour conserver un fonctionnement cohérent sur la période d'optimisation. Finalement, nous avons listé un certain nombre de pistes qui pourraient potentiellement améliorer les résultats obtenus
In the current climate and energy context, solutions must be found to gradually replace the use of fossil fuels. Solar thermal energy is a resource with great potential that is still insufficiently exploited in France on an industrial scale. In this context, large solar thermal installations are increasingly studied. Currently, a majority of studies focus on optimizing the sizing of the plants based on standard operating strategies. This manuscript offers a mathematical resolution methodology for the simulation and dynamic optimization of a solar thermal plant. This type of optimization makes it possible to take into account the dynamics of this system and in particular the slow dynamics of a thermal energy storage. It is carried out by exploiting the degrees of freedom of the problem. By leaving certain design parameters free, dynamic optimization makes it possible to optimize the operation and sizing of the plant simultaneously.The different elements of a solar thermal plant (solar field, heat exchanger, thermal energy storage, pumps, pipes) are modeled and form a Differential Algebraic Equation system. We have described the orthogonal collocation method which allows to discretize these equations and thus, to obtain a system comprising only algebraic equations. Different models are confronted with experimental data from a plant located in Condat-sur-Vézère (France). Their precision is quantified. The development of a method by successive simulations and initializations allowed us to carry out the dynamic simulation of a solar thermal plant. However, certain operating constraints (control rules necessary to saturate the degrees of freedom) are difficult to formulate in a coherent and implementable way in the GAMS software used in this work. The interest of using dynamic optimization is to take advantage of the degrees of freedom of the problem in order to minimize / maximize an objective function (while respecting the constraints of the problem) without having to formulate constraints to saturate them.A first dynamic optimization problem was formulated and then solved, using an equation-oriented strategy. Over a five-day time horizon and with a fixed plant sizing, we have maximized the benefits from the sale of solar heat to a consumer by optimizing the operation of the plant. This notably brought to light counter-intuitive operating strategies allowing a significant improvement of the objective function compared to more standard strategies. In particular, the use of a dynamic inclination of the flat-plate collectors (as with a solar tracking device) has proved effective, on the one hand, to increase the energy captured by the solar field and, on the other hand, to handle possible overheating by defocusing the collectors from the maximum energy capture trajectory. The use of a thermal energy storage was also useful to allow the phase difference between production and demand.The formulation of a second optimization problem, over a time horizon of one year, made it possible to minimize the average cost of solar heat sold to the consumer (over the duration of the project) by determining the optimal sizing of the plant and the optimal time profiles of the operating variables as a function of the load curve. Difficulties have been encountered, in particular to maintain consistent operation over the optimization period. Finally, we listed a number of leads that could potentially improve the results obtained

Cette thèse s’intéresse au cas d’un port maritime dans lequel des terminaux à conteneurs coopèrent afin de fournir un meilleur service global. Pour coordonner les opérations entre les terminaux, un modèle et plusieurs méthodes de résolution sont proposés. L’objectif est de minimiser les temps de rotation des navires aux longs cours, des navires caboteurs, des barges fluviales et des trains. Une solution au modèle fournit une affectation des véhicules de transport de conteneurs aux terminaux, ce qui inclue les camions, ainsi qu’une allocation de ressources et des intervalles temporels pour leurs prises en charge et pour celles de leurs conteneurs. Pour obtenir des solutions au modèle, une formulation du problème comme un programme linéaire en variables mixtes est proposée, ainsi que plusieurs heuristiques basées sur la programmation mathématique. Une méthode de planification en horizon glissant est introduite pour la gestion dynamique avec prise en compte des incertitudes. Des expériences numériques sont conduites avec des milliers d’instances réalistes variées, dont les résultats indiquent la viabilité de notre approche. Des résultats démontrent qu’autoriser la coopération entre terminaux augmente significativement la performance du système
This thesis deals with the case of a maritime port in which container terminals are cooperating to provide better global service. In order to coordinate operations between the terminals, a model and several solving methods are proposed. The objective is to minimize turnaround times of mother and feeder vessels, barges and trains. A solution to the model provides an assignment of container-transport vehicles to the terminals, including trucks, as well as an allocation of resources and time intervals to handle them and their containers. To obtain solutions to the model, a mixed-integer programming formulation is provided, as well as several mathematical programming based heuristics. A rolling horizon framework is introduced for dynamic management under uncertainty. Numerical experiments are conducted on thousands of various realistic instances. Results indicate the viability of our approach and demonstrate that allowing cooperation between terminals significantly increases the performance of the system

Les reseaux optiques a multiplexage en longueur d'onde (reseaux WDM) offrent la possibilite de satisfaire economiquement la demande croissante de services de telecommunications. Ces reseaux, bases sur des normes en cours de developpement a l'UIT-T, l'IETF et l'OIF, seront tres probablement deployes dans les 5 ou 6 annees a venir. De nouveaux problemes d'optimisation apparaissent en relation avec ces reseaux pour plusieurs raisons. En premier lieu, les couts pour les equipements optiques sont encore mal connus en raison du caractere recent des technolologies utilisees pour ces reseaux. Deuxiemement, l'incertitude de la demande, liee notamment a la concurrence dans le marche des telecommunications et a l'adoption massive de nouvelles applications informatiques, rendent difficile le dimensionnement des reseaux. Enfin, les nouvelles technologies optiques conduisent a de nouvelles contraintes fonctionnelles qui doivent etre prises en compte dans la conception et le dimensionnement du reseau. Nous etudions les problemes d'optimisation lies a l'ingenierie d'un reseau de transport optique. L'ingenierie de reseaux concerne la configuration des ressources reseau existantes pour satisfaire des demandes de trafic connues. A la difference de la planification des reseaux et de l'ingenierie de trafic, les problemes d'ingenierie de reseaux sont pertinents a des echelles de temps allant de l'heure a la semaine. A cette echelle de temps, l'evolution dynamique de la charge de trafic represente un element important qui doit etre pris en compte dans la configuration du reseau. Par ailleurs, la periodicite de l'evolution de la charge de trafic observee dans des reseaux de transport operationnels suggere que le trafic peut etre modelise de facon deterministe. Nous proposons un modele de trafic dynamique deterministe appele Scheduled Lightpath Demand (SLD). Une SLD est une demande de connexion representee par un quintuplet (s, d, n, alpha, omega) ou s et d representent les noeuds source et destination de la demande, n represente le nombre de connexions requises et alpha et omega les dates d'etablissement (set-up) et de fin (tear-down) des connexions demandees. Le modele decrit la distribution spatiale et temporelle d'un ensemble de connexions et, par son caractere deterministe, facilite l'utilisation de techniques d'optimisation combinatoire pour la resolution de problemes d'optimisation reseau. Nous etudions trois problemes d'optimisation reseau impliquant ce modele de trafic : - le probleme du routage et de l'affectation de longueurs d'onde (RWA) pour des SLDs dans un reseau a commutation de longueurs d'onde. Le probleme du routage est formule sous forme d'un probleme d'optimisation combinatoire avec deux fonctions objectif possibles. Nous proposons une methode par separation et evaluation (Branch & Bound ou B&B, en anglais) et un algorithme de Recherche Tabou (RT) pour le calcul de solutions exactes et approchees, respectivement. Le probleme de l'affectation de longueurs d'onde est formule sous forme d'un probleme de coloration de graphes. Nous utilisons un algorithme glouton existant pour trouver des solutions approchees. - le probleme de protection pour des SLDs dans un reseau a commutation de longueurs d'onde. Le probleme consite a determiner pour chaque demande un couple de chemins disjoints de telle sorte que le nombre de canaux primaires et de protection soit minimal. Nous proposons une technique de reutilisation de canaux pour reduire le nombre de canaux primaires et une technique de multiplexage de protection pour reduire le nombre de canaux dedies a la protection. Le probleme est formule sous forme d'un probleme d'optimisation combinatoire. Nous proposons un algorithme de type recuit simule (RS) pour calculer des solutions approchees. - Finalement, nous etudions le probleme de routage et d'agregation des SLDs (RAS) dans un reseau avec deux niveaux de granularite de commutation. Nous considerons un reseau dont les noeuds disposent d'un commutateur de longueurs d'onde et d'un commutateur de bandes. Le probleme est formule sous forme d'un probleme d'optimisation combinatoire. Nous proposons un algorithme Tabou parallele pour le calcul de solutions approchees. Nous definisons les conditions sous lesquelles un reseau avec deux niveax de granularite de commutation est plus economique qu'un reseau a commutation de longueurs d'onde.

L'analyse du comportement vibratoire est essentielle pour la conception optimale de certaines structures assemblées complexes. L'intégration de phénomènes non linéaires, en particulier aux interfaces entre les sous-structures, permet la réalisation de simulations numériques haute fidélité. Cependant, le coût de calcul rend inenvisageable l'utilisation de méthodes classiques d'optimisation paramétrique globale sur des structures non linéaires industrielles. L'objectif de ces travaux est d'étudier une stratégie complète permettant la conduite d'une optimisation paramétrique sous contraintes, en dynamique vibratoire, sur des structures industrielles présentant des non-linéarités localisées. La stratégie proposée repose principalement sur deux outils. D'abord, un solveur mécanique dédié basé sur la méthode de l'équilibrage harmonique et un processus de continuation par pseudo-longueur d'arc permet la réalisation des simulations en dynamique vibratoire. Ensuite, ce solveur mécanique est utilisé pour la construction et l'enrichissement d'un métamodèle de type processus gaussien au sein d'une démarche d'optimisation bayésienne afin de limiter le nombre d'appels au solveur. La stratégie est appliquée pour l'optimisation sans contraintes d'un oscillateur de Duffing puis pour l'optimisation sous contrainte d'un portique de levage présentant des non-linéarités de contact. Les résultats obtenus montrent les possibilités d'utilisation de la stratégie dans un contexte industriel
Vibration analysis can be critical for the optimal design of complex assembled structures. Integrating nonlinear phenomenon, especially at the interfaces between substructures, allows for high-fidelity numerical simulations. However, the computational cost makes it impractical to use classical global parametric optimization methods for industrial nonlinear structures. The work aims to study a comprehensive strategy for constrained parametric optimization applied to industrial vibrating structures exhibiting local nonlinearities. The proposed strategy mainly relies on two tools. First, a dedicated mechanical solver based on the Harmonic Balance Method and a pseudo-arclength continuation procedure is used for the dynamic simulations. Then, this mechanical solver is employed for the construction and enrichment of a Gaussian Process surrogate model within a Bayesian Optimization framework in order to limit the number of solver calls. The strategy is applied to unconstrained optimization of a Duffing oscillator and the constrained optimization of a gantry crane with contact nonlinearities. The results obtained suggest the feasibility of deploying the strategy in an industrial setting

Dans cette these je m'interesse a certains aspects des systemes desordonnes. D'abord, je introduis les systemes desordonnes a connectivite finie en insistant sur les nouveaux ingredients physiques et techniques qui les distinguent de leur correspondant completement connectes. Ensuite, je considere deux modeles en particulier. Le premier est un systeme de spins a connectivite finie, appele k-sat, dont l'analyse de la phase de basse temperature se traduit en un probleme d'optimisation qui est central en informatique theorique. Notre analyse variationnelle de k-sat predit une structure multifractale de l'espace des etats fondamentaux (solutions du probleme d'optimisation) et ameliore la comprehension qualitative et quantitative de ce probleme. Le deuxieme modele etudie est la diffusion sur un graphe aleatoire qui procure l'exemple le plus simple afin d'etudier le lien entre desordre geometrique et localisation. Nous avons montre, grace a une analyse numerique et analytique, que la localisation est due a des fluctuations de la connectivite locale et nous avons developpe et teste un schema d'approximation qui peut etre applique a des cas plus generaux. Dans le chapitre 5 je presente dans les details une analyse de la relation entre les etats purs et les structures inherentes. Ceci permet de comprendre comment certains concepts, comme celui d'etat tap, qui jouent un role essentiel dans l'analyse des modeles completement connectes, s'etendent en dimension finie ou a des systemes a connectivite finie ; ceci montre aussi que pour obtenir (en dimension finie) une theorie de la phase vitreuse basee sur l'analogie avec les verres de spins generalises il est necessaire d'introduire une definition temporelle d'etat. Ensuite, je presente une analyse du lien entre paysage d'energie libre et dynamique a temps longs pour le modele de hopfield avec un nombre de patterns fini et pour le modele a p-spins spheriques. Pour le premier systeme, en considerant une dynamique de glauber, nous montrons que les inverses des temps de relaxation les plus longs coincident avec les modules des valeurs propres de l'energie libre autour de ses points de stationnarite ; tandis que pour le deuxieme modele, je generalise l'approche de thouless, anderson et palmer (tap) a la dynamique ; ce qui permet de montrer explicitement la relation entre les etats tap et les lois de probabilite dynamiquement stables, et que le vieillissement peut etre interprete comme une evolution dans les directions plates de l'energie libre. Enfin, a travers des exemples simples et des resultats mathematiques recents nous proposons une definition temporelle d'etat et un formalisme dynamique afin de generaliser en dimension finie la description de la phase vitreuse, obtenue par l'analyse des verres de spins generalises. De plus, l'application de ce formalisme au modele a p-spins spheriques, a permis de devoiler les caracteristiques de la solution dynamique intervenant dans le calcul des proprietes des etats metastables, qui est d'un type nouveau par rapport aux solutions trouvees jusqu'a maintenant.

De récentes études expérimentales sur des situations d'atterrissage d'hélicoptères à grande vitesse dit dur (vitesse supérieure à 2 m/s), ont révélé que de par l'effort structural transmis par les trains d'atterrissage couplés mécaniquement au fuselage, la poutre de queue d'un appareil dont le premier mode de flexion se situe dans les basses fréquences pouvait être excitée. Les oscillations de celle-ci génèrent des contraintes mécaniques au niveau de la liaison entre la cabine et la poutre de queue qui portent atteinte à la pérennité de la structure. Afin de lutter contre ce phénomène problématique, une solution passive consiste à rigidifier la liaison entre la cabine et la poutre de queue. Coûteuse en masse et interférente avec le bon fonctionnement des dispositifs anti-vibratoires dimensionnés en fonction des fréquences propres initiales de l'appareil, celle-ci peut être évitée par une optimisation de l'effort transmis par les trains d'atterrissage en agissant sur le comportement dynamique de ceux-ci. Fort de ce constat, les travaux de recherche présentés dans ce mémoire, concernent l'étude et le développement de méthodes d'optimisation passive et active des trains d'atterrissage en vue de minimiser les efforts supportés par la poutre de queue et induits par l'impact de l'appareil sur le sol. Basé sur une constante synergie entre les aspects théoriques et les aspects expérimentaux appuyés par le développement d'un démonstrateur, cette étude formalise tout d'abord la problématique lié aux atterrissages des aéronefs et se propose d'analyser la physique du phénomène des atterrissages via des outils de modélisation utilisant des approches analytique et multi-corps. Ensuite après une analyse et une identification des paramètres d'optimisation de la dynamique des trains d'atterrissage, des méthodes d'optimisation passive et semi-active sont développées et validées expérimentalement sur un démonstrateur mécaniquement équivalent à l'hélicoptère considéré pour cette étude.

Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés

Cette thèse porte sur la résolution de problèmes d'optimisation combinatoire multi-objectif. La résolution de ces problèmes passe par la détermination de l'ensemble des solutions efficaces. Cependant, il peut s'avérer que le nombre de solutions efficaces soit très grand. Approcher l'ensemble des solutions efficaces d'un tel problème constitue, dès lors, un sujet de recherche central dans ce domaine. Les approches existantes sont souvent basées sur des méthodes approchées, de type (méta-)heuristiques, donc sans garantie sur la qualité des solutions trouvées. Des algorithmes d'approximation (à garantie de performance) ont aussi été développés pour certains problèmes, sans toutefois avoir été conçus en vue d'une mise en œuvre pratique. Dans cette thèse, nous nous sommes attachés à concevoir des approches visant à concilier à la fois les qualités des méthodes approchées et celles des méthodes d'approximation. Pour ce faire, nous proposons, dans un contexte général où les solutions sont comparées à l'aide d'une relation de préférence pouvant être non-transitive, un cadre de Programmation Dynamique Généralisée (PDG). Ce cadre est basé sur une extension du concept de relations de dominance utilisées dans la PD. Il permet, notamment, de concevoir des méthodes exactes et d'approximation qui se sont avérées particulièrement efficaces en pratique pour résoudre le problème du sac-à-dos multi-objectif 0-1. Enfin, une dernière partie de notre travail a porté sur l'apport d'une modélisation multicritère pour résoudre, dans un contexte réel, le problème d'association de données. Ceci nous a conduits à nous intéresser au problème d'affectation multi-objectif et à sa résolution au sein de notre cadre de PDG
This thesis deals with the resolution of multi-objective combinatorial optimization problems. A first step in the resolution of these problems consists in determining the set of efficient solutions. Nevertheless, the number of efficient solutions can be very huge. Approximating the set of efficient solutions for these problems constitutes, then, a major challenge. Existing methods are usually based on approximate methods, such as heuristics or meta-heuristics, that give no guarantee on the quality of the computed solutions. Alternatively, approximation algorithms (with provable guarantee) have been also designed. However, practical implementations of approximation algorithms are cruelly lacking and most of the approximation algorithms proposed in the literature are not efficient in practice. This thesis aims at designing approaches that conciliate on the one hand the qualities of the approximate approaches and on the other hand those of the approximation approaches. We propose, in a general context, where the preference relation used to compare solutions is not necessarily transitive, a Generalized Dynamic Programming (GDP) framework. GDP relies on an extension of the concept of dominance relations. It provides us, in particular, with exact and approximation methods that have been proved to be particularly efficient in practice to solve the 0-1 multi-objective knapsack problem. Finally, a last part of our work deals with the contributions of a multi-criteria modelling for solving, in real context, the data association problem. This led us to study the multi-objective assignment problem and, in particular, the resolution of this problem by the means of our GDP framework

Le réseau de distribution électrique français, construit dans une optique de desserte d'électricité depuis les centrales de production en amont, vers les consommateurs en aval, est aujourd'hui le lieu de transits d'énergie multi-sens et dont la charge instantanée dépend à la fois des consommations et des productions locales. Il faut donc moderniser les modèles d'exploitation des réseaux actuellement utilisés.C'est dans ce contexte que le gestionnaire du réseau de distribution de la Vienne SRD, et les différentes équipes du laboratoire LIAS, ont cherché à mettre en place un outil d'optimisation des schémas d'exploitation des réseaux de distribution d'électricité de la VIENNE.Dans cette thèse, le trnvt1il s'est porté principalement sur la modélisation du problème et non sur les méthodes de résolution. En effet, le contexte industriel du développement de l'outil d'optimisation du réseau a permis de se rapprocher au mieux de la réalité des informations disponibles concernant le réseau électrique. Et il est apparu plus pertinent d'utiliser des méthodes de résolution exactes tout en recherchant à simplifier le modèle complexe de représentation du réseau électrique. Ainsi,un modèle simple d'optimisation basé sur le problème de Bot à coût minimum a été mis en place et une étude comparative a été réalisée avec les modèles complexes présents dans la littérature.Ce premier modèle a été reformulé et rendu convexe et quadratique, et permet ainsi d'obtenir des performances supérieures en terme de temps de résolution à solution égale. Le problème d'optimisation simplifié a aussi été élaboré pour permettre de prendre en compte un horizon de temps dans l'optimisation du réseau électrique', afin de prendre en compte des profils de consommation et de production au cours du temps. En effet, ceci permet ainsi de prendre en compte des variations liées au comportement des consommateurs et des producteurs reliés au réseau.Et pour finir. ces modèles d'optimisation ayant pour objectif d'être inséré dans un outil d'aide à la décision pour une utilisation dans un contexte industriel. différentes contraintes liées à l'exploitation des réseaux électriques ont été insérées au modèle.Différents cas d'études issus de la littérature sont présentés pour valider la pertinence du modèle au regard des méthodes existantes. Nous avons pu expérimenter en simulation notre optimisation de réseau sur données de réseaux réels, ce qui a démontré l'applicabilité de la démarche à des problèmes de tailles importantes correspondant à la réalité du réseau électrique de SRD
The French electrical distribution network was originally built to bring electricity from very large producers to consumers, but it has now become a place of multi-directional energy flows that rely on local production and consumption. Because of this new situation, the way of operating electrical networks needs to be renewed. In light of this, the local Distribution System Operator (SRO) of the French department Vienne and the different teams of the LIAS laboratory have worked together on the development of a distribution network configuration optimization tool. In this thesis the majority of the work was focused on the modeling part of the problem rather than on the development of new optimization methods. The industrial root of this project gave the opportunity to be very close to the reality of the available network data. Based on those observations,it was more consistent to use exact and precise optimization methods to solved simplified versions of the complex electrical network models.Thus a simple optimization model based on the minimum cost flow problem was developed, and a comparative study between the developed model and state of the art more complex one was led. This simple model was reformulated to become convex and quadratic and to reach better resolution time performances with the same solutions. This optimization problem was developed to take into account a time horizon factor into the optimization of the operation planning of the distribution network. The time horizon factor aim to represent the production and consumption variation over a selected period. Finally. because this model has to be integrated into a decision making helping tool that will be used by the DSO SRD several operational constraints were added into the optimization model. Several state of the art case studies arc presented to validate the model accuracy regarding existing methods. Simulation experiments were done on real networks data to show the applicability of the proposed optimization model over large scale case studies which correspond to the DSO SRO reality

Ce travail porte sur l’optimisation sous contraintes de masse de structures de type cabine de camion. Il s’agit ici d’un problème dans lequel deux objectifs antagonistes doivent être conciliés. En effet, la réduction de la masse de la structure entraîne une dégradation de ses performances vibro-acoustiques. Il faut donc pouvoir déterminer quelles zones de la structure influent le moins sur ce comportement afin de diminuer la masse localement. C’est dans cet esprit que, dans un premier temps, différentes méthodes d’analyse de sensibilité sont présentées afin de déterminer leurs avantages et inconvénients dans le cas de leur utilisation pour identifier les variables à retenir dans le cas d’une procédure d’optimisation donnée. Ensuite une procédure d’optimisation adaptative en basses fréquences est présentée et appliquée à un cas test représentant schématiquement une cabine de camion et les résultats obtenus sont comparés à ceux issus d’un algorithme d’optimisation sous contraintes non-linéaires couramment utilisé. Une seconde méthode est également développée dans le cas des moyennes et hautes fréquences où les informations disponibles sur la structure sont seulement des quantités énergétiques. Ici encore les résultats obtenus sont comparés à ceux issus d’un algorithme d’optimisation sous contraintes non-linéaires
This work deals with mass optimization procedures underdesign constraints of truck cabs. It consists in a problem where two conflicting objectives must be conciliated as the mass reduction would deteriorate the vibroacoustic behaviour. One has to determine the zones in which the mass could be locally reduced. First, this work presents several sensitivity analysis procedures and discusses theirs advantages and drawbacks. Then an adaptive optimization procedure is developed in the low frequency range. This procedure is applied on atest-case and the obtained results are compared with results issued from a commonlyused optimization algorithm. The procedure is then extended to medium and high frequency range where the only available quantities are energetic ones. The obtained results are also compared with those from a commonly-used optimization algorithm

L'optimisation combinatoire est une branche de l'optimisation mathématique qui se concentre sur la recherche de solutions optimales parmi un ensemble fini de combinaisons possibles, tout en respectant un ensemble de contraintes et en maximisant ou minimisant une fonction objectif. Pour résoudre ces problèmes, les méthodes incomplètes sont souvent utilisées en pratique, car ces dernières peuvent produire rapidement des solutions de haute qualité, ce qui est un point critique dans de nombreuses applications. Dans cette thèse, nous nous intéressons au développement d'approches hybrides qui permettent d'améliorer la recherche incomplète en exploitant les méthodes complètes. Pour traiter en cas pratique, nous considérons ici le problème de tournées de véhicules avec profits, dont l'objectif est de sélectionner un sous-ensemble de clients à visiter par des véhicules de manière à maximiser la somme des profits associés aux clients visités. Plus précisément, nous visons tout d'abord à améliorer les algorithmes de recherche incomplets en exploitant les connaissances acquises dans le passé. L'idée centrale est de: (i) apprendre des conflits (combinaisons de décisions qui conduisent à une violation de certaines contraintes ou à une sous-optimalité des solutions) et les utiliser pour éviter de réexaminer les mêmes solutions et guider la recherche, et (ii) exploiter les bonnes caractéristiques de solutions élites afin de produire de nouvelles solutions ayant une meilleure qualité. En outre, nous étudions le développement d'un solveur générique pour des problèmes de routage complexes pouvant impliquer des clients optionnels, des véhicules multiples, des fenêtres temporelles multiples, des contraintes supplémentaires, et/ou des temps de transition dépendant du temps. Le solveur générique proposé exploite des sous-problèmes pour lesquels des méthodes de raisonnement dédiées sont disponibles. L'efficacité des approches proposées est évaluée par diverses expérimentations sur des instances classiques et sur des données réelles liées à un problème d'ordonnancement pour des satellites d'observation de la Terre, qui inclut éventuellement des profits incertains
Combinatorial optimization is an essential branch of computer science and mathematical optimization that deals with problems involving a discrete and finite set of decision variables. In such problems, the main objective is to find an assignment that satisfies a set of specific constraints and optimizes a given objective function. One of the main challenges is that these problems can be hard to solve in practice. In many cases, incomplete methods are preferred to complete methods since the latter may have difficulties in solving large-scale problems within a limited amount of time. On the other hand, incomplete methods can quickly produce high-quality solutions, which is a critical point in numerous applications. In this thesis, we investigate hybrid approaches that enhance incomplete search by exploiting complete search techniques. For this, we deal with a concrete case study, which is the vehicle routing problem with profits. In particular, we aim to boost incomplete search algorithms by extracting some knowledge during the search process and reasoning with the knowledge acquired in the past. The core idea is two-fold: (i) to learn conflicting solutions (that violate some constraints or that are suboptimal) and exploit them to avoid reconsidering the same solutions and guide search, and (ii) to exploit good features of elite solutions in order to hopefully generate new solutions having a higher quality. Furthermore, we investigate the development of a generic framework by decomposing and exchanging information between sub-modules to efficiently solve complex routing problems possibly involving optional customers, multiple vehicles, multiple time windows, multiple side constraints, and/or time-dependent transition times. The effectiveness of the approaches proposed is shown by various experiments on both standard benchmarks (e.g., the Orienteering Problem and its variants) and real-life datasets from the aerospace domain (e.g., the Earth Observation Satellite scheduling problem), and possibly involving uncertain profits

Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La programmation stochastique et la programmation biniveau sont deux sous-domaines de la PM, permettant chacun de modéliser un aspect particulier de ces problèmes pratiques. Nous élaborons un modèle mathématique issu d'un problème appliqué, où les aspects biniveau et stochastique sont tous deux sollicités, puis procédons à une série de transformations du modèle. Une méthode de résolution est proposée pour le PM résultant. Nous démontrons alors théoriquement et vérifions expérimentalement la convergence de cette méthode. Cet algorithme peut être utilisé pour résoudre d'autres programmes biniveaux que celui qui est proposé.Le second thème de recherche de cette thèse s'intitule "problèmes de coupe et de couverture partielles dans les graphes". Les problèmes de coupe et de couverture sont parmi les problèmes de graphe les plus étudiés du point de vue complexité et algorithmique. Nous considérons certains de ces problèmes dans une variante partielle, c'est-à-dire que la propriété de coupe ou de couverture dont il est question doit être vérifiée partiellement, selon un paramètre donné, et non plus complètement comme c'est le cas pour les problèmes originels. Précisément, les problèmes étudiés sont le problème de multicoupe partielle, de coupe multiterminale partielle, et de l'ensemble dominant partiel. Les versions sommets des ces problèmes sont également considérés. Notons que les problèmes en variante partielle généralisent les problèmes non partiels. Nous donnons des algorithmes exacts lorsque cela est possible, prouvons la NP-difficulté de certaines variantes, et fournissons des algorithmes approchés dans des cas assez généraux
This thesis is composed of two parts, each part belonging to a sub-domain of combinatorial optimization a priori distant from the other. The first research subject is stochastic bilevel programming. This term regroups two research subject rarely studied together, namely stochastic programming on the one hand, and bilevel programming on the other hand. Mathematical Programming (MP) is a set of modelisation and resolution methods, that can be used to tackle practical problems and help take decisions. Stochastic programming and bilevel programming are two sub-domains of MP, each one of them being able to model a specific aspect of these practical problems. Starting from a practical problem, we design a mathematical model where the bilevel and stochastic aspects are used together, then apply a series of transformations to this model. A resolution method is proposed for the resulting MP. We then theoretically prove and numerically verify that this method converges. This algorithm can be used to solve other bilevel programs than the ones we study.The second research subject in this thesis is called "partial cut and cover problems in graphs". Cut and cover problems are among the most studied from the complexity and algorithmical point of view. We consider some of these problems in a partial variant, which means that the cut or cover property that is looked into must be verified partially, according to a given parameter, and not completely, as it was the case with the original problems. More precisely, the problems that we study are the partial multicut, the partial multiterminal cut, and the partial dominating set. Versions of these problems were vertices are

Le travail developpe dans cette these concerne la reduction de la complexite en temps de methodes d'optimisation directes. Nous avons retenu deux methodes qui n'utilisent aucune information variationnelle mais simplement la valeur de la fonction en des points particuliers: la methode du simplexe de nelder-mead et la programmation dynamique. Malgre leurs avantages, leur application est limitee par la dimension des problemes et par l'espace memoire necessaire. Les approches developpees portent sur des ameliorations algorithmiques et sur la conception d'algorithmes paralleles sur des architectures mimd a memoire partagee: le cray c98 et a memoire distribuee: un reseau local de stations et l'environnement landa. Dans un premier temps notre travail a porte sur la generalisation de l'algorithme du simplexe. Pour cela, apres avoir analyse les proprietes d'un simplexe, nous avons elabore trois classes d'algorithmes dont le principe commun repose sur la multiplication des directions de recherche. Dans un second temps, nous avons etudie la parallelisation de cet algorithme. L'idee de base consiste a effectuer une anticipation des operations dans l'ordre ou elles pourraient apparaitre. La modelisation des performances de cette strategie a permis d'estimer de maniere precise les accelerations envisageables. En ce qui concerne la programmation dynamique nous avons developpe une approche numerique vectorielle et parallele pour la resolution de problemes de commande optimale deterministes ou stochastiques, en horizon fini ou infini, contraints sur l'etat et/ou la commande. Les strategies de parallelisation adoptees sont basees sur la vectorisation des calculs, le partionnement des domaines, et la relaxation du synchronisme

L'objectif est de réaliser l'optimisation dynamique de mouvements de systèmes à cinématique ouverte ou fermée. La méthode choisie est l'optimisation paramétrique. La technique utilisée consiste à approximer les paramètres du mouvement par des fonctions splines de classe C3 constituées de polynômes de degré 4 raccordés en des points de jonction équirépartis sur le temps. Les couples actionneurs, et les efforts de liaison associés aux conditions de fermetures, s'expriment ainsi, par l'intermédiaire des équations du mouvement, comme des fonctions du temps et des paramètres d'optimisation. Ces couples et efforts quadratiques intégrés sur le temps fournissent la fonction objectif à minimiser. Le problème d'optimisation dynamique est alors transformé en un problème d'optimisation paramétrique, résolu par des codes de calcul existants. Cette technique est appliquée à la synthèse de pas de marche sagittale. La seule donnée d'une vitesse de marche permet d'engendrer un pas optimal
This work is aimed at optimizing motions of constrained dynamics systems. A parametric optimisation method is developed. It consists in approximating joint motion coordinates using spline functions of class C3, made up of 4-order polynomials linked at uniformly distributed knots, in order to avoid jerks at connecting points. Joint actuating torques as well as interaction forces associated with closure constraints of closed kinematic chains, are expressed, through dynamics equations, as functions depending on both the time and the optimisation parameters. The objective function to be minimized is obtained by integrating quadratic torques and interaction forces along the motion time. The initial dynamic optimisation problem is then recast as a parametric optimisation problem, which is solved using existing computing codes. This technique is used to carry out optimal synthesis of sagittal gait. The walking velocity is the only data required for generating an optimal step

Au cours des dernières décennies, avec l'ère de la mondialisation, le transport aérien a joué un rôle économique important en facilitant le transport des personnes et des marchandises entre les différentes parties du monde et vers les régions éloignées des pays. Les aéroports en tant que terminaux intermodaux sol / air constituent le segment terrestre du système de transport aérien. Des investissements soutenus sur de longues périodes de plusieurs décennies semblent essentiels pour maintenir ou développer les opérations aéroportuaires. Ces investissements sont en général coûteux et la planification des investissements aéroportuaires est une question importante aux niveaux local et national. L'objectif de cette thèse est de présenter une approche de planification à long terme des investissements de réseaux d'aéroports nationaux. Un cadre pour la génération à long terme de scénarios de demande de transport multimodal au niveau national, qui assure la cohérence entre la prévision des différents modes de transport et assure la compatibilité entre les flux de transport aérien prévus entre les aéroports considérés, est proposé. Ensuite, le problème central de décision pour l'allocation des ressources à long terme entre les différents aéroports d'un réseau national est formulé comme un problème d'optimisation. Ce modèle peut être résolu avec différents scénarios de demande, dans lesquels les scénarios extrêmes devraient prévoir un intervalle pour l'effort financier nécessaire à chaque étape de l'horizon de planification pour chaque aéroport. Pour résoudre les problèmes d'optimisation qui en résultent, une approche de programmation dynamique a été envisagée où les états candidats à traiter à chaque étape sont générés par un réseau de Petri construit à partir des plans directeurs non datés des aéroports du réseau considéré. L'approche proposée est illustrée dans le cas d'un grand pays en voie de développement (République du Niger)
In the last decades with the era of globalisation, air transportation has been playing an important economic role by easing the transportation of people and goods between the different parts of the World and to remote areas within countries. The airports as ground/air intermodal terminals are the ground segment of the air transport system. Sustained investments over long periods of several decades appear essential to maintain or expand airport operations. These investments are in general costly and airport investment planning is an important issue at the local and national levels. The objective of this thesis is to present a long-term planning approach for the investments in national airports networks. A framework for the long-term generation of multimodal transportation demand scenarios at the national level, which insures coherency between the prediction of the different transportation modes and assure compatibility between the predicted air transportation flows between the considered airports, is proposed. Then the central decision problem for long-term resource allocation between the different airports of a national network is formulated as an optimization problem. This model can be solved with different demand scenarios, where extreme scenarios should provide an interval for the necessary financial effort at each stage of the planning horizon for each airport. To solve the resulting optimization problems a Dynamic Programming approach has been considered where the candidate states to be processed at each stage are generated by a Petri Net built from the undated master plans of the airports of the considered network. The proposed approach is illustrated in the case of a large under developed country (Niger Republic)

Dans le but de remédier aux problèmes aujourd'hui omniprésents dans le secteur du transport, qu'ils soient financiers, environnementaux ou autres, nous nous intéressons à l'établissement d'un système de covoiturage dynamique optimisé. La voiture partagée est venue subvenir à des besoins restés insatisfaits en matière de déplacement (flexibilité spatiotemporelle...) encourageant l'émergence d'un mode de transport révolutionnaire qu'est la comodalité. Le focus est alors mis sur la complémentarité entre les modes collectifs et individuels et vient considérer la voiture partagée et plus particulièrement le covoiturage comme des modes de transport à part entière. Placés dans ce cadre, nous nous intéressons à l'aspect temps réel dans les systèmes de covoiturage et développons nos travaux dans ce sens. Ce problème ayant une complexité qui n'est pas des moindres, tous nos efforts sont dirigés dans le but de contrecarrer cet obstacle et mettre en œuvre une application logicielle compétitive à grande échelle offrant satisfaction et qualité de service. Pour ce faire, nous considérons une alliance des systèmes multi-agents et des techniques d'optimisation donnant lieu à des agents optimisateurs répartis selon une modélisation de graphe dynamique distribué. Celui-ci est établi sur la base d'un principe de décomposition du réseau géographique desservi inspiré des techniques de classification pour la mise en exergue des zones de concentration des abonnés. Cette modélisation favorise le traitement parallèle des requêtes de par la décentralisation et décomposition du processus initial sur une multitude d'agents optimisateurs chargés chacun d'une ou plusieurs tâches de moindre complexité.

Dans cette thèse, nous nous sommes intéressés à la résolution exacte de problèmes de dimensionnement de réseaux RCSF, rencontrés pendant la phase de planification. Tout d’abord nous nous intéressons au problème de déploiement. Il s’agit de positionner les capteurs dans un plan euclidien afin de minimiser le coût des opérations de communication pour transmettre les données vers le Station de Base. Le deuxième problème, le problème de configuration de réseau, s’intéresse à l’organisation des capteurs dans des zones/clusters. L’objectif ici est de déterminer le nombre optimal de zones et leurs portées respectives afin de minimiser la consommation en énergie de chaque capteur. Les méthodes proposées sont basées sur des algorithmes de programmation dynamique qui garantissent des solutions optimales et sont à faible complexité si on les compare aux approches de littérature. Le dernier problème étudié concerne l’affectation de puissances aux capteurs et d’ordonnancement des transmissions. Ici l’objectif est de garantir les transmissions concurrentes entre les nœuds tout en minimisant le temps de transmission des données. Au cœur de notre approche est la stratégie d’affectation de puissances de transmissions qui tente de maximiser la valeur minimale de SINR estimée chez les récepteurs. Le problème est modélisé et résolu en utilisant un algorithme itératif basé sur la programmation linéaire
In this thesis, we focused on the development of optimal methods regarding WSN dimensioning problems, mostly encountered during the planning phase. These were instantiated basically into three combinatorial optimization problems. The network deployment scheme which seeks to place the sensors in a such way that the cost of communication operations is minimized. The network configuration problem that asks to find a strategy for dividing the network such that some criteria are satisfied. In the problem’s model we took into account the data aggregation constraint and the discrete values of power transmission. For both problems we proposed a resolution method, based on dynamic programming, which permitted us to solve them optimally. Finally, the joint problem of scheduling and power assignment, consisted in finding a feasible scheduling under SINR constraints and a power assignment scheme to guarantee successful concurrent transmissions. As the problem is shown to be NP-hard we propose a greedy heuristic. The resolution method for the power assignment strategy, an iterative algorithm based on linear programming, provides optimal solutions

Cette thèse traite le développement d'un modèle mathématique d'optimisation acoustique des trajectoires de vol de deux avions commerciaux en approche sous contrainte énergétique, aérodynamique et opérationnelle. C'est un modèle analytique de contrôle optimal non-linéaire et non-convexe régi par un système d'équations différentielles ordinaires issues de la dynamique de vol et des contraintes associées. Notre contribution porte sur la modélisation mathématique des équations, l'optimisation et la programmation algorithmique d'un modèle d'optimisation non-linéaire du bruit de deux avions en approche simultanée. Les points abordés sont le développement mathématique du modèle 3D "exact" de leur dynamique de vol, la modélisation mathématique de la commande optimale de ce système dynamique, l'introduction de la consommation du carburant par les avions comme une équation différentielle avec une fonction consommation spécifique variable en fonction de l'évolution de leur dynamique, la modélisation mathématique instantanée de la fonction objectif représentant le bruit global des deux avions en approche. Sa résolution porte sur la méthode directe de programmation séquentielle quadratique avec régions de confiance sous AMPL et KNITRO. Une méthode indirecte a été appliquée sous le principe de maximum de Pontryagin suivie d'une discrétisation de type Runge-Kutta partition-née symplectique d'ordre 4 afin de démontrer la commutation entre l'approche directe et l'approche indirecte. Les résultats obtenus confirment des trajectoires optimales en descente continue, réduisant le bruit au sol ainsi que la consommation de kérosène de deux avions

Dans ce travail, nous avons cherché à tester l'hypothèse selon laquelle les araignées femelles adultes d'une espèce orbitèle, Zygiella x-notata, construisent leurs toiles successives de manière à maximiser leur fitness. Après avoir mis au point un outil méthodologique permettant d'estimer la longueur de la spirale d'une toile, l'aspect dynamique des constructions a été étudiée à court terme. Nos résultats montrent que les araignées utilisent des informations relatives aux événements de capture et de consommation de proies associés à une toile lors de la construction de la toile suivante. La dynamique des constructions a ensuite été étudiée à plus long terme, entre la mue imaginale des femelles et leur première ponte. Ce travail a nécessité de préciser les coûts et bénéfices associés au comportement de construction et de réaliser un modèle prédictif de la stratégie optimale de construction des toiles. Cette stratégie a pu être comparée aux comportements des araignées. Les données recueillies suggèrent que le risque de prédation encouru durant la construction d'une toile sont faibles et révèlent que les dépenses énergétiques associés à la construction d'une toile augmentent à la fois avec la quantité de soie mise en place et avec le poids des araignées. Les probabilités de capture de proies (bénéfices énergétiques) augmentent avec la taille des toiles. Les données de terrain et de laboratoire révèlent que les araignées réduisent leur activité de construction au cours de leur développement. En accord avec ces observations, le modèle prédit que les araignées devraient réduire leur activité de tissage quand leur poids devient élevé. Par ailleurs nos résultats suggèrent que la pression de sélection exercée sur le comportement de construction est faible au cours d'une grande part du développement des araignées femelles adultes, ce qui pourrait expliquer en partie la diversité des comportements de construction exprimés par celles-ci
This study aims to test the hypothesis that adult female spiders of the orb-weaving species Zygiella x-notata build their successive webs according to rules that allow them to maximise their fitness. A non invasive method was first set up to estimate the total capture thread length of a web. Short term web building dynamics could be then investigated. Our results showed that informations linked to capture events and to prey ingestion with a given web influence following web building. Long term web building dynamics was studied through a longitudinal study of spiders between their final moult and their first egg-laying. Cost and benefits of web-building behaviour had to be estimated before setting up a predictive model of web-building optimal strategy. Predictions of this model could then be matched with observed behaviour. Behavioural data suggest predation risk occurring during web building to be weak, and energetic expenditure to increase both with the amount of silk set up per web and with spider's body weight. Probability of prey catching -that is, energetic expected gains- increased together with web size. Both field and laboratory data showed that adult female spiders reduced their web building activity throughout their development. Results of the predictive model also suggest that when their body weight increased, optimal spiders should reduce their building activity. Furthermore, we could make the following hypothesis: selective pressures should remain weak over web-building behaviour during most of adult female spider's development. This could explain, at least partly, the great diversity of observed web-building behaviours

La population mondiale fait face, globalement, à une urbanisation expansive. Cet étalement urbain, souvent mal contrôlé, menace aussi bien l’environnement que la santé, la qualité de vie et la sécurité alimentaire des humains. Il est possible de le limiter en lui préférant la densification urbaine. Néanmoins, la complexité des phénomènes en jeu dans un tel contexte nous incite à penser que les responsables d’opérations de densification urbaine ont besoin d’outils pour les aider à faire les choix les plus pertinents possibles. Dans un premier temps, l’état de l’art présenté dans cette thèse montre que l’outil idéal n’existe pas, et que l’optimisation multicritère par algorithme génétique est une technique adaptée à l’aide à la conception de bâtiments. Les caractéristiques souhaitables pour une méthode d’assistance des concepteurs de projets de densification urbaine sont alors précisées. Nous recommandons de baser cette méthode sur le couplage entre un algorithme génétique et un outil capable de réaliser des simulations thermiques dynamiques (STD) de quartiers. Les capacités des logiciels de STD Pleiades+COMFIE (P+C) et EnergyPlus (E+) sont situées par rapport à ces exigences, puis un premier test d’optimisation d’un projet de densification urbaine en associant EnergyPlus à un algorithme génétique est présenté. Certaines lacunes de cette méthode peuvent être comblées par la plateforme en cours de développement dans le projet ANR MERUBBI. Dans un second temps, nous analysons donc les résultats d’une étude comparative entre P+C, E+ et l’outil MERUBBI, menée sur un projet de densification d’un îlot à forte densité urbaine. Ils montrent que ce dernier est fiable et particulièrement pertinent pour l’évaluation précise des interactions entre bâtiments. Dans un troisième temps, nous abordons la problématique de la diminution des temps de calcul, enjeu crucial pour que notre méthode d’aide à la conception soit réellement accessible aux professionnels du bâtiment. Nous proposons une technique de réduction de la période de simulation que nous présentons en détail. Enfin, la méthode d’optimisation développée est appliquée à la résolution de différents problèmes de conception du projet sus-cité, en utilisant E+. Nous montrons en quoi l’utilisation de l’outil MERUBBI enrichira cette approche, avant de conclure sur des perspectives de développement de notre méthode pour améliorer son interactivité
The world’s population is facing an expansive urbanization. This urban sprawl, which is often not well managed, is endangering the environment as well as human health, quality of life and food security. It can be controlled by favouring urban densification. Nonetheless, the complexity of the phenomena involved in such a context leads us to think that supervisors of urban densification operations need some tools to help them make the most relevant choices. This thesis begins with a literature review that shows the ideal tool does not exist, and explains why multi-objective optimization using a genetic algorithm is a suitable technique for building design aid. Then we clarify the desirable features of an assistance method for urban densification projects designers. We recommend to base this method on the coupling of a genetic algorithm with a district-scale dynamic thermal simulation (DTS) tool. We compare capabilities of EnergyPlus (E+) and Pleiades+COMFIE (P+C) DTS software with these requirements, then we present a first urban densification project optimization test associating EnergyPlus with a genetic algorithm. The platform under development in the ANR MERUBBI project can offset certain shortcomings of this method. Hence, in a second phase we analyze the results of a comparative study of P+C, E+ and the MERUBBI tool, carried out using a high-density district densification project as a test case. It shows that the latter is reliable and particularly relevant to precisely assess interactions between buildings. In a third phase we address the problematic of reducing the computing time, a major issue to make our design aid method truly accessible to building professionals. We propose a way of reducing the operating period length and present it in detail. Finally, our optimization method is used to solve various design problems of the above-mentioned project, using E+. We show how the use of the MERUBBI platform will enrich this approach before concluding with development ideas to make our method more user-friendly and interactive

Le chargement/déchargement des conteneurs et leurs stockages provisoires dans le port est la plus importante et complexe tâche dans les terminaux portuaires. Elle est fortement liée au routage des grues de quai et son coût augmente considérablement surtout en absence d’une gestion efficace du terminal. Dans ce travail, nous étudions le problème de stockage des conteneurs (PSC). Il appartient à la catégorie des problèmes NP-difficiles et NP-complets. PSC consiste à déterminer un plan d’arrangement des conteneurs destinés à l’import et à l’export dans le port qui minimise les remaniements ultérieurs lors de leur transfert vers le bateau, camion ou train. En effet, le temps d'attente des camions des clients, le temps de transfert des grues de quai et le temps nécessaire au chargement/déchargement du navire sont avantageusement réduits. PSC est généralement étudié en considérant un seul type de conteneur. Cependant, plusieurs types de conteneurs sont utilisés dans les ports maritimes (dry, réfrigérés, toit ouvert,...). En outre, le problème de stockage de conteneurs peut être traité de façon statique ou dynamique (date d’arrivée et de départ des conteneurs incertains).L’objectif de cette thèse est de résoudre le PSC statique et le PSC dynamique pour un seul et plusieurs types de conteneurs en utilisant deux métaheuristiques : l’algorithme génétique, la recherche harmoniquePour vérifier la performance de chacune des approches proposées, une étude comparative des résultats générés par chaque méthode ainsi que celle de l’algorithme LIFO est établie
The loading and unloading of containers and their temporary storage in the container terminal are the most important and complex operation in seaport terminals. It is highly inter-related with the routing of yard crane and truck and their costs increased significantly especially without an efficient terminal management. To improve this process, an efficiency decision for the container storage space allocation must be taken.In this thesis, we studied the container storage problem (CSP). It falls into the category of NP hard and NP complete problems. CSP consists on finding the most suitable storage location for incoming containers that minimizes rehandling operations of containers during their transfer to the ship, truck or train. In fact, the wait time of customer trucks, the transfer time of yard crane and the Ship turnaround time are advantageously reduced.Generally, this problem is studied considering a single container type. However, this does not stand the problem under its real-life statement as there are multiple container types that should be considered, (refrigerated, open side, empty, dry, open top and tank). Often, containers arrive at the port dynamically over time and have an uncertain departure date (ship delayed, a ship down, delayed arrival of customer trucks…). Indeed, CSP must be studied in dynamic aspectThe objective of this thesis is to study Static CSP for a single and various container type and dynamic CSP for ONE and several container types and to propose solutions for each of them. Genetic algorithm and Harmony Search algorithm are used to solve these problems and we compare the results of each approach with the LIFO algorithm

La complexité du vivant est omniprésente à toutes les échelles : des interactions entre molécules individuelles aux réseaux d'interactions permettant à la cellule d'assurer ses fonctions vitales et de répondre aux stimuli. Cette thèse se veut être une application des outils de l'Automatique et de l'Informatique à certaines questions de la Biologie et Biochimie.
Pour cela, nous avons abordé le problème via deux aspects : le premier concerne la modélisation des interactions moléculaires en vue de prédire les modes de fixation et les affinités entre molécules. Puisque ces estimations nécessitent de considérer la flexibilité des acteurs, nous avons abordé, en premier lieu, la prédiction des conformations moléculaires qui reste un challenge majeur, caractérisé par ses aspects multimodal et de grandes dimensions. Nous avons alors développé une suite d'heuristiques autour d'un algorithme génétique central. Les paramètres de contrôle et les stratégies d'hybridation sont pilotés par un méta-algorithme permettant d'optimiser la recherche. En outre, des stratégies innovantes de parallélisation sur grilles d'ordinateurs ont été validées afin de réduire les temps de calculs. Enfin, pour entreprendre l'étude des conformations de plusieurs molécules, nous avons développé des algorithmes de criblage rapides basés sur la comparaison d'indices topologiques.
Nous avons également étudié un autre aspect en modélisant formellement certains graphes d'interactions, ceci à une toute autre échelle : celle des concentrations des molécules. Nous avons alors mis en évidence l'impact des modes d'interactions moléculaires sur la dynamique globale.

Cette thèse s'est déroulée en partenariat entre l'Institut de Mathématiques de Toulouse, où de nouvelles méthodes d'optimisation ont été introduites et Snecma, où elles ont été appliquées à l'optimisation de la compensation des aubes de turbomachines. Les méthodes d'optimisation d'ordre zéro ont connu un essor considérable ces dernières années en raison des difficultés posées par le calcul du gradient qui peut avoir un domaine de validité extrêmement réduit. Deux outils généraux d'optimisation d'ordre zéro avec mémoire en grande dimension sont proposés. L'idée de base consiste à exploiter toutes les évaluations de la fonction coût générées au cours du processus d'optimisation afin de créer un modèle approché. La génération d'un nouveau point doit tenir compte d'un double objectif : se rapprocher du point optimum et assurer une bonne approximation de la fonction coût à l'étape suivante. Parmi toutes les techniques d'approximation classiques, nous avons considéré pour cette étude, uniquement celles assurant l'approximation d'une constante avec précision. En effet, si ce critère n'est pas satisfait, des minima locaux sans rapport avec le problème physique peuvent apparaître. Pour cette raison, nous avons alors retenu seulement deux méthodes : les réseaux neuronaux et les sparse grid. Cette dernière méthode émergente ouvre de nouvelles perspectives dans différents domaines scientifiques en raison de son caractère hiérarchique et adaptatif. L'efficacité de ces deux techniques est démontrée sur des fonctions analytiques, puis validée sur le problème industriel de la compensation
This thesis presents the result of collaboration between Snecma and IMT (Institut de Mathématiques de Toulouse). New efficient optimisation methods have been developed in IMT and then applied on blade design at Technical Department of Snecma. In many industrial applications, the gradient of a cost function is not available and if it is available, its domain of validity is very restricted. This led to the recent development of numerous zero order optimisation methods. Two numerical tools for large dimension optimisation without derivative computation are discussed here. The main idea is to use the cost function evaluations, which are performed during the optimisation process, to build a surrogate model. Addition of a new point during the optimisation process must reach a double target: progress towards the optimum and improve the approximation of the cost function for the next step. Among all approximation techniques, we focus here on those which catch easily constant behaviour. As a matter of fact, other methods introduce false local minima. Consequently we focus on two methods: neural networks and sparse grids. Especially sparse grid is a new promising way for various scientific topics thanks to its adaptative and hierarchical properties. Efficiency of these methods is proved on analytical functions and confirmed on industrial cases and especially for bend momentum balance of compressor and turbine blades

L'inertie thermique constitue un atout essentiel pour stocker l'énergie reçue par le bâtiment et la restituer quand cela est nécessaire : elle permet d'emmagasiner les apports gratuits issus du rayonnement solaire pour réduire les consommations énergétiques liées au chauffage en présence d'une isolation performante. En été, son association à la ventilation nocturne contribue à évacuer l'énergie stockée au cours de la journée limitant ainsi les surchauffes à l'intérieur du bâtiment. Une exploitation optimale de l'inertie passe par une sélection appropriée des matériaux de construction lors de la phase d'avant-projet et par le développement de stratégies visant à exploiter leur capacité de stockage. Les outils de simulation thermique dynamique dont on dispose permettent de modéliser de façon assez précise les transferts de chaleur dans l'enveloppe du bâtiment mais leur niveau de finesse n'est pas nécessairement adapté aux besoins des concepteurs au moment de faire les choix les plus fondamentaux. Néanmoins ils demeurent indispensables non seulement pour la validation de ces choix mais aussi pour le développement de méthodes destinées à améliorer l'exploitation de l'énergie avant de procéder à la réalisation d'un projet. Ce travail a consisté à développer une méthodologie de conception basée sur deux approches complémentaires : la première approche permet de décrire le comportement détaillé du bâtiment à l'aide d'un modèle de simulation dynamique performant développé dans la plateforme SimSPARK qu'on a eu l'occasion de comparer aux mesures expérimentales de la plateforme INCAS. La seconde est basée sur le développement de l'outil simplifié CoSPARK qui à partir de la connaissance de quelques éléments clés, permet de déterminer les caractéristiques appropriées de l'enveloppe pour favoriser la performance énergétique des bâtiments. La dernière partie de ce travail a été consacrée à l'optimisation de stratégies d'une part en activant l'inertie thermique dans le cas d'une ventilation nocturne adaptative pour l'été et d'autre part en réduisant les consommations de chauffage en hiver dans le cas d'un plancher couplé à une installation solaire en utilisant le modèle de référence SimSPARK.

Cette thèse propose dans un premier temps une évaluation structurelle des effets microéconomiques de deux politiques phares du Plan d'Aide au retour à l'Emploi (PARE) implémenté en France en 2001 : l'accompagnement et la formation des demandeurs d'emploi. La création d'entreprise étant souvent citée comme une alternative à ces politiques, on établit dans un second temps un modèle du cycle de vie des travailleurs indépendants. Toutefois, ne disposant du coût social des mesures étudiées, une analyse coût-bénéfice complète n'a pu être réalisée dans le cadre de ce travail. D'un point de vue méthodologique l'approche structurelle est abordée ici comme une extension des évaluations en forme réduite et non comme leur antithèse. Compte tenu des difficultés algorithmiques posées par cette méthode, on accorde une attention particulière aux techniques d'optimisation utilisées et on s'attache - suivant les recommandations de Judd - à simplifier au maximum la mise en oeuvre des estimations grâce à l'usage du logiciel AMPL.

Les travaux présentés dans ce document portent sur des problèmes d'optimisation dans le domaine de la logistique interne des entrepôts. Le domaine est soumis à une forte concurrence et est en plein essor, poussé par les besoins croissants du marché et favorisé par l'automatisation. L'entreprise SAVOYE construit des équipements et propose sa propre solution GTP (Goods-To-Person) pour la préparation de commandes. La solution utilise un système de stockage automatisé appelé X-Picking Tray System (X-PTS) et achemine les charges automatiquement à des postes de travail via des carrousels pour effectuer des opérations séquencées. C'est un système de systèmes particulièrement complexe qui offre de nombreuses applications aux techniques de la recherche opérationnelle. Tout cela définit le périmètre applicatif et théorique des travaux menés dans cette thèse. Nous avons d'abord traité un problème d'ordonnancement de type Job Shop avec des contraintes de précédences. Le contexte particulier du problème a permis de le résoudre en un temps polynomial avec un algorithme exact. Celui-ci a permis de calculer les dates d'injection des charges provenant des différents flux de sortie du stockage pour s'agréger sur un carrousel, dans un ordre donné. Ainsi, la gestion inter-allées du stockage PTS a été améliorée et le débit du flux de charges maximisé, depuis le stockage jusqu'à un poste. Nous avons ensuite étudié des algorithmes de tri tels que le tri par base et développé un algorithme de tri en ligne, utilisé pour piloter des systèmes autonomes de tri appelés Buffers Séquenceurs (BS). Placés en amont de chaque poste de travail dans la solution GTP, les BS permettent de délocaliser la fonction de tri en aval du stockage, augmentant de facto le débit des flux de sortie. Enfin, nous avons considéré un problème de séquencement consistant à trouver une extension linéaire d'un ordre partiel minimisant une distance avec un ordre donné. Nous proposons de le résoudre par une approche de programmation linéaire en nombres entiers, par la construction de programmes dynamiques et par des heuristiques de type glouton. Une heuristique efficace a été développée en se basant sur des appels itératifs d'un des programmes dynamiques, permettant d'atteindre une solution proche ou égale à l'optimum en un temps très court. L'application de ce problème aux flux de sortie non ordonnés du stockage X-PTS permet de réaliser un pré-tri au niveau des carrousels. Les diverses solutions développées ont été validées par simulation et certaines ont été brevetées et/ou déjà été mises en application dans des entrepôts
The work presented in this PhD thesis deals with optimization problems in the context of internal warehouse logistics. The field is subject to strong competition and extensive growth, driven by the growing needs of the market and favored by automation. SAVOYE builds warehouse storage handling equipment and offers its own GTP (Goods-To-Person) solution for order picking. The solution uses an Automated Storage and Retrieval System (ASRS) called X-Picking Tray System (X-PTS) and automatically routes loads to workstations via carousels to perform sequenced operations. It is a highly complex system of systems with many applications for operational research techniques. All this defines the applicative and theoretical scope of the work carried out in this thesis. In this thesis, we have first dealt with a specific scheduling Job Shop problem with precedence constraints. The particular context of this problem allowed us to solve it in polynomial time with exact algorithms. These algorithms made it possible to calculate the injection schedule of the loads coming from the different storage output streams to aggregate on a carousel in a given order. Thus, the inter-aisle management of the X-PTS storage was improved and the throughput of the load flow was maximized, from the storage to a station. In the sequel of this work, the radix sort LSD (Least Significant Digit) algorithm was studied and a dedicated online sorting algorithm was developed. The second one is used to drive autonomous sorting systems called Buffers Sequencers (BS), which are placed upstream of each workstation in the GTP solution. Finally, a sequencing problem was considered, consisting of finding a linear extension of a partial order minimizing a distance with a given order. An integer linear programming approach, different variants of dynamic programming and greedy algorithms were proposed to solve it. An efficient heuristic was developed based on iterative calls of dynamic programming routines, allowing to reach a solution close or equal to the optimum in a very short time. The application of this problem to the unordered output streams of X-PTS storage allows pre-sorting at the carousel level. The various solutions developed have been validated by simulation and some have been patented and/or already implemented in warehouses

Dans ce travail, l’optimisation de la propulsion et de la commande des AUV (Autonomous Underwater Vehicles en anglais) est développée. Le modèle hydrodynamique de l’AUV est examiné. Egalement, son système de propulsion est étudié et des modèles pour des solutions de propulsion différentes (fixe et vectorielle) sont développés dans le cadre de la mobilité autonome.Le modèle et l’identification de la technologie de propulsion dite fixe sont basés sur un propulseur disponible commercialement. Le système de propulsion vectoriel est basé sur un prototype de propulseur magneto-couplé reconfigurable (PMCR) développé à l’IRDL-ENIB.Une méthode de commande non linéaire utilisant le modèle hydrodynamique de l’AUV est développée et son adaptation à deux systèmes de propulsion est présentée. Des analyses portant sur la commandabilité du robot et l’application de cette commande à différents systèmes sont proposées. L’optimisation globale est utilisée pour trouver des topologies propulsives et des paramètres de commande adaptés à la réalisation de tâches robotiques spécifiques. L’optimisation réalisée permet de trouver des solutions capables d’assurer le suivi de trajectoire et de minimiser la consommation énergétique du robot. L’optimisation utilise un algorithme génétique (algorithme évolutionnaire), une méthode d’optimisation stochastique appliquée ici à la conception orientée tâche de l’AUV. Les résultats de cette optimisation peuvent être utilisés comme une étape préliminaire dans la conception des AUVs, afin de donner des pistes pour améliorer les capacités de la propulsion.La technique d’optimisation est également appliquée au robot RSM (fabriqué au sein de l’IRDL-ENIB) en modifiant seulement quelques paramètres de sa topologie propulsive. Cela afin d’obtenir des configurations de propulsion adaptées au cours d’une seule et même mission aux spécificités locomotrices des tâches rencontrées : reconfiguration dynamique de la propulsion de l’AUV
In this PhD thesis, the optimization of the propulsion and control of AUVs is developed. The hydrodynamic model of the AUVs is examined. Additionally, AUV propulsion topologies are studied and models for fixed and vectorial technology are developed. The fixed technology model is based on an off the shelf device, while the modeled vectorial propulsive system is based on a magnetic coupling thruster prototype developed in IRDL (Institut de Recherche Dupuy de Lôme) at ENI Brest. A control method using the hydrodynamic model is studied, its adaptation to two AUV topologies is presented and considerations about its applicability will be discussed. The optimization is used to find suitable propulsive topologies and control parameters in order to execute given robotic tasks, speeding up the convergence and minimizing the energy consumption. This is done using a genetic algorithm, which is a stochastic optimization method used for task-based design.The results of the optimization can be used as a preliminary stage in the design process of an AUV, giving ideas for enhanced propulsive configurations. The optimization technique is also applied to an IRDL existing robot, modifying only some of the propulsive topology parameters in order to readily adapt it to different tasks, making the AUV dynamically reconfigurable

Les travaux de ce mémoire portent sur une gestion optimisée des blocs opératoires dans un service chirurgical. Les arrivées des patients chaque semaine, la durée des opérations et les temps de séjour des patients sont considérés comme des paramètres assujettis à des incertitudes. Chaque semaine, le gestionnaire hospitalier doit déterminer les blocs chirurgicaux à mettre en service et leur affecter certaines opérations figurant sur la liste d'attente. L'objectif est la minimisation d'une part des coûts liés à la réalisation et au report des opérations, et d'autre part des coûts hospitaliers liés aux ressources chirurgicaux. Lorsque nous considérons que les modèles de programmations mathématiques couramment utilisés dans la littérature n'optimisent pas la performance à long terme des programmes chirurgicaux, nous proposons un nouveau modèle d'optimisation à deux phases combinant le processus de décision Markovien (MDP) et la programmation stochastique. Le MDP de la première phase détermine les opérations à effectuer chaque semaine et minimise les coûts totaux sur un horizon infini. La programmation stochastique de la deuxième phase optimise les affectations des opérations sélectionnées dans les blocs chirurgicaux. Afin de résoudre la complexité des problèmes de grande taille, nous développons un algorithme de programmation dynamique approximatif basé sur l'apprentissage par renforcement et plusieurs autres heuristiques basés sur la génération de colonnes. Nous développons des applications numériques afin d'évaluer le modèle et les algorithmes proposés. Les résultats expérimentaux indiquent que ces algorithmes sont considérablement plus efficaces que les algorithmes traditionnels. Les programmes chirurgicaux du modèle d’optimisation à deux phases sont plus performants de manière significative que ceux d’un modèle de programmation stochastique classique en termes de temps d’attente des patients et de coûts totaux sur le long terme
This thesis deals with the advance scheduling of elective surgeries in an operating theatre that is composed of operating rooms and downstream recovery units. The arrivals of new patients in each week, the duration of each surgery, and the length-of-stay of each patient in the downstream recovery unit are subject to uncertainty. In each week, the surgery planner should determine the surgical blocks to open and assign some of the surgeries in the waiting list to the open surgical blocks. The objective is to minimize the patient-related costs incurred by performing and postponing surgeries as well as the hospital-related costs caused by the utilization of surgical resources. Considering that the pure mathematical programming models commonly used in literature do not optimize the long-term performance of the surgery schedules, we propose a novel two-phase optimization model that combines Markov decision process (MDP) and stochastic programming to overcome this drawback. The MDP model in the first phase determines the surgeries to be performed in each week and minimizes the expected total costs over an infinite horizon, then the stochastic programming model in the second phase optimizes the assignments of the selected surgeries to surgical blocks. In order to cope with the huge complexity of realistically sized problems, we develop a reinforcement-learning-based approximate dynamic programming algorithm and several column-generation-based heuristic algorithms as the solution approaches. We conduct numerical experiments to evaluate the model and algorithms proposed in this thesis. The experimental results indicate that the proposed algorithms are considerably more efficient than the traditional ones, and that the resulting schedules of the two-phase optimization model significantly outperform those of a conventional stochastic programming model in terms of the patients' waiting times and the total costs on the long run

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.
Les gens consacrent une importante part de leur existence à prendre diverses décisions, pouvant affecter leur demande en transport, par exemple les choix de lieux d'habitation et de travail, les modes de transport, les heures de départ, le nombre et type de voitures dans le ménage, les itinéraires ... Les choix liés au transport sont généralement fonction du temps et caractérisés par un grand nombre de solutions alternatives qui peuvent être spatialement corrélées. Cette thèse traite de modèles pouvant être utilisés pour analyser et prédire les choix discrets dans les applications liées aux réseaux de grandes tailles. Les modèles et méthodes proposées sont particulièrement pertinents pour les applications en transport, sans toutefois s'y limiter. Nous modélisons les décisions comme des séquences de choix, dans le cadre des choix discrets dynamiques, aussi connus comme processus de décision de Markov paramétriques. Ces modèles sont réputés difficiles à estimer et à appliquer en prédiction, puisque le calcul des probabilités de choix requiert la résolution de problèmes de programmation dynamique. Nous montrons dans cette thèse qu'il est possible d'exploiter la structure du réseau et la flexibilité de la programmation dynamique afin de rendre l'approche de modélisation dynamique en choix discrets non seulement utile pour représenter les choix dépendant du temps, mais également pour modéliser plus facilement des choix statiques au sein d'ensembles de choix de très grande taille. La thèse se compose de sept articles, présentant divers modèles et méthodes d'estimation, leur application ainsi que des expériences numériques sur des modèles de choix discrets de grande taille. Nous regroupons les contributions en trois principales thématiques: modélisation du choix de route, estimation de modèles en valeur extrême multivariée (MEV) de grande taille et algorithmes d'optimisation non-linéaire. Cinq articles sont associés à la modélisation de choix de route. Nous proposons différents modèles de choix discrets dynamiques permettant aux utilités des chemins d'être corrélées, sur base de formulations MEV et logit mixte. Les modèles résultants devenant coûteux à estimer, nous présentons de nouvelles approches permettant de diminuer les efforts de calcul. Nous proposons par exemple une méthode de décomposition qui non seulement ouvre la possibilité d'estimer efficacement des modèles logit mixte, mais également d'accélérer l'estimation de modèles simples comme les modèles logit multinomiaux, ce qui a également des implications en simulation de trafic. De plus, nous comparons les règles de décision basées sur le principe de maximisation d'utilité de celles sur la minimisation du regret pour ce type de modèles. Nous proposons finalement un test statistique sur les erreurs de spécification pour les modèles de choix de route basés sur le logit multinomial. Le second thème porte sur l'estimation de modèles de choix discrets statiques avec de grands ensembles de choix. Nous établissons que certains types de modèles MEV peuvent être reformulés comme des modèles de choix discrets dynamiques, construits sur des réseaux de structure de corrélation. Ces modèles peuvent alors être estimées rapidement en utilisant des techniques de programmation dynamique en combinaison avec un algorithme efficace d'optimisation non-linéaire. La troisième et dernière thématique concerne les algorithmes d'optimisation non-linéaires dans le cadre de l'estimation de modèles complexes de choix discrets par maximum de vraisemblance. Nous examinons et adaptons des méthodes quasi-Newton structurées qui peuvent être facilement intégrées dans des algorithmes d'optimisation usuels (recherche linéaire et région de confiance) afin d'accélérer le processus d'estimation. Les modèles de choix discrets dynamiques et les méthodes d'optimisation proposés peuvent être employés dans diverses applications de choix discrets. Dans le domaine des sciences de données, des modèles qui peuvent traiter de grands ensembles de choix et des ensembles de choix séquentiels sont importants. Nos recherches peuvent dès lors être d'intérêt dans diverses applications d'analyse de la demande (analyse prédictive) ou peuvent être intégrées à des modèles d'optimisation (analyse prescriptive). De plus, nos études mettent en évidence le potentiel des techniques de programmation dynamique dans ce contexte, y compris pour des modèles statiques, ouvrant la voie à de multiples directions de recherche future.

Les réseaux électriques sont actuellement en pleine mutation du fait de la dérégulation du secteur électrique. L'une des conséquences de la dérégulation est l'apparition de génération d'énergie dispersée dans les réseaux de distribution. Cette introduction de production d'énergie au sein des réseaux de distribution existants n'est pas sans effet sur ceux-ci. Le travail réalisé dans le cadre de cette thèse a permis d'identifier et d'étudier les principaux impacts de la génération d'énergie dispersée sur les réseaux de distribution (impact sur le plan de tension, sur les courants de courtcircuit, sur la stabilité, sur les temps d'élimination critique de défaut, etc.). Ces impacts sont mis en évidence par des simulations numériques et des outils de la théorie petits signaux (valeurs propres et facteurs de participation). De ce travail d'identification, des algorithmes d'optimisation sont utilisés afin d'insérer au mieux cette génération d'énergie dispersée dans les réseaux de distribution. Les algorithmes d'optimisation (algorithme du Minimax, génétique, simplexe et recuit simulé) sont mis en oeuvre pour améliorer le profil de tension des réseaux de distribution en présence de génération d'énergie dispersée. Certains de ces algorithmes sont aussi utilisés pour coordonner les gains contenus dans les régulations des générations d'énergie dispersées afin d'améliorer la stabilité des réseaux. Des indices d'influence sont aussi définis afin d'identifier les zones d'influence de la génération d'énergie dispersée sur les réseaux de distribution.