Academic literature on the topic 'Algorithme d’apprentissage primal- dual'

Cette thèse découle des défis de recherche opérationnelle de la chaîne logistique Renault. Pour y répondre, nous apportons des contributions à l’architecture et à l’entraînement des réseaux neuronaux avec des couches d’optimisation combinatoire (CO). Nous les combinons avec de nouvelles matheuristiques pour aborder les problèmes de routage d’inventaire de Renault. La Partie I est dédiée aux applications des réseaux neuronaux avec des couches CO en recherche opérationnelle. Nous introduisons une méthode pour approximer les contraintes. Nous utilisons de telles couches pour encoder des politiques pour des processus de décision markoviens à grands espaces d’états et d’actions. Alors que la plupart des études sur les couches CO reposent sur l’apprentissage super- visé, nous introduisons un schéma primal-dual pour la minimisation du risque empirique. Notre algorithme est compatible avec l’apprentissage profond, adapté à de grands espaces combinatoires, et générique. La Partie II est dédiée à la logistique retour des emballages Renault en Europe. Notre politique pour les décisions opérationnelles est basée sur une nouvelle matheuristique pour la variante déterministe du problème. Nous montrons son efficacité sur des instances à grande échelle, que nous publions, avec notre code et nos solutions. Une version de notre politique est utilisée quotidiennement en production depuis mars 2023. Nous abordons aussi la contractualisation de routes au niveau tactique. L’ampleur du problème empêche l’utilisation d’approches classiques d’optimisation stochastique. Nous introduisons un nouvel algorithme basé sur les contributions de la Partie I pour la minimisation du risque empirique
This thesis stems from operations research challenges faced by Renault supply chain. Toaddress them, we make methodological contributions to the architecture and training of neural networks with combinatorial optimization (CO) layers. We combine them with new matheuristics to solve Renault’s industrial inventory routing problems.In Part I, we detail applications of neural networks with CO layers in operations research. We notably introduce a methodology to approximate constraints. We also solve some off- policy learning issues that arise when using such layers to encode policies for Markov decision processes with large state and action spaces. While most studies on CO layers rely on supervised learning, we introduce a primal-dual alternating minimization scheme for empirical risk minimization. Our algorithm is deep learning-compatible, scalable to large combinatorial spaces, and generic. In Part II, we consider Renault European packaging return logistics. Our rolling-horizon policy for the operational-level decisions is based on a new large neighborhood search for the deterministic variant of the problem. We demonstrate its efficiency on large-scale industrialinstances, that we release publicly, together with our code and solutions. We combine historical data and experts’ predictions to improve performance. A version of our policy has been used daily in production since March 2023. We also consider the tactical-level route contracting process. The sheer scale of this industrial problem prevents the use of classic stochastic optimization approaches. We introduce a new algorithm based on methodological contributions of Part I for empirical risk minimization

Après une description de la méthode de Karmarkar, il est montré que la valeur du pas de déplacement peut être largement améliorée. Les principales difficultés pratiques de la méthode sont discutées. Plus particulièrement, l'hypothèse de connaitre, au départ, la valeur optimale de l'objectif. Diverses extensions et variantes sont étudiées dans le but de relaxer l'hypothèse ci-dessus

Dans cette thèse, nous étudions un principe général de convexification permettant de traiter certainsproblèmes variationnels non convexes sur Rd. Grâce à ce principe nous pouvons mettre en oeuvre lespuissantes techniques de dualité et ramener de tels problèmes à des formulations de type primal–dualdans Rd+1, rendant ainsi efficace la recherche numérique de minima globaux. Une théorie de ladualité et des champs de calibration est reformulée dans le cas de fonctionnelles à croissance linéaire.Sous certaines hypothèses, cela nous permet de généraliser un principe d’exclusion découvert parVisintin dans les années 1990 et de réduire le problème initial à la minimisation d’une fonctionnelleconvexe sur Rd. Ce résultat s’applique notamment à une classe de problèmes à frontière libre oumulti-phasique donnant lieu à des tests numériques très convaincants au vu de la qualité des interfacesobtenues. Ensuite nous appliquons la théorie des calibrations à un problème classique de surfacesminimales avec frontière libre et établissons de nouveaux résultats de comparaison avec sa varianteoù la fonctionnelle des surfaces minimales est remplacée par la variation totale. Nous généralisonsla notion de calibrabilité introduite par Caselles-Chambolle et Al. et construisons explicitementune solution duale pour le problème associé à la seconde fonctionnelle en utilisant un potentiellocalement Lipschitzien lié à la distance au cut-locus. La dernière partie de la thèse est consacrée auxalgorithmes d’optimisation de type primal-dual pour la recherche de points selle, en introduisant denouvelles variantes plus efficaces en précision et temps calcul. Nous avons en particulier introduit unevariante semi-implicite de la méthode d’Arrow-Hurwicz qui permet de réduire le nombre d’itérationsnécessaires pour obtenir une qualité satisfaisante des interfaces. Enfin nous avons traité la nondifférentiabilité structurelle des Lagrangiens utilisés à l’aide d’une méthode géométrique de projectionsur l’épigraphe offrant ainsi une alternative aux méthodes classiques de régularisation
In this thesis, we study a general principle of convexification to treat certain non convex variationalproblems in Rd. Thanks to this principle we are able to enforce the powerful duality techniques andbring back such problems to primal-dual formulations in Rd+1, thus making efficient the numericalsearch of a global minimizer. A theory of duality and calibration fields is reformulated in the caseof linear-growth functionals. Under suitable assumptions, this allows us to revisit and extend anexclusion principle discovered by Visintin in the 1990s and to reduce the original problem to theminimization of a convex functional in Rd. This result is then applied successfully to a class offree boundary or multiphase problems that we treat numerically obtaining very accurate interfaces.On the other hand we apply the theory of calibrations to a classical problem of minimal surfaceswith free boundary and establish new results related to the comparison with its variant where theminimal surfaces functional is replaced by the total variation. We generalize the notion of calibrabilityintroduced by Caselles-Chambolle and Al. and construct explicitly a dual solution for the problemassociated with the second functional by using a locally Lipschitzian potential related to the distanceto the cut-locus. The last part of the thesis is devoted to primal-dual optimization algorithms forthe search of saddle points, introducing new more efficient variants in precision and computationtime. In particular, we experiment a semi-implicit variant of the Arrow-Hurwicz method whichallows to reduce drastically the number of iterations necessary to obtain a sharp accuracy of theinterfaces. Eventually we tackle the structural non-differentiability of the Lagrangian arising fromour method by means of a geometric projection method on the epigraph, thus offering an alternativeto all classical regularization methods

Dans cette thèse, nous étudions un principe général de convexification permettant de traiter certainsproblèmes variationnels non convexes sur Rd. Grâce à ce principe nous pouvons mettre en oeuvre lespuissantes techniques de dualité et ramener de tels problèmes à des formulations de type primal–dualdans Rd+1, rendant ainsi efficace la recherche numérique de minima globaux. Une théorie de ladualité et des champs de calibration est reformulée dans le cas de fonctionnelles à croissance linéaire.Sous certaines hypothèses, cela nous permet de généraliser un principe d’exclusion découvert parVisintin dans les années 1990 et de réduire le problème initial à la minimisation d’une fonctionnelleconvexe sur Rd. Ce résultat s’applique notamment à une classe de problèmes à frontière libre oumulti-phasique donnant lieu à des tests numériques très convaincants au vu de la qualité des interfacesobtenues. Ensuite nous appliquons la théorie des calibrations à un problème classique de surfacesminimales avec frontière libre et établissons de nouveaux résultats de comparaison avec sa varianteoù la fonctionnelle des surfaces minimales est remplacée par la variation totale. Nous généralisonsla notion de calibrabilité introduite par Caselles-Chambolle et Al. et construisons explicitementune solution duale pour le problème associé à la seconde fonctionnelle en utilisant un potentiellocalement Lipschitzien lié à la distance au cut-locus. La dernière partie de la thèse est consacrée auxalgorithmes d’optimisation de type primal-dual pour la recherche de points selle, en introduisant denouvelles variantes plus efficaces en précision et temps calcul. Nous avons en particulier introduit unevariante semi-implicite de la méthode d’Arrow-Hurwicz qui permet de réduire le nombre d’itérationsnécessaires pour obtenir une qualité satisfaisante des interfaces. Enfin nous avons traité la nondifférentiabilité structurelle des Lagrangiens utilisés à l’aide d’une méthode géométrique de projectionsur l’épigraphe offrant ainsi une alternative aux méthodes classiques de régularisation
In this thesis, we study a general principle of convexification to treat certain non convex variationalproblems in Rd. Thanks to this principle we are able to enforce the powerful duality techniques andbring back such problems to primal-dual formulations in Rd+1, thus making efficient the numericalsearch of a global minimizer. A theory of duality and calibration fields is reformulated in the caseof linear-growth functionals. Under suitable assumptions, this allows us to revisit and extend anexclusion principle discovered by Visintin in the 1990s and to reduce the original problem to theminimization of a convex functional in Rd. This result is then applied successfully to a class offree boundary or multiphase problems that we treat numerically obtaining very accurate interfaces.On the other hand we apply the theory of calibrations to a classical problem of minimal surfaceswith free boundary and establish new results related to the comparison with its variant where theminimal surfaces functional is replaced by the total variation. We generalize the notion of calibrabilityintroduced by Caselles-Chambolle and Al. and construct explicitly a dual solution for the problemassociated with the second functional by using a locally Lipschitzian potential related to the distanceto the cut-locus. The last part of the thesis is devoted to primal-dual optimization algorithms forthe search of saddle points, introducing new more efficient variants in precision and computationtime. In particular, we experiment a semi-implicit variant of the Arrow-Hurwicz method whichallows to reduce drastically the number of iterations necessary to obtain a sharp accuracy of theinterfaces. Eventually we tackle the structural non-differentiability of the Lagrangian arising fromour method by means of a geometric projection method on the epigraph, thus offering an alternativeto all classical regularization methods

Le but de cette thèse est de développer de nouvelles techniques d'éclatement d'opérateurs multivoques pour résoudre des problèmes d'inclusion monotone structurés dans des espaces hilbertiens. La dualité au sens des inclusions monotones tient une place essentielle dans ce travail et nous permet d'obtenir des décompositions qui ne seraient pas disponibles via une approche purement primale. Nous développons plusieurs algorithmes à métrique fixe ou variable dans un cadre unifié, et montrons en particulier que de nombreuses méthodes existantes sont des cas particuliers de la méthode explicite--implicite formulée dans des espaces produits adéquats. Les méthodes proposées sont appliquées aux problèmes d'inéquations variationnelles, aux problèmes de minimisation, aux problèmes inverses, aux problèmes de traitement du signal, aux problèmes d'admissibilité et aux problèmes de meilleure approximation. Dans un second temps, nous introduisons une notion de suite quasi-fejérienne à métrique variable et analysons ses propriétés asymptotiques. Ces résultats nous permettent d'obtenir des extensions de méthodes d'éclatement aux problèmes où la métrique varie à chaque itération.

L’estimation des matrices origine-destination (OD) est un sujet de recherche important depuis les années 1950. En effet, ces tableaux à deux entrées recensent la demande de transport d'une zone géographique donnée et sont de ce fait un élément clé de l'ingénierie du trafic. Historiquement, les seules données disponibles pour leur estimation par les statistiques étaient les comptages de véhicules par les boucles magnétiques. Ce travail s'inscrit alors dans le contexte de l'installation à Brisbane de plus de 600 détecteurs Bluetooth qui ont la capacité de détecter et d'identifier les appareils électroniques équipés de cette technologie.Dans un premier temps, il explore la possibilité offerte par ces détecteurs pour les applications en ingénierie du transport en caractérisant ces données et leurs bruits. Ce projet aboutit, à l'issue de cette étude, à une méthode de reconstruction des trajectoires des véhicules équipés du Bluetooth à partir de ces seules données. Dans un second temps, en partant de l'hypothèse que l'accès à des échantillons importants de trajectoires va se démocratiser, cette thèse propose d'étendre la notion de matrice OD à celle de matrice OD par lien afin de combiner la description de la demande avec celle de l'utilisation du réseau. Reposant sur les derniers outils méthodologies développés en optimisation convexe, nous proposons une méthode d'estimation de ces matrices à partir des trajectoires inférées par Bluetooth et des comptages routiers.A partir de peu d'hypothèses, il est possible d'inférer ces nouvelles matrices pour l'ensemble des utilisateurs d'un réseau routier (indépendamment de leur équipement en nouvelles technologies). Ce travail se distingue ainsi des méthodes traditionnelles d'estimation qui reposaient sur des étapes successives et indépendantes d'inférence et de modélisation
Origin Destination matrix estimation is a critical problem of the Transportation field since the fifties. OD matrix is a two-entry table taking census of the zone-to-zone traffic of a geographic area. This traffic description tools is therefore paramount for traffic engineering applications. Traditionally, the OD matrix estimation has solely been based on traffic counts collected by networks of magnetic loops. This thesis takes place in a context with over 600 Bluetooth detectors installed in the City of Brisbane. These detectors permit in-car Bluetooth device detection and thus vehicle identification.This manuscript explores first, the potentialities of Bluetooth detectors for Transport Engineering applications by characterising the data, their noises and biases. This leads to propose a new methodology for Bluetooth equipped vehicle trajectory reconstruction. In a second step, based on the idea that probe trajectories will become more and more available by means of new technologies, this thesis proposes to extend the concept of OD matrix to the one of link dependent origin destination matrix that describes simultaneously both the traffic demand and the usage of the network. The problem of LOD matrix estimation is formulated as a minimisation problem based on probe trajectories and traffic counts and is then solved thanks to the latest advances in nonsmooth convex optimisation.This thesis demonstrates that, with few hypothesis, it is possible to retrieve the LOD matrix for the whole set of users in a road network. It is thus different from traditional OD matrix estimation approaches that relied on successive steps of modelling and of statistical inferences