Local Search for Integer Quadratic Programming

Integer quadratic programming (IQP) is an important problem in operations research. Local search is a powerful primal heuristic method for solving hard problems, but the research on local search algorithms for solving IQP is still in its early stages. This paper introduces an efficient local search algorithm called LS-IQCQP, which stands for “local search for integer quadratically constrained quadratic programming.” The algorithm is designed for solving general IQP, and it is capable of handling cases where quadratic terms appear in the objective function, constraints, or both. We propose four newly designed operators: the root operator for feasibility and three operators—inequality exploration, equality balance, and unconstrained free operator—for optimizing the objective function. To evaluate the quality of these operations, a weighted scoring function is introduced. Based on the scoring function, LS-IQCQP iteratively applies effective operations and employs a WalkSAT-like approach (a classic local search algorithm for satisfiability problems) by randomly selecting an operation to escape local optima. Experiments are conducted on standard IQP benchmarks from the Quadratic Programming Library (QPLIB) and Mixed-Integer Nonlinear Programming Library (MINLPLIB), comparing LS-IQCQP with several state-of-the-art IQP solvers. Experimental results demonstrate that LS-IQCQP is competitive with the most powerful commercial solver Gurobi and other state-of-the-art solvers in terms of finding a good feasible solution quickly. Moreover, LS-IQCQP has established six new records for QPLIB and MINLPLIB open instances by finding the new best-known solutions.

History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms.

Funding: This research was supported by the National Key Research and Development Program of China [Grant 2023YFA1009500].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1178) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1178). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.