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

在许多领域，如电信、物流和遗传学，决策者往往倾向于寻找解决方案，在这种方案中，只选择了潜在资源分配的一小部分。这样的解决方案更容易解释和实施，但可能很难识别。利用新的结构结果，调查人员开发了新的技术，以获得这些类型问题的高质量解决方案。该项目将把这些技术应用于数据分析和网络阻断问题。网络阻断模型已成功地用于识别电力和供水系统中的漏洞，并确保联网系统的安全。改进的方法将有助于创建更好的预测模型和收益工具，以增强国家安全。这项研究还将支持研究生和本科生的培训以及教学材料的创建。本项目旨在开发新的凸松弛技术，从而为基数约束数学规划(CCMP)带来更强的松弛界，并改善混合整数非线性规划的通用和定制分支定界代码的收敛。具体地说，研究人员将(I)通过最近发展的凸化过程的透镜来研究基数要求的双线性公式；(Ii)专注于先前为CCMP的线性松弛引入的析取松弛，它可以用于从任何不满足基数约束的单纯形基本解生成割集；(Iii)开发割平面策略，该策略可以通过重新公式线性化技术的扩展来生成凸壳描述；以及(Iv)利用置换不变性的概念来为在数据分析和各种逻辑命题的模型中产生的CCMP开发新的公式和松弛。该项目还将研究这些结果在非对称信息网络阻断的KKT公式中的应用。研究人员还将利用这些改进的松弛来开发用于稀疏主成分分析的启发式和精确解技术。

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.