Combinatorial Algorithms for Approximately Solving Certain Classes of Large Scale Linear Programs and Applications

In this research we propose to investigate ways of enhancing the theory and practice of optimization to respond to the new challenges coming from a fast growing spectrum of large scale industrial applications. In particular, our focus is on approximately solving large scale linear programs. Our objective is to design robust algorithms that are fast and scalable, at a negligible loss (if any at all) in the quality of our solutions. We envision to exploit combinatorial properties of special classes of linear programs to quickly deliver very good solutions of very large problem instances. Of particular interests are those linear programs that need to be solved repeatedly as a subroutine within a more complex algorithm (such as is the case for many supply chain management algorithms).

Our project is both theoretical and practical. From a theoretical point of view, we want to design algorithms with provably good properties (speed and approximation guarantee); from a practical point of view we want to test our and other researchers' algorithms and fine tune them to understand how well they can perform in real-world applications. Our investigations, though targeted on large scale linear programs, will also be concerned with rounding techniques and approximation algorithms for the integer versions of the linear programs which in most cases will be NP-hard combinatorial problems. For in-stance, we will be interested in solving the maximum concurrent multicommodity flow problem in which we allow the paths to split commodities (linear program), but we will also be interested in unsplittable solutions, that is, solutions that require that each com-modity chooses only one path (this combinatorial problem is NP-complete). Again our interest is both theoretical and practical. Our research will be, essentially, application oriented. For instance, our work will focus, at least initially, in certain type of multicommodity flow problems that arise in telecom-munication networks and facility location problems that are part of larger supply chain management systems. We expect to study linear programs that come from other research areas such as hard scheduling problems and financial mathematics.

We intend to contribute to other research efforts inside ETH concerning large scale com-puting such as the research groups in Control Theory, Scientific Computing, Theoretical Computer Science and Theory of Communication Networks. As a by-product, we also expect to attract interest from the railroad industry and telecommunications.

Contacts

Vania Dos Santos Eleuterio

Collaborators

• Prof. Fabian Chudak
• Prof. Yurii Nesterov
• Prof. Naveen Garg
• Prof. David Shmoys