Linear Optimization: Theory and Applications

线性优化：理论与应用

• 批准号: RGPIN-2020-06846
• 负责人: Deza, Antoine
• 金额: $ 3.13万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741381
• 关键词: 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系统的影响，并通过在交通流量估计的情况下战略性地定位充电站来优化单向电动汽车共享计划的充电站位置。