10/13/16 | 4:15pm | E51-315 
Reception to follow.

Abstract: Although bilevel programs are mostly intractable, some instances are amenable to efficient solution procedures, either exact or heuristic. In this presentation, I focus on the approximation of hard nonlinear instances by more tractable formulations in mixed integer linear format (MILP). The algorithmic framework is illustrated on a competitive location problem that involves queueing at the facilities, and where users achieve a stochastic equilibrium with respect to travel delays and service levels. First, taking advantage of the model's structure, I describe a MILP reformulation that allows the resolution of small instances. Next, it is shown that a single-level heuristic that yields total control to the users perform very well in practice, although it can be arbitrarily bad in the worst case. Finally, I show how the methodological framework developed for this application extends to other situations.

Patrice Marcotte

Professor
University of Montreal

Bio: Patrice Marcotte is professor at the Computer Science and Operations Research department of the University of Montreal. He has contributed to the theoretical literature in variational inequalities and bilevel programming, with applications in traffic assignment, revenue management, network pricing, and energy. He has also published on optimal strategies in badminton, and is the co-author of two cycling guides. He currently sits on the editorial boards of Operations Research, Transportation Science, JOTA, Operations Research Letters, and EJCO. His current research focuses on the design of efficient algorithms, either exact or heuristic, for addressing nonlinear mixed-integer bilevel programs that involve utility-maximizing users.