Fast Presolving Framework For Sparsity Constrained Convex Quadratic Programming: Screening-Based Cut Generation and Selection

Screening is widely utilized for Mixed-Integer Programming (MIP) presolving. It aims to certify a priori whether one or multiple specific binary variables can be fixed to optimal values based on solutions from convex relaxations. This paper studies the challenge of solving Sparsity-constrained (strongly) Convex Quadratic Programming (SCQP) and proposes the Screening-based Cut Presolving Framework (SCPF). SCPF contains two parts: a Screening-based Cut Generation (SCG) rule and a Screening-based Cut Selection (SCS) method. We show that the SCG provides superior screening ability compared to existing screening methods, and achieves a finer balance between screening effectiveness and computational overhead. We then provide theoretical guarantees for the SCS method to ensure the selection of generated cuts with high screening ability. Extensive numerical experiments validate the theoretical findings and demonstrate that the proposed framework significantly outperforms state-of-the-art screening methods. Notably, our SCPF achieves a 1.7X to 3.0X acceleration in total running time, especially in challenging phases, across high-dimensional synthetic datasets, complex real-world instances, and simulation libraries from sparse identification of nonlinear dynamics.

Article

Download

View PDF