Behavioural-based mathematical programming: algorithmics and applications

点击翻译按钮获取中文摘要

The aim of my research is to study, from both the theoretical and computational points of view, decision problems that involve agents with conflicting objectives. To fix ideas, let us consider the problem of setting tolls on the links of a highway. In order to optimize the revenue, one must take into account the behaviour of drivers, who want to minimize their own travel cost. If tolls are low, revenue will be low. If tolls are high, revenue will also be low, due to the low number of drivers for which the highway will be attractive. One must then strike the right balance, taking into account user behaviour. Although it has been shown that, even in that simple setting, the problem is hard to solve, the situation becomes all the more complex when behaviour varies across the population or when congestion occurs. Such problems fit the framework of bilevel mathematical programs, or leader-follower games. In these games, the leader factors into its optimization problem the rational reaction of an adversary or a population impacted by his decisions. This reaction would be the drivers' path choices in our introductory example. This situation is ubiquitous. Indeed, it is the exception that all variables of a problem are controlled by the leader. ******Bilevel programming has been applied to areas as diverse as energy (optimizing the efficiency of a network, monitoring the 'smart grid'), urban planning, health care, transportation (rail, airlines). Governments use regulations and taxes to increase global welfare, and fail to achieve this goal if they do not consider the alternatives faced by the citizens. For instance, following a stiff tax increase of cigarettes that triggered smuggling, resulting in a decrease of tax revenues and an actual increase in cigarette consumption, contrary to the goal pursued!******Despite their capability to address important industrial, commercial and social issues, bilevel models are limited by their computational complexity. It is therefore important to design smart algorithms that take advantage of each application's structure. For a class of problems that I am studying, one approach consists in approximating the original model by a more tractable one, and then make progress from its solution towards the solution of the original. Other strategies, that are based on the combinatorial nature of bilevel problems, will also be investigated. All of them will be applied to practical instances in energy, facility location (including health care) and transportation.