Linear Optimization: Theory and Applications

线性优化：理论与应用

• 批准号: RGPIN-2020-06846
• 负责人: Deza, Antoine
• 金额: $ 3.13万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750428
• 关键词: Linear; Optimization; Theory; Applications

Data-driven analytics methodologies are presently at the forefront of efficient decision making and decision support in many industries. One prominent set of examples of this state-of-the-art optimization tools that made headway is optimizing energy generation, storage, transmission and delivery, and trading. These applications spread from operational to strategic time horizons. To name a few, optimization combined with other methods such as machine-learning is successfully used to improve the steam assisted gravity drainage (SAGD) process in oil recovery; optimization models and methods play a key role in determining efficient energy storage and dispatch strategies for smart grids, as well as help determine effective layouts for wind and solar farms; quantitative modelling and optimization occupy a central role when trading (energy) financial derivatives. Many data-driven problems can be formulated or approximated as linear optimization problems. There has been substantial progress in recent years in both the theoretical formulations and computational performances, including novel analysis of linear optimization algorithms and models for integer optimization. For instance, insights into the simplex method were obtained, Hirsch conjecture and its continuous analogue were disproved, and central-path following methods were shown to be non-strongly polynomial. Still there remains a dearth of work to further advance linear optimization theory and algorithms. This research proposal aims at searching for new ideas and extensions via the investigation of the strengths and limitations of currently used advanced algorithms. The methodology is based on a combination of novel constructions and worst-case examples, and advanced computational approaches to close the gap between the currently established lower and upper bounds. Worst-case instances appear in many contexts due to their extremal properties. For instance, the structures conjectured to maximize the diameter of lattice polytopes arise in the determination of the complexity of convex matroid optimization, and in the computation of the number of generalized retarded functions in quantum field theory. Combinatorial and high dimensional geometric properties are often unexpected. Computational experiments are therefore a key factor for identifying and proving theoretical properties. Another key focus of this research proposal is to develop new models to handle questions with applications in management sciences, supply-chain and transportation. Specifically, the proposal aims at further exploring optimization formulations to tackle question dealing with assemble-to-order (ATO) system and with shared electric vehicles. The objectives includes to further analyze the impact of component commonality for periodic review ATO systems, and to optimize the locations for charging stations for one-way electric car sharing programs by strategically locating charging stations given estimates of traffic flow.

数据驱动的分析方法目前处于许多行业高效决策和决策支持的前沿。这种取得进展的最先进的优化工具的一个突出例子是优化能源发电、存储、传输和交付以及交易。这些应用程序从运营时间范围扩展到战略时间范围。例如，优化与机器学习等其他方法相结合，成功地用于改进采油中的蒸汽辅助重力泄油（SAGD）工艺；优化模型和方法在确定智能电网高效储能和调度策略方面发挥着关键作用，并有助于确定风电场和太阳能发电场的有效布局；在（能源）金融衍生品交易时，定量建模和优化占据核心作用。许多数据驱动的问题可以用公式表示或近似为线性优化问题。近年来，在理论公式和计算性能方面都取得了实质性进展，包括线性优化算法和整数优化模型的新颖分析。例如，获得了对单纯形法的见解，反驳了赫希猜想及其连续类比，并且证明了中心路径跟踪方法是非强多项式的。 进一步推进线性优化理论和算法仍然缺乏工作。本研究提案旨在通过研究当前使用的先进算法的优点和局限性来寻找新的想法和扩展。该方法基于新颖的结构和最坏情况示例的组合，以及先进的计算方法来缩小当前建立的下限和上限之间的差距。由于其极值特性，最坏情况的实例出现在许多情况下。例如，在确定凸拟阵优化的复杂性以及计算量子场论中广义延迟函数的数量时，会出现被推测最大化晶格多面体直径的结构。组合和高维几何特性常常是意想不到的。因此，计算实验是识别和证明理论特性的关键因素。 该研究计划的另一个重点是开发新模型来处理管理科学、供应链和运输领域的应用问题。具体来说，该提案旨在进一步探索优化公式，以解决按订单组装（ATO）系统和共享电动汽车的问题。目标包括进一步分析组件通用性对定期审查 ATO 系统的影响，并通过根据交通流量估计来战略性地定位充电站，从而优化单向电动汽车共享计划的充电站位置。