Collaborative Research: Novel Relaxations for Cardinality-constrained Optimization Problems with Applications in Network Interdiction and Data Analysis

协作研究：基数约束优化问题的新颖松弛及其在网络拦截和数据分析中的应用

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

In many fields, such as telecommunication, logistics, and genetics, a decision-maker often prefers to find a solution, where only a fraction of potential resource assignments is selected. Such solutions are easier to interpret and implement, but they may be difficult to identify. Leveraging new structural results, the investigators develop new techniques to obtain high quality solutions to these types of problems. This project will apply these techniques to data analysis and network interdiction problems. Network interdiction models have been successfully used to identify vulnerabilities in power and water systems, and to secure networked systems. Improved methods will help create better predictive models and yield tools to enhance national security. This research will also support training of graduate and undergraduate students and creation of pedagogical material.This project seeks to develop new convex relaxation techniques that will lead to stronger relaxation bounds for cardinality constrained mathematical programs (CCMPs) and improve the convergence of generic and custom branch-and-bound codes for mixed integer nonlinear programs. Specifically, the researchers will (i) investigate bilinear formulations of cardinality requirements through the lens of the recently developed convexification procedures; (ii) focus on disjunctive relaxations previously introduced for linear relaxations of CCMPs, which can be used to generate cuts from any simplex basic solution that does not satisfy a cardinality constraint; (iii) develop cutting plane strategies that can generate convex hull descriptions devised from extensions of reformulation-linearization techniques; and (iv) utilize the concept of permutation-invariance to develop new formulations and relaxations for CCMPs arising in data analysis and models of various logical propositions. The project will also investigate the application of these results to the KKT formulation of network interdiction with asymmetric information. The investigators will also make use of these improved relaxations in the development of heuristic and exact solution techniques for sparse principal component analysis.

在许多领域，如电信，物流和遗传学，决策者往往更喜欢找到一个解决方案，其中只有一小部分潜在的资源分配被选中。这种解决方案更容易解释和实施，但可能难以识别。利用新的结构结果，研究人员开发新的技术，以获得高质量的解决方案，这些类型的问题。这个项目将把这些技术应用于数据分析和网络阻断问题。 网络阻断模型已成功地用于识别电力和水系统中的脆弱性，并确保网络系统的安全。改进的方法将有助于创建更好的预测模型，并产生加强国家安全的工具。该研究还将支持研究生和本科生的培训以及教学材料的创建。该项目旨在开发新的凸松弛技术，该技术将导致基数约束数学规划（CCMP）的更强松弛边界，并改善混合整数非线性规划的通用和自定义分支定界码的收敛性。具体而言，研究人员将（i）通过最近开发的凸化程序的透镜研究基数要求的双线性公式;（ii）专注于先前为CCMP的线性松弛引入的析取松弛，其可用于从任何不满足基数约束的单纯形基本解生成切割;（iii）开发切割平面策略，该切割平面策略能够生成从重构线性化技术的扩展设计的凸形船体描述;及（iv）利用排列的概念-不变性，为数据分析和各种逻辑命题的模型中出现的CCMP开发新的公式和松弛。该项目还将研究这些结果的应用，网络阻断与不对称信息的KKT制定。 研究人员还将利用这些改进的松弛的启发式和精确的解决方案技术稀疏主成分分析的发展。

项目成果

Tractable Relaxations of Composite Functions

复合函数的易于处理的松弛

• DOI: 10.1287/moor.2021.1162
• 发表时间: 2022
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: He, Taotao;Tawarmalani, Mohit
• 通讯作者: Tawarmalani, Mohit

Probability estimation via policy restrictions, convexification, and approximate sampling

通过政策限制、凸化和近似抽样进行概率估计

• DOI: 10.1007/s10107-022-01823-6
• 发表时间: 2022
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Chandra, Ashish;Tawarmalani, Mohit
• 通讯作者: Tawarmalani, Mohit

A new framework to relax composite functions in nonlinear programs

• DOI: 10.1007/s10107-020-01541-x
• 发表时间: 2020-07
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Taotao He;Mohit Tawarmalani

Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis

• DOI: 10.1287/moor.2021.1219
• 发表时间: 2021-12
• 期刊: Math. Oper. Res.
• 作者: Jinhak Kim;Mohit Tawarmalani;Jean-Philippe P. Richard

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.