Detection and Transformation Algorithms for Optimization Software

这笔赠款通过在对人来说自然的模型公式和对计算求解器有效的问题表示之间进行转换，为有助于大规模优化实践的算法的开发提供资金。这些算法可以归类为发现隐藏在模型中的结构的检测方法、将已知结构转换为求解器可以处理的形式的变换方法以及需要这两种方法的一系列中间情况。将使用目前最先进的建模和求解软件，在各种实际感兴趣的优化设置中识别、设计和测试新算法。将利用正在进行的标准化建模系统和求解器之间的通信的努力，以便能够独立于特定软件包的文件和数据格式。具体的研究将集中在广义决策变量域、单个变量的分段线性函数、各种形式的二阶锥规划、一般凸表达式、互补约束以及包括析取、蕴涵、计数和复杂逻辑约束在内的逻辑表达式。如果成功，本研究的结果将带来更自然、更高效的优化建模环境，以及更多功能的解算器，可以直接解决更广泛的问题类型。优化的用户将在科学、工程、经济和商业领域受益，包括生物信息学、化学工程、大规模电路设计、物流、电力管理、机器人、统计、半导体制造、电信和水资源规划。所研究的算法的实现将以开放源码软件的形式发布，这些软件随时可用，并有良好的文档记录。

This grant provides funding for the development of algorithms that contribute to the practice of large-scale optimization, by converting between model formulations that are natural to people and problem representations that are efficient for computational solvers. These algorithms can be categorized as detection methods that find structures hidden in models, transformation methods that convert known structures to forms that solvers can handle, and a range of intermediate situations requiring methods of both kinds. New algorithms will be identified, designed, and tested in diverse optimization settings of practical interest, using the most advanced currently available software for modeling as well as solving. Advantage will be taken of ongoing efforts to standardize communications between modeling systems and solvers, so as to allow for independence from the file and data formats of particular software packages. Specific studies will focus on generalized decision-variable domains, piecewise-linear functions of individual variables, second-order cone programs of varied forms, general convex expressions, complementarity constraints, and logical expressions including disjunctions, implications, counts, and complex logical constraints.If successful, the results of this research will lead to more natural and efficient modeling environments for optimization, and also to more versatile solvers that can directly address a greater range of problem types. Users of optimization will benefit in areas of science, engineering, economics, and business as diverse as bioinformatics, chemical engineering, large-scale circuit design, logistics, power management, robotics, statistics, semiconductor manufacturing, telecommunications, and water resource planning. Implementations of the studied algorithms will be released as open-source software in readily available and well-documented forms.