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.