Home > Department of Mathematics > Seminars > Seminar on Operations Research in 2015

Department of Mathematics
Columbia House
London School of Economics
Houghton Street
London WC2A 2AE, UK

 

Email: maths.info@lse.ac.uk
Tel: +44(0)207 955 7732/7925
Connect with LSE Maths: Twitter

 

Click here for information on how to get to LSE using public transport and maps of the campus

Seminar on Operations Research in 2015

Below you'll find an overview of the past seminars in this series from September 2015. The seminars are listed in reverse chronological order, most recent first.


Tuesday 8 December at 14.00 - Nisheeth Vishnoi (EPFL)
Natural Algorithms for Flows and Linear Programming

In the last few years, there has been a significant interest in the computational abilities of Physarum Polycephalum (a slime mold). This drew from a remarkable experiment which showed that this organism can compute shortest paths in a maze. Subsequently, the workings of Physarum were mathematically modeled as a dynamical system and algorithms inspired by this model were proposed to solve several basic optimization problems such as flows and linear programs.  These dynamics are arrived at by a local and mechanistic interpretation of the inner workings of the slime mold and a global optimization perspective has been  lacking even in the simplest of instances.  If these algorithms could be shown to work, it would raise the tantalizing possibility that nature, via evolution, has developed algorithms that could efficiently solve some of the most complex optimization problems.

In this talk I will focus on the Physarum dynamics for flows and linear programming and prove convergence and complexity bounds for them.  I will also shed some light on the question of how one could arrive at these "local" dynamics from an optimization point of view.

This is based on joint works with Damian Straszak.

Friday 13 November - R. Ravi (CMU)
***Seminar held jointly with the Lunchtime Seminar Series***
Improved Approximations for Graph-TSP in Regular Graphs

A tour in a graph is a connected walk that visits every vertex at least once, and returns to the starting vertex. We describe improved approximation results for a tour with the minimum number of edges in regular graphs. En route we illustrate the main ideas used recently in designing improved approximation algorithms for graph TSP.

Wednesday 28 October - Xue Lu (LSE)
A Generalized Dantzig-Wolfe Decomposition Algorithm for Mixed Integer Programming Problems

We propose a generalized Dantzig-Wolfe decomposition algorithm for mixed integer programming. By generating copy variables, we can reformulate the original problem to have a diagonal structure which is amendable to the Dantzig-Wolfe decomposition. We apply the proposed algorithm to multi-level capacitated lot sizing problem and production routing problem. Rigorous computational results show that our algorithm provides a tighter bound of the optimal solution than all the existing methods.

This is joint work with Zeger Degraeve.

Wednesday 21 October - Eleni Pratsini (IBM Research Ireland)
Big and Fast Data in Cities: Trends and Challenges

It is expected that by 2050, seventy percent of the world's population will live in cities. This causes great challenges but also opportunities as cities look at how information can be used to manage services and communities, and assess the impact and benefits to citizens. The Smarter Cities Technology Centre at IBM Research - Ireland, houses a cross-disciplinary research and development team helping cities around the world to better understand, interconnect and manage their core operational systems such as transport, communication, water and energy and also to improve citizen services and care. In this presentation, we will first explain what defines a "smart city", and through the use of examples, present how the intersection of mathematics, information technology, economics and engineering is used to address some of the challenges in the area of citizen care.

Biography
Eleni Pratsini is Director of IBM Research - Ireland, leading the Smarter Cities Technology Center activities in Exascale Computing, Hybrid Systems, and Risk Analytics. Prior to moving to Ireland, Eleni was Director of Optimization Research at the IBM T.J. Watson Research Center in New York, and Manager of Mathematical and Computational Sciences at IBM Research - Zurich.  Before joining IBM, she was an Associate Professor of Decision Sciences at Miami University (USA) and a Research Scientist at the Institute for Operations Research, at ETH Zurich.

Wednesday 16 September - Jugal Garg (Max Planck Institute for Informatics, Saarbrücken)
Polynomial-Time Complementary Pivot Algorithms for Market Equilibria

We consider the problem of computing equilibria in the Fisher market for utility functions such as linear, spending constraint and perfect price-discrimination. In each case we start with a convex program that captures market equilibria, and in a systematic way, covert it into a linear complementary problem (LCP) formulation. To obtain a polynomial-time algorithm, we depart from previous approaches of pivoting on a single polyhedron associated with the LCP. Instead, we carefully construct a polynomial-length sequence of polyhedra, one containing the other, such that starting from an optimal solution to one allows us to obtain an optimal solution to the next in the sequence in a polynomial number of complementary pivot steps.

This is a joint work with Ruta Mehta, Milind Sohoni and Nisheeth Vishnoi.

Wednesday 2 September - Zeev Nutov (The Open University of Israel)
On LP-Relaxations for the Tree Augmentation Problem
 
In the Tree Augmentation Problem (TAP)  we are given a tree T (a laminar family) on node set V and an edge set E on V. The goal is to augment T by a min-size edge-set F \subseteq E such that T+F is 2-edge-connected. In the weighted version of the problem (Weighted TAP), F should be of minimum weight.
 
Weighted TAP is currently a "threshold" problem in connectivity network design. It is the simplest  problem for which ratio better than 2 is not known, but is  suspected to exist -- since TAP admits ratio 1.5.
 
In this talk I will give a new LP-relaxation for (Weighted) TAP, and describe a  relatively simple dual-fitting 1.75-approximation algorithm for TAP that is based  on this LP-relaxation.

Share:Facebook|Twitter|LinkedIn|