Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université de Montréal

$24,000.00

On the exploitation of uncertainty in exact and approximate optimization

EF 2018-19

Résumé
With the progress in computing power, mathematical programs involving uncertainty are more and more studied as they often better capture the incomplete knowledge of the problem to optimize, especially when it involves future decisions. The proposed research aims to analyze how to handle uncertainty on some practical problems and to improve its exploitation.*A first objective is to take uncertainty into consideration in the context of aircraft arrival sequencing, as the planning horizon is expected to grow during the next years, while an efficient arrival sequencing allows to increase the use of the airport runways while satisfying the operational constraints, especially with respect to safety considerations. More specifically, the scheduling has to be performed in advance in order to limit the air control operations when the aircraft arrives at the airport.*A second, more general, objective is to consider problems involving a sequence of decisions, over stages. The first-stage decisions are the most important, as they have to be implemented first, however we have to take account of the subsequent stages in order to select first-stage actions that will not cause problems in the future. The complexity of such problems increases very fast, even when only two stages are considered, especially if the second-stage programs to solve are complex, possibly involving black-box optimization or simulation. We aim to study how many second-stage problems, corresponding to different scenarios, should be solved in practice to obtain a first-stage solution of sufficient quality, and in the case where the second-stage problem can only be solved approximately, to establish the required accuracy for the second-stage program solution.*We also project to apply the findings in the context of dynamic discrete choice, where a given individual has to operate a sequence of choices between a discrete set of alternatives, possibly time-dependent. A specific application is the route choice estimation problem as recent progress allows to efficiently solve it by means of dynamic programming, as long as the network is perfectly known by the decision-maker at the origin. It has been shown that representing the problem as the choice of a sequence of links delivers a more tractable formulation. Even if the perfect knowledge assumption is restrictive, it opens the possibility to estimate discrete choice sequences in a deterministic setting, using the analogy between shortest path and dynamic programming. The extension to the stochastic situation is not trivial but we aim to capitalize on developments in approximate dynamic programming to address them.*A side objective is also to analyze how random noise can be directly exploited in optimization to diversify the search, as it can help to escape local minimizers in nonlinear problems, by hybridizing random search techniques proposed in derivative free optimization and metaheuristics.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2017-05798
Name nom
Bastin, Fabian
Department département
Informatique et recherche opérationnelle
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
2018
Competition year année de concours
2017
Award amount
24000
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
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
2
Nb partie
5
Application title
On the exploitation of uncertainty in exact and approximate optimization
Keyword
NSERC
Application summary
With the progress in computing power, mathematical programs involving uncertainty are more and more studied as they often better capture the incomplete knowledge of the problem to optimize, especially when it involves future decisions. The proposed research aims to analyze how to handle uncertainty on some practical problems and to improve its exploitation.*A first objective is to take uncertainty into consideration in the context of aircraft arrival sequencing, as the planning horizon is expected to grow during the next years, while an efficient arrival sequencing allows to increase the use of the airport runways while satisfying the operational constraints, especially with respect to safety considerations. More specifically, the scheduling has to be performed in advance in order to limit the air control operations when the aircraft arrives at the airport.*A second, more general, objective is to consider problems involving a sequence of decisions, over stages. The first-stage decisions are the most important, as they have to be implemented first, however we have to take account of the subsequent stages in order to select first-stage actions that will not cause problems in the future. The complexity of such problems increases very fast, even when only two stages are considered, especially if the second-stage programs to solve are complex, possibly involving black-box optimization or simulation. We aim to study how many second-stage problems, corresponding to different scenarios, should be solved in practice to obtain a first-stage solution of sufficient quality, and in the case where the second-stage problem can only be solved approximately, to establish the required accuracy for the second-stage program solution.*We also project to apply the findings in the context of dynamic discrete choice, where a given individual has to operate a sequence of choices between a discrete set of alternatives, possibly time-dependent. A specific application is the route choice estimation problem as recent progress allows to efficiently solve it by means of dynamic programming, as long as the network is perfectly known by the decision-maker at the origin. It has been shown that representing the problem as the choice of a sequence of links delivers a more tractable formulation. Even if the perfect knowledge assumption is restrictive, it opens the possibility to estimate discrete choice sequences in a deterministic setting, using the analogy between shortest path and dynamic programming. The extension to the stochastic situation is not trivial but we aim to capitalize on developments in approximate dynamic programming to address them.*A side objective is also to analyze how random noise can be directly exploited in optimization to diversify the search, as it can help to escape local minimizers in nonlinear problems, by hybridizing random search techniques proposed in derivative free optimization and metaheuristics.