 |
|
||||||||||
Finding Approximate Solutions for Large Scale Linear Programs
IFOR Events
Seminar:
'Optimization & Applications'
(see information & program)
Feb 20 - May 28, 2012
IFOR Mitteilungen
This booklet informs about ongoing projects and future events at the IFOR and appears once at the end of the year.
| Author | Vania Dos Santos Eleuterio |
| Abstract |
Linear Programming is one of the most frequently applied tools for modeling and solving real world optimization problems. Nonetheless, most commercially available solvers are often incapable of dealing with large problem sizes, e.g.~millions of variables or hundreds of thousands of constraints, arising in modern applications. To cope, researchers have applied decomposition methods, in particular Lagrange relaxation. In this thesis, we investigate new methods for solving Lagrange relaxations and consequently the Linear Program approximately both from a theoretical as well as a numerical point of view. In the theoretical part, we consider two recently developed primal-dual optimization methods by Nesterov for approximately solving non-smooth convex optimization problems. The first method, called Primal-Dual Subgradient method, is a variation of the standard subgradient method, where the computed subgradients are used not only to create at each step a primal but also a dual solution. This method has a convergence rate of O(1/Є2) to reach an absolute accuracy of Є>0, which is the best possible rate for techniques based on subgradients. The second method, called Excessive Gap method, consists of a smoothing of the objective functions and the usage of optimal gradient schemes. It has a convergence rate of O(1/Є). Using this method, we design a polynomial time approximation scheme for the linear programming relaxation of the Uncapacitated Facility Location problem, which improves the running time dependence on Є from the previously known O(1/Є2) to O(1/Є). Both methods depend on oracles for solving subproblems in each iteration. However, exact oracles are often unavailable. We examine the influence of approximate oracles on the overall convergence of the methods. We show that in order to obtain an overall absolute accuracy of Є, the Primal-Dual Subgradient method requires oracles with a theoretical accuracy of Є2. In contrast, the Excessive Gap method needs an oracle accuracy of Є5 suggesting that it is much less stable. However, we only assumed to know the absolute accuracy of the solution delivered by the oracles. Introducing other requirements may lead to an improvement of these results. In the practical part of the thesis, we examine the application of the methods to the linear programming relaxation of the Uncapacitated Facility Location problem and the Static Traffic Assignment Problem, for which we had access to real world data. As expected by theory, the Excessive Gap method outperformed the Primal-Dual Subgradient method in solving the linear programming relaxation of the Uncapacitated Facility Location problem, for which exact oracles are available. Surprisingly, the Primal-Dual Subgradient method was much better than the Excessive Gap method in solving the Static Traffic Assignment Problem. This can be explained by the subproblems arising in the methods. In the Excessive Gap method, we have to solve Minimum Quadratic Cost Flow problems, which are much harder than the Shortest Paths computations arising in the Primal-Dual Subgradient method. For solving the Minimum Quadratic Cost Flow problem, we considered approximate oracles and we noticed that the Excessive Gap method demonstrated more stability than predicted by theory. As we used a novel formulation of the Static Traffic Assignment problem developed by Nesterov and de Palma, we also compared the characteristics of the obtained traffic assignments to assignments obtained using the traditional Beckmann model. Results showed that the Nesterov and de Palma model better concentrates travel flows leading to more predictable congestions. |
| Download |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
