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.