Collaborative Research: Reformulation-Linearization Technique for Discrete and Continuous Nonconvex Optimization with Applications

合作研究：离散和连续非凸优化的重构线性化技术及其应用

• 批准号: 0969169
• 负责人: Hanif Sherali
• 金额: $ 15万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-05-15 至 2013-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0969169&HistoricalAwards=false
• 关键词: Collaborative; Research; Reformulation; Linearization; Technique

The research objective of this project is to develop theoretical and computational tools for solving difficult, large-scale, discrete and continuous nonconvex optimization problems. The work will focus on extending and refining a reformulation-linearization/convexification technique (RLT). The RLT is a methodological concept for enhancing problem solvability by constructing improved (tightened) mathematical models in lifted, higher-dimensional spaces. The intent of this study is to address several theoretical and algorithmic developments as well as computational implementation issues related to the RLT, and to identify and exploit mathematical structures that arise from applying it. Specifically, the work will include (1) an extension of the underlying RLT theory through the use of Lagrange interpolating polynomials to characterize structures of the convex hull of discrete sets by way of enhancing the ability to solve integer programs; (2) a unified RLT approach with semidefinite programming constructs along with filtering and basis-reduction techniques that can be used to design effective algorithms for solving discrete as well as continuous nonconvex optimization problems; and (3) the development of tailored methods for solving both discrete and nonlinear problems having certain special structures that arise in particular applications.The results of this study are expected to lead to more efficient tools for solving a variety of challenging nonconvex optimization programs, both discrete and continuous. The discrete programs arise in such diverse areas as clustering, cryptography, facility layout, logical inference, and scheduling, while the continuous nonconvex programs have applications in engineering design, network design, risk management, and Homeland Security. The research will also demonstrate how the algebraic properties of Lagrange interpolating polynomials can be exploited to analyze and generate cuts for mixed-integer and continuous nonlinear programming problems. Conceptually, the research will unify the realms of discrete and continuous optimization, and improve understanding of these domains.

该项目的研究目标是开发解决困难的、大规模的、离散的和连续的非凸优化问题的理论和计算工具。这项工作将侧重于扩展和完善一种重新表述-线性化/凸化技术(RLT)。RLT是一种方法论概念，通过在提升的、更高维的空间中构建改进的(紧凑的)数学模型来增强问题的可解性。这项研究的目的是解决与RLT相关的几个理论和算法发展以及计算实施问题，并确定和利用应用它所产生的数学结构。具体地说，这项工作将包括：(1)通过使用拉格朗日插值多项式来刻画离散集凸壳的结构，以增强求解整数规划的能力，从而扩展了基本的RLT理论；(2)使用半定规划构造以及过滤和基减缩技术的统一RLT方法，可以用于设计求解离散和连续非凸优化问题的有效算法；以及(3)为解决特定应用中出现的具有特定结构的离散和非线性问题的定制方法的发展。这项研究的结果有望导致更有效的工具来解决各种具有挑战性的非凸优化问题，包括离散的和连续的。离散规划出现在集群、密码学、设施布局、逻辑推理、调度等领域，而连续非凸规划在工程设计、网络设计、风险管理、国土安全等领域有着广泛的应用。研究还将演示如何利用拉格朗日插值多项式的代数性质来分析和生成混合整数和连续非线性规划问题的割集。从概念上讲，这项研究将统一离散优化和连续优化的领域，并提高对这些领域的理解。