Spelling suggestions: "subject:"bundle methods"" "subject:"rundle methods""
1 |
Dynamic Graph Generation and an Asynchronous Parallel Bundle Method Motivated by Train TimetablingFischer, Frank 12 July 2013 (has links) (PDF)
Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems.
The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes.
The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions.
Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.
|
2 |
Optimisation convexe non-différentiable et méthodes de décomposition en recherche opérationnelle / Convex nonsmooth optimization and decomposition methods in operations researchZaourar, Sofia 04 November 2014 (has links)
Les méthodes de décomposition sont une application du concept de diviser pour régner en optimisation. L'idée est de décomposer un problème d'optimisation donné en une séquence de sous-problèmes plus faciles à résoudre. Bien que ces méthodes soient les meilleures pour un grand nombre de problèmes de recherche opérationnelle, leur application à des problèmes réels de grande taille présente encore de nombreux défis. Cette thèse propose des améliorations méthodologiques et algorithmiques de méthodes de décomposition. Notre approche est basée sur l'analyse convexe et l'optimisation non-différentiable. Dans la décomposition par les contraintes (ou relaxation lagrangienne) du problème de planification de production électrique, même les sous-problèmes sont trop difficiles pour être résolus exactement. Mais des solutions approchées résultent en des prix instables et chahutés. Nous présentons un moyen simple d'améliorer la structure des prix en pénalisant leurs oscillations, en utilisant en particulier une régularisation par variation totale. La consistance de notre approche est illustrée sur des problèmes d'EDF. Nous considérons ensuite la décomposition par les variables (ou de Benders) qui peut avoir une convergence excessivement lente. Avec un point de vue d'optimisation non-différentiable, nous nous concentrons sur l'instabilité de l'algorithme de plans sécants sous-jacent à la méthode. Nous proposons une stabilisation quadratique de l'algorithme de Benders, inspirée par les méthodes de faisceaux en optimisation convexe. L'accélération résultant de cette stabilisation est illustrée sur des problèmes de conception de réseau et de localisation de plates-formes de correspondance (hubs). Nous nous intéressons aussi plus généralement aux problèmes d'optimisation convexe non-différentiable dont l'objectif est coûteux à évaluer. C'est en particulier une situation courante dans les procédures de décomposition. Nous montrons qu'il existe souvent des informations supplémentaires sur le problème, faciles à obtenir mais avec une précision inconnue, qui ne sont pas utilisées dans les algorithmes. Nous proposons un moyen d'incorporer ces informations incontrôlées dans des méthodes classiques d'optimisation convexe non-différentiable. Cette approche est appliquée avec succès à desproblèmes d'optimisation stochastique. Finalement, nous introduisons une stratégie de décomposition pour un problème de réaffectation de machines. Cette décomposition mène à une nouvelle variante de problèmes de conditionnement vectoriel (vectorbin packing) où les boîtes sont de taille variable. Nous proposons des heuristiques efficaces pour ce problème, qui améliorent les résultats de l'état de l'art du conditionnement vectoriel. Une adaptation de ces heuristiques permet de construire des solutions réalisables au problème de réaffectation de machines de Google. / Decomposition methods are an application of the divide and conquer principle to large-scale optimization. Their idea is to decompose a given optimization problem into a sequence of easier subproblems. Although successful for many applications, these methods still present challenges. In this thesis, we propose methodological and algorithmic improvements of decomposition methods and illustrate them on several operations research problems. Our approach heavily relies on convex analysis and nonsmooth optimization. In constraint decomposition (or Lagrangian relaxation) applied to short-term electricity generation management, even the subproblems are too difficult to solve exactly. When solved approximately though, the obtained prices show an unstable noisy behaviour. We present a simple way to improve the structure of the prices by penalizing their noisy behaviour, in particular using a total variation regularization. We illustrate the consistency of our regularization on real-life problems from EDF. We then consider variable decomposition (or Benders decomposition), that can have a very slow convergence. With a nonsmooth optimization point of view on this method, we address the instability of Benders cutting-planes algorithm. We present an algorithmic stabilization inspired by bundle methods for convex optimization. The acceleration provided by this stabilization is illustrated on network design andhub location problems. We also study more general convex nonsmooth problems whose objective function is expensive to evaluate. This situation typically arises in decomposition methods. We show that it often exists extra information about the problem, cheap but with unknown accuracy, that is not used by the algorithms. We propose a way to incorporate this coarseinformation into classical nonsmooth optimization algorithms and apply it successfully to two-stage stochastic problems.Finally, we introduce a decomposition strategy for the machine reassignment problem. This decomposition leads to a new variant of vector bin packing problems, where the bins have variable sizes. We propose fast and efficient heuristics for this problem that improve on state of the art results of vector bin packing problems. An adaptation of these heuristics is also able to generate feasible solutions for Google instances of the machine reassignment problem.
|
3 |
Dynamic Graph Generation and an Asynchronous Parallel Bundle Method Motivated by Train TimetablingFischer, Frank 09 July 2013 (has links)
Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems.
The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes.
The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions.
Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.
|
4 |
[en] CONVEX ANALYSIS AND LIFT-AND-PROJECT METHODS FOR INTEGER PROGRAMMING / [es] ANÁLISIS CONVEXA Y MÉTODOS LIFT-AND-PROJECT PARA PROGRAMACIÓN ENTERA / [pt] ANÁLISE CONVEXA E MÉTODOS LIFT-AND-PROJECT PARA PROGRAMAÇÃO INTEIRAPABLO ANDRES REY 06 August 2001 (has links)
[pt] Algoritmos para a resolução de problemas de programação
mista 0-1 gerais baseados em cortes derivados dos métodos
lift-and-project, tem se mostrado bastante eficientes na
prática. Estes cortes são gerados resolvendo um problema
que depende de uma certa normalização. Desde um ponto de
vista teórico, o bom comportamento destes algoritmos não
foi completamente compreendido, especialmente no que diz
respeito à normalização. Neste trabalho consideramos
normalizações gerais definidas por um conjunto convexo
fechado arbitrário, estendendo assim a análise teórica
desenvolvida nos anos noventa. Apresentamos um marco
teórico que abarca todas as normalizações previamente
estudadas e introduzimos novas normalizações, analisando
as propriedades dos cortes associados.Introduzimos também
uma nova fórmula de atualização do parâmetro proximal
para uma variante dos métodos de feixes. Estes métodos
são bem conhecidos pela sua eficiência na resolução de
problemas de otimização não diferenciável. Por último,
propomos uma metodologia para eliminr soluções
redundantes de programas inteiros combinatórios. Nossa
proposta baseia-se na utilização da informação de
simetria do problema, eliminam a simetria sem prejudicar
a solução do problema inteiro. / [en] Algorithms for general 0-1 mixed integer programs can be
successfully developed by using lift-and-project methods to
generate cuts. Cuts are generated by solving a cut-
generation-program that depends on a certain normalization.
From a theoretical point of view, the good numerical
behavior of these cuts is not completely understood yet,
specially, concerning to the normalization chosen. We
consider a general normalization given by an arbitrary
closed convex set, extending the theory developed in the
90's. We present a theoretical framework covering a wide
group of already known normalizations. We also introduce
new normalizations and analyze the properties of the
associated cuts. In this work, we also propose a new
updating rule for the prox parameter of a variant of the
proximal bundle methods, making use of all the information
available at each iteration. Proximal bundle methods are
well known for their efficiency in nondifferentiable
optimization. Finally, we introduce a way to eliminate
redundant solutions ( due to geometrical symmetries ) of
combinatorial integer program. This can be done by using
the information about the problem symmetry in order to
generate inequalities, which added to the formulation of
the problem, eliminate this symmetry without affecting
solution of the integer problem. / [es] Los algoritmos para la resolución de problemas de programación mixta 0-1 generales que utilizan
cortes derivados de los métodos lift-and-project, se han mostrado bastante eficientes en la práctica.
Estos cortes se generan resolviendo un problema que depende de una cierta normalización. Desde el
punto de vista teórico, el buen comportamiento de estos algoritmos no fue completamente
comprendido, especialmente respecto a la normalización. En este trabajo consideramos
normalizaciones generales definidas por un conjunto convexo cerrado arbitrario, extendiendo así el
análisis teórico desarrollado en los años noventa. Presentamos un marco teórico que abarca todas las
normalizaciones previamente estudiadas e introducimos nuevas normalizaciones, analizando las
propiedades de los cortes asociados. Introducimos una nueva fórmula de actualización del parámetro
de. Estoss métodos son bien conocidos por su eficiencia en la resolución de problemas de
optimización no diferenciable. Por último, proponemos una metodología para eliminar soluciones
redundantes de programas enteros combinatorios. Nuestra propuesta se basa en la utilización de la
información de simetría del problema, eliminan la simetría sin perjudicar la solución del problema
entero.
|
Page generated in 0.0316 seconds