Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université de Montréal

$41,000.00

Behavioural-based mathematical programming: algorithmics and applications

FY 2017-18

Summary
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 considerthe problem of setting tolls on the links of a highway. In order to optimize the revenue, onemust 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 numberof 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 behaviourvaries across the population or when congestion occurs. Such problems fit the framework of bilevelmathematical programs, or leader-follower games. In these games, the leader factors into itsoptimization 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 controlledby 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 goalif they do not consider the alternatives faced by the citizens. For instance, following a stifftax increase of cigarettes that triggered smuggling, resulting in a decrease of tax revenues and anactual increase in cigarette consumption, contrary to the goal pursued! Despite their capability to address important industrial, commercial and social issues, bilevel models are limitedby their computational complexity. It is therefore important to design smart algorithms that takeadvantage of each application's structure. For a class of problems that I am studying, one approachconsists in approximating the original model by a more tractable one, and then make progress from its solutiontowards the solution of the original. Other strategies, that are based on the combinatorial nature ofbilevel problems, will also be investigated. All of them will be applied to practical instances inenergy, facility location (including health care) and transportation.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-05073
Name nom
Marcotte, Patrice
Department département
Informatique et recherche opérationnelle - Informatique et recherche opérationne
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
41000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
1
Nb partie
5
Application title
Behavioural-based mathematical programming: algorithmics and applications
Keyword
NSERC
Application summary
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 considerthe problem of setting tolls on the links of a highway. In order to optimize the revenue, onemust 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 numberof 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 behaviourvaries across the population or when congestion occurs. Such problems fit the framework of bilevelmathematical programs, or leader-follower games. In these games, the leader factors into itsoptimization 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 controlledby 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 goalif they do not consider the alternatives faced by the citizens. For instance, following a stifftax increase of cigarettes that triggered smuggling, resulting in a decrease of tax revenues and anactual increase in cigarette consumption, contrary to the goal pursued! Despite their capability to address important industrial, commercial and social issues, bilevel models are limitedby their computational complexity. It is therefore important to design smart algorithms that takeadvantage of each application's structure. For a class of problems that I am studying, one approachconsists in approximating the original model by a more tractable one, and then make progress from its solutiontowards the solution of the original. Other strategies, that are based on the combinatorial nature ofbilevel problems, will also be investigated. All of them will be applied to practical instances inenergy, facility location (including health care) and transportation.