Collaborative Research: Novel Tighter Relaxations for Complementarity Constraints with Applications to Nonlinear and Bilevel Programming

协作研究：互补约束的新颖更严格松弛及其在非线性和双层规划中的应用

• 批准号: 1234897
• 负责人: Mohit Tawarmalani
• 金额: $ 22.62万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1234897&HistoricalAwards=false
• 关键词: Collaborative; Research; Novel; Tighter; Relaxations

This collaborative research award provides funding for the development of new and stronger techniques for the solution of optimization problems with complementarity constraints to global optimality. Complementarity problems are pervasive in business, engineering, and economics, since complementarity conditions arise in optimality conditions for nonlinear programs and in models of equilibria. Algorithms for complementarity problems have until recently focused on feasibility problems by employing local optimization techniques. This project focuses on the development of convex relaxations for these problems, with the goal of incorporating them into branch-and-bound algorithms for global optimization. The research is aimed at deriving procedures that (i) exploit the combinatorial and disjunctive structure of complementarity constraints, (ii) focus on relaxations with a provable guarantee of strength, and (iii) target problems in which some of the constraints (besides complementarities) are nonlinear. The benefits of relaxation techniques will be studied relative to mature implementations of global optimization algorithms.If successful, the new relaxations developed with this research, along with factorable decomposition and separation techniques, will advance the state of the art in the global optimization of complementarity programs, bringing many practically relevant problems within the range of tractability. Because complementarity constraints arise in equilibrium analyses of supply and demand, adversarial relationships between strategically interacting entities, traffic equilibria, and in the analyses of multistage optimization problems, this research could lead to improved efficiencies in various sectors of the economy. Further, since bilevel programs have numerous applications in defense planning, including interdiction and protection of critical infrastructure, this research could impact positively various areas of national defense. From an educational perspective, related material will be incorporated into undergraduate and graduate education and doctoral students will be trained in relevant technologies including integer programming and global optimization. In addition, a website will be designed to disseminate prototype implementations and problem data sets.

该合作研究奖为开发新的、更强大的技术提供资金，以解决具有全局最优性互补约束的优化问题。互补性问题在商业、工程和经济学中普遍存在，因为互补性条件出现在非线性程序的最优性条件和平衡模型中。直到最近，互补性问题的算法还通过采用局部优化技术来关注可行性问题。该项目专注于开发这些问题的凸松弛，目标是将它们合并到分支定界算法中以实现全局优化。该研究旨在推导以下程序：(i) 利用互补性约束的组合和析取结构，(ii) 重点关注具有可证明强度保证的松弛，以及 (iii) 一些约束（除了互补性之外）是非线性的目标问题。将相对于全局优化算法的成熟实现来研究松弛技术的优点。如果成功，本研究开发的新松弛以及可因式分解和分离技术将推进互补程序全局优化的最新技术，在可处理性范围内带来许多实际相关的问题。由于供给和需求的均衡分析、战略互动实体之间的对抗关系、交通均衡以及多阶段优化问题的分析中会出现互补性约束，因此这项研究可以提高经济各个部门的效率。此外，由于双层计划在国防规划中有许多应用，包括拦截和保护关键基础设施，因此这项研究可能会对国防的各个领域产生积极影响。从教育角度来看，相关材料将纳入本科生和研究生教育，博士生将接受整数规划、全局优化等相关技术的培训。此外，还将设计一个网站来传播原型实现和问题数据集。

项目成果

On cutting planes for cardinality-constrained linear programs

关于基数约束线性规划的割平面

• DOI: 10.1007/s10107-018-1306-0
• 发表时间: 2018
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Kim, Jinhak;Tawarmalani, Mohit;Richard, Jean-Philippe P.
• 通讯作者: Richard, Jean-Philippe P.