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

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.