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
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679900
• 关键词: 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.

随着计算能力的进展，涉及不确定性的数学程序越来越多地研究，因为它们通常更好地捕获了对问题的不完整知识以进行优化，尤其是在涉及未来决策时。拟议的研究旨在分析如何处理某些实际问题的不确定性并改善其剥削。******的第一个目标是在飞机到达测序的背景下考虑不确定性，因为预计计划范围将在未来几年内增长，而有效的序列可以提高机场跑道的使用，同时又可以满足限制性的限制。更具体地说，必须提前执行调度，以限制飞机到达机场时的空气控制操作。******第二个更通用的目标是考虑涉及一系列决策的问题，分期阶段。第一阶段的决策是最重要的，因为必须先实施，但是我们必须考虑后续阶段，以便选择将来不会引起问题的第一阶段动作。即使仅考虑两个阶段，尤其是解决第二阶段的程序很复杂，可能涉及黑盒优化或仿真的情况下，这种问题的复杂性也会很快增加，尤其是在考虑两个阶段。我们的目的是研究在实践中应解决多少个与不同情景相对应的第二阶段问题，以获得足够质量的第一阶段解决方案，如果只能解决第二阶段问题，则只能解决第二阶段问题，以确定第二阶段程序解决方案所需的准确性。时间依赖。特定的应用程序是路由选择估计问题，因为最近的进度允许通过动态编程有效地解决该问题，只要该网络在原点上完全知道网络。已经表明，将问题表示为一系列链接的选择提供了更容易处理的公式。即使完美的知识假设是限制性的，它也可以使用最短路径和动态编程之间的类比在确定性设置中估算离散选择序列的可能性。扩展到随机情况并不是微不足道的，但我们旨在利用近似动态编程中的发展来解决它们。******一个侧面目标还可以分析如何在优化中直接利用随机噪声来优化搜索以使搜索多样化，因为它可以帮助避免在非线性问题中逃避范围的搜索量，并在范围内降低了范围的搜索技术，并在范围内降低了范围的范围。