【Title】A Unified Look at Decomposition Methods for Network Revenue Management

【Speaker】Dr. Huseyin Topaloglu, Associate Professor, School of Operations Research and Information Engineering, Cornell University.

【Host】Dr. Lei Zhao

【Time】May 28, 2013 (Tuesday), 16:00 – 17:00

【Location】Room N412, Shun-de Building

【Abstract】Network revenue management problems involve dynamically allocating the capacity on the flight legs operated over an airline network to the itinerary requests that arrive randomly over time. In the simplest flavor of network revenue management problems, customers arrive over time and each customer requests an itinerary. The goal of the airline is to accept or reject each itinerary request so as to maximize the total expected revenue. Dynamic programming formulations of such problems generally have high dimensional state variables because these formulations require keeping track of the remaining capacity on all of the flight legs. In this talk, we describe and compare two decomposition methods to obtain tractable approximations. The first method decomposes the problem by the flight legs by prorating the revenue of an itinerary over the different flight legs that it uses. The second method uses linear approximations of the value functions, and chooses the slope parameters of the approximations by using the linear programming representation of the underlying dynamic program. Both methods provide upper bounds on the value functions, but the relative strength of these bounds is not clear because while the first method obtains a set of piecewise linear approximations to the value functions, the second method obtains the tightest possible linear approximations. In this talk, we establish an ordering between the upper bounds, demonstrate how we can quickly obtain a good revenue proration scheme for the first decomposition method, and relate the second decomposition method to a fluid approximation to the network revenue management problem..

【Brief bio】Huseyin Topaloglu is an Associate Professor in the School of Operations Research and Information Engineering at Cornell University. He holds a B.Sc. in Industrial Engineering from Bogazici University in Turkey, and a Ph.D. in Operations Research and Financial Engineering from Princeton University. His research interests include stochastic programming and approximate dynamic programming with applications in revenue management, transportation logistics and supply chain management. He teaches courses on simulation modeling, systems engineering, revenue management and dynamic programming. Huseyin Topaloglu is currently serving as associate editors for IIE Transactions, Mathematical Programming Computation, Operations Research and Transportation Science.

Looking forward to your attendance.