Decomposition-Based Optimization: A New Solver Paradigm

基于分解的优化：新的求解器范式

• 批准号: 1130914
• 负责人: Theodore Ralphs
• 金额: $ 25万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-10-01 至 2014-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1130914&HistoricalAwards=false
• 关键词: Decomposition; Based; Optimization; New; Solver

The research objectives of this award are (1) to develop advanced methodologies based on decomposition for the solution of large-scale optimization problems, (2) to integrate these methodologies with current state-of-the-art techniques, and (3) to make these methodologies accessible to users through modeling languages and extensions to the standard APIs (Application Program Interfaces) provided by current state-of-the-art optimization software. Although decomposition techniques have proven very effective in certain applications, these methods have not been adopted in commercial solvers due to lack of a mathematical theory integrating other advanced techniques; difficulties in implementation; challenges associated with automatic detection of model structure; and lack of support in modeling languages for expressing decomposition strategies. This research aims to overcome these challenges and to develop practical methodologies and implementations of advanced methods, along with support for modeling by practitioners.The impact of this research will be in allowing practitioners to have access to powerful methods of optimizing large-scale systems, whose ever-increasing complexity is being driven in practice by the increased availability of data and storage. Among other things, decomposition methods are the methods of choice for the optimization of large-scale systems consisting of smaller subsystems linked by relatively few system-level constraints. One typical example of such a system is a logistics system consisting of geographically distributed warehouses, each with an associated fleet of delivery vehicles. When the system-level constraints are relaxed, the underlying optimization problem decomposes, leading to more efficient solution methods. Decomposition may provide a practical approach to parallelization and thus a means of capitalizing on the commoditization of multi-core/multi-processor architectures. All methodologies will be implemented in open source and distributed through the COIN-OR open source repository (http://www.coin-or.org), ensuring wide dissemination.

该奖项的研究目标是(1)开发基于分解的高级方法来解决大规模优化问题，(2)将这些方法与当前最先进的技术相结合，以及(3)通过建模语言和对当前最先进的优化软件提供的标准API(应用程序接口)的扩展，使用户可以使用这些方法。虽然分解技术在某些应用中被证明是非常有效的，但这些方法还没有被商业求解器采用，原因是缺乏整合其他先进技术的数学理论；实现困难；与模型结构自动检测相关的挑战；以及缺乏对表达分解策略的建模语言的支持。这项研究旨在克服这些挑战，开发实用的方法和高级方法的实现，并支持从业者进行建模。这项研究的影响将是使从业者能够获得优化大规模系统的强大方法，其日益增长的复杂性实际上是由数据和存储的可用性增加推动的。在其他方面，分解方法是优化由相对较少的系统级约束连接的较小子系统组成的大系统的选择方法。这种系统的一个典型例子是由地理上分散的仓库组成的物流系统，每个仓库都有一支相关的运输车辆车队。当系统级约束放松时，底层优化问题就会分解，从而产生更有效的求解方法。分解可以提供一种实用的并行化方法，从而提供一种利用多核/多处理器架构的商品化的手段。所有方法都将以开源方式实施，并通过硬币或开源储存库(http://www.coin-or.org)，)分发，以确保广泛传播。