On the exploitation of uncertainty in exact and approximate optimization

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

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.