Local Search for Integer Quadratic Programming
Integer Quadratic Programming (IQP) is an important problem in operations research. Local search is a powerful method for solving hard problems, but the research on local search algorithms for IQP solving is still on its early stage. This paper develops an efficient local search solver for solving general IQP, called LS-IQCQP. We propose four new local search operators for IQP that can handle quadratic terms in the objective function, constraints or both. Furthermore, a two-mode local search algorithm is introduced, utilizing newly designed scoring functions to enhance the search process. Experiments are conducted on standard IQP benchmarks QPLIB and 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 outperforms other state-of-the-art solvers. Moreover, LS-IQCQP has established 6 new records for QPLIB and MINLPLIB open instances.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Overall Complexity Certification of a Standard Branch and Bound Method for Mixed-Integer Quadratic Programming
This paper presents a method to certify the computational complexity of a standard Branch and Bound method for solving Mixed-Integer Quadratic Programming (MIQP) problems defined as instances of a multi-parametric MIQP. …
Model Predictive ControlAutomatic Generation of Polynomial Symmetry Breaking Constraints
Symmetry in integer programming causes redundant search and is often handled with symmetry breaking constraints that remove as many equivalent solutions as possible. We propose an algebraic method which allows to generat…
SDP Relaxation with Randomized Rounding for Energy Disaggregation
We develop a scalable, computationally efficient method for the task of energy disaggregation for home appliance monitoring. In this problem the goal is to estimate the energy consumption of each appliance over time base…
Informative Path Planning in Random Fields via Mixed Integer Programming
We present a new mixed integer formulation for the discrete informative path planning problem in random fields. The objective is to compute a budget constrained path while collecting measurements whose linear estimate re…
Addressing Unboundedness in Quadratically-Constrained Mixed-Integer Problems
Mixed-integer (MI) quadratic models subject to quadratic constraints, known as All-Quadratic MI Programs, constitute a challenging class of NP-complete optimization problems. The particular scenario of unbounded integers…