Collaborative Research: Generating Stronger Cuts for Nonlinear Programs Via Orthogonal Disjunctions and Lifting Techniques

协作研究：通过正交析取和提升技术为非线性程序生成更强的削减

• 批准号: 0856605
• 负责人: Jean-Philippe Richard
• 金额: $ 20.27万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-01 至 2013-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0856605&HistoricalAwards=false
• 关键词: Collaborative; Research; Generating; Stronger; Cuts

The award is funded under American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The expressive power of nonlinear programs allows the formulation of a remarkable number of application problems from business, science, engineering, and economics. In the presence of nonconvexity, global optimization of such programs poses unmistakable challenges. The objective of this project is to explore how lifting and orthogonal disjunctions can generate computationally tractable cutting planes and convex relaxations for nonlinear programs. The proposed research departs from existing techniques in two crucial dimensions. First, instead of relaxing the left-hand-side and right-hand-side of an inequality independently of each other, tighter relaxations are derived by considering them simultaneously. Second, the techniques do not add new variables, a feature with obvious computational advantages over existing approaches. The objective is to (i) derive, preferably in closed-form, new strong cuts or relaxations for commonly occurring nonlinear structures in areas such as process design and bi-clustering, (ii) characterize structures of nonconvex inequalities where the proposed techniques yield provably tight relaxations, and (iii) design computational procedures that automatically generate strong cuts and evaluate the impact of integrating them in a branch-and-bound algorithm. If successful, this project will provide an impetus to theoretical, algorithmic, and computational advances in deterministic global optimization through research on convexification procedures. A significant expected outcome of this research project is the improvement of the branch-and-bound algorithm for nonconvex programs through the derivation of new and stronger convex relaxations. This project will invigorate the research at the interface of integer programming and global optimization and benefit both communities. The proposed relaxation schemes will be implemented in software enabling the solution of larger nonconvex problems, which, in turn, will impact many application contexts in science, engineering, business, and economics. Work on solving specially-structured problems will bring operational efficiencies in those contexts.

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。非线性程序的表达能力允许从商业、科学、工程和经济学中制定大量的应用问题。在存在非凸性的情况下，全局优化这类程序提出了明确的挑战。该项目的目标是探索提升和正交析取如何为非线性程序生成可计算的切割平面和凸松弛。拟议的研究在两个关键方面偏离了现有技术。首先，而不是放松的左手边和右手边的不等式相互独立，更严格的放松，同时考虑他们。其次，该技术不添加新的变量，这一特征与现有方法相比具有明显的计算优势。目标是（i）最好以封闭形式导出在诸如过程设计和双聚类等领域中常见的非线性结构的新的强切割或松弛，（ii）表征非凸不等式的结构，其中所提出的技术产生可证明的紧松弛，和（iii）设计计算程序，自动生成强切割，并评估将它们集成到分支中的影响，定界算法如果成功的话，这个项目将通过对凸化过程的研究，为确定性全局优化的理论、算法和计算进步提供动力。一个重要的预期成果，这个研究项目是改进的分支定界算法的非凸规划，通过推导新的和更强的凸松弛。该项目将激发整数规划和全局优化接口的研究，并使两个社区受益。所提出的松弛方案将在软件中实现，从而能够解决更大的非凸问题，这反过来将影响科学，工程，商业和经济学中的许多应用环境。解决特殊结构问题的工作将在这些情况下带来运营效率。