On the exploitation of uncertainty in exact and approximate optimization

关于精确和近似优化中不确定性的利用

• 批准号: RGPIN-2017-05798
• 负责人: Bastin, Fabian
• 金额: $ 1.75万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=644769
• 关键词: exploitation; uncertainty; exact; 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.

随着计算能力的提高，涉及不确定性的数学规划得到了越来越多的研究，因为它们往往能更好地捕捉问题的不完整知识进行优化，特别是当涉及未来决策时。该研究旨在分析如何处理一些实际问题的不确定性，并提高其利用率。第一个目标是在飞机抵达排序方面考虑到不确定性，因为预计未来几年规划范围将扩大，而有效的抵达排序可以增加机场跑道的使用，同时满足运营限制，特别是安全方面的考虑。更具体地说，必须提前执行调度，以便在飞机到达机场时限制空中管制操作。第二个更一般的目标是考虑涉及一系列决策的问题，分阶段进行。第一阶段的决定是最重要的，因为它们必须首先执行，但我们必须考虑到随后的阶段，以便选择不会在未来造成问题的第一阶段行动。即使只考虑两个阶段，这类问题的复杂性也会增加得非常快，特别是如果要解决的第二阶段程序很复杂，可能涉及黑盒优化或模拟。我们的目标是研究在实践中应该解决多少与不同场景相对应的第二阶段问题，以获得足够质量的第一阶段解，并且在第二阶段问题只能近似解决的情况下，建立第二阶段程序解所需的精度。我们还计划将研究结果应用于动态离散选择的背景下，其中一个给定的个人必须在一组离散的替代品之间进行一系列选择，可能是时间依赖的。一个具体的应用是路线选择估计问题，因为最近的进展允许通过动态规划来有效地解决它，只要网络是由决策者在原点完全已知的。它已被证明，代表的问题，作为一个序列的链接的选择提供了一个更易于处理的配方。即使完美的知识假设是限制性的，它打开了一个确定性的设置，估计离散的选择序列的可能性，使用最短路径和动态规划之间的类比。扩展到随机情况并不是微不足道的，但我们的目标是利用近似动态规划的发展来解决它们。一个侧面的目标也是分析如何随机噪声可以直接利用优化多样化的搜索，因为它可以帮助逃避局部极小值的非线性问题，通过混合随机搜索技术提出的无导数优化和metacetanistics。