Local Search for Integer Quadratic Programming

References

• Abbas A, Ambainis A, Augustino B, Bärtschi A, Buhrman H, Coffrin C, Cortiana G, et al. (2024) Challenges and opportunities in quantum optimization. Nature Rev. Phys. 6(12):718–735.Crossref, Google Scholar
• Abdi H (2010) Coefficient of variation. Salkind NJ, ed. Encyclopedia of Research Design (SAGE Publications, Thousand Oaks, CA), 170–171.Google Scholar
• Achterberg T (2009) SCIP: Solving constraint integer programs. Math. Programming Comput. 1(1):1–41.Crossref, Google Scholar
• Anstreicher KM (2003) Recent advances in the solution of quadratic assignment problems. Math. Programming 97(1–2):27–42.Crossref, Google Scholar
• Benoist T, Estellon B, Gardi F, Megel R, Nouioua K (2011) Localsolver 1.x: A black-box local-search solver for 0-1 programming. 4OR 9(3):299–316.Crossref, Google Scholar
• Berthold T (2013) Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6):611–614.Crossref, Google Scholar
• Berthold T (2014) RENS: The optimal rounding. Math. Programming Comput. 6(1):33–54.Crossref, Google Scholar
• Berthold T, Gleixner AM (2014) Undercover: A primal MINLP heuristic exploring a largest sub-MIP. Math. Programming 144(1–2):315–346.Crossref, Google Scholar
• Blekos K, Brand D, Ceschini A, Chou CH, Li RH, Pandya K, Summer A (2024) A review on quantum approximate optimization algorithm and its variants. Phys. Rep. 1068(1):1–66.Crossref, Google Scholar
• Bonami P, Gonçalves JP (2012) Heuristics for convex mixed integer nonlinear programs. Comput. Optim. Appl. 51(2):729–747.Crossref, Google Scholar
• Boros E, Hammer PL, Tavares G (2007) Local search heuristics for quadratic unconstrained binary optimization (QUBO). J. Heuristics 13(2):99–132.Crossref, Google Scholar
• Bussieck MR, Drud AS, Meeraus A (2003) MINLPLib—A collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1):114–119.Link, Google Scholar
• Byrd RH, Nocedal J, Waltz RA (2006) Knitro: An integrated package for nonlinear optimization. Di Pillo G, Roma M, eds. Large-Scale Nonlinear Optimization (Springer, Boston), 35–59.Crossref, Google Scholar
• Cai S (2015) Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. Yang Q, Wooldridge MJ, eds. Proc. Twenty-Fourth Internat. Joint Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 747–753.Google Scholar
• Coffrin C, Nagarajan H, Bent R (2019) Evaluating Ising processing units with integer programming. Rousseau LM, Stergiou K, eds. Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper. Res. CPAIOR 2019, Lecture Notes in Computer Science, vol. 11494 (Springer, Cham, Switzerland), 163–181.Google Scholar
• Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. Preprint, submitted November 14, https://arxiv.org/abs/1411.4028.Google Scholar
• Feo TA, Resende MG (1995) Greedy randomized adaptive search procedures. J. Global Optim. 6(2):109–133.Crossref, Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1):23–47.Crossref, Google Scholar
• Fischetti M, Glover F, Lodi A (2005) The feasibility pump. Math. Programming 104(1):91–104.Crossref, Google Scholar
• Frangioni A, Furini F, Gentile C (2016) Approximated perspective relaxations: A project and lift approach. Comput. Optim. Appl. 63(3):705–735.Crossref, Google Scholar
• Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, et al. (2019) QPLIB: A library of quadratic programming instances. Math. Programming Comput. 11(2):237–265.Crossref, Google Scholar
• Gertz EM, Wright SJ (2003) Object-oriented software for quadratic programming. ACM Trans. Math. Software 29(1):58–81.Crossref, Google Scholar
• Glover F (1989) Tabu search—Part I. ORSA J. Comput. 1(3):190–206.Link, Google Scholar
• Glover F, Lü Z, Hao JK (2010) Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR 8(3):239–253.Crossref, Google Scholar
• Glover F, Kochenberger G, Hennig R, Du Y (2022) Quantum bridge analytics I: A tutorial on formulating and using QUBO models. Ann. Oper. Res. 314(1):141–183.Crossref, Google Scholar
• Gould NI, Toint PL (2002) An iterative working-set method for large-scale nonconvex quadratic programming. Appl. Numer. Math. 43(1–2):109–128.Crossref, Google Scholar
• Gribling S, Sinjorgo L, Sotirov R (2025) Improved approximation ratios for the quantum max-cut problem on general, triangle-free and bipartite graphs. Preprint, submitted April 15, https://arxiv.org/abs/2504.11120.Google Scholar
• Gurobi Optimization LLC (2025) Gurobi optimizer reference manual. Accessed September 20, 2025, https://www.gurobi.com.Google Scholar
• He X, Lin P, Jiang T, Cai S (2026) Local search for integer quadratic programming. https://doi.org/10.1287/ijoc.2025.1178.cd, https://github.com/INFORMSJoC/2025.1178.Google Scholar
• Herrman R, Treffert L, Ostrowski J, Lotshaw PC, Humble TS, Siopsis G (2021) Impact of graph structures for QAOA on MaxCut. Quantum Inform. Processing 20(9):289.Crossref, Google Scholar
• Holliday JB, Blount D, Osaba E, Luu K (2025) Advanced quantum annealing approach to vehicle routing problems with time windows. Preprint, submitted March 31, https://arxiv.org/abs/2503.24285.Google Scholar
• Land AH, Doig AG (2009) An automatic method for solving discrete programming problems. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer, Berlin), 105–132.Google Scholar
• Liberti L, Mladenović N, Nannicini G (2011) A recipe for finding good solutions to MINLPs. Math. Programming Comput. 3(4):349–390.Crossref, Google Scholar
• Lobe E (2022) Combinatorial problems in programming quantum annealers. PhD thesis, Otto von Guericke Universität Magdeburg, Magdeburg, Germany.Google Scholar
• Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. Glover F, Kochenberger GA, eds. Handbook of Metaheuristics, International Series in Operations Research & Management Science, vol. 57 (Springer, Boston), 320–353.Crossref, Google Scholar
• Lü Z, Glover F, Hao JK (2010a) A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. 207(3):1254–1262.Crossref, Google Scholar
• Lü Z, Hao JK, Glover F (2010b) A study of memetic search with multi-parent combination for UBQP. Cowling P, Merz P, eds. Evolutionary Comput. Combin. Optim. EvoCOP 2010, Lecture Notes in Computer Science, vol. 6022 (Springer, Berlin), 154–165.Google Scholar
• Lucas A (2014) Ising formulations of many NP problems. Frontiers Phys. 2(1):5.Google Scholar
• Merz P, Freisleben B (2002) Greedy and local search heuristics for unconstrained binary quadratic programming. J. Heuristics 8(2):197–213.Crossref, Google Scholar
• Merz P, Katayama K (2004) Memetic algorithms for the unconstrained binary quadratic programming problem. Biosystems 78(1–3):99–118.Crossref, Google Scholar
• Mittelmann H (2023) Visualizations of Mittelmann benchmarks. Accessed September 20, 2025, https://mattmilten.github.io/mittelmann-plots/.Google Scholar
• Mladenović N, Hansen P (1997) Variable neighborhood search. Comput. Oper. Res. 24(11):1097–1100.Crossref, Google Scholar
• Nannicini G (2019) Performance of hybrid quantum-classical variational heuristics for combinatorial optimization. Phys. Rev. E 99(1):013304.Crossref, Google Scholar
• Nannicini G, Belotti P (2012) Rounding-based heuristics for nonconvex minlps. Math. Programming Comput. 4(1):1–31.Crossref, Google Scholar
• Nannicini G, Belotti P, Liberti L (2008) A local branching heuristic for minlps. Preprint, submitted December 11, https://arxiv.org/abs/0812.2188.Google Scholar
• Nickel S, Steinhardt C, Schlenker H, Burkart W (2022) Decision Optimization with IBM ILOG CPLEX Optimization Studio (Springer, Berlin).Crossref, Google Scholar
• Pardalos PM, Xue J (1994) The maximum clique problem. J. Global Optim. 4(3):301–328.Crossref, Google Scholar
• Parekh O, Thompson K (2022) An optimal product-state approximation for 2-local quantum hamiltonians with positive terms. Preprint, submitted June 16, https://arxiv.org/abs/2206.08342v1.Google Scholar
• Pérez Armas LF, Creemers S, Deleplanque S (2024) Solving the resource constrained project scheduling problem with quantum annealing. Sci. Rep. 14(1):16784.Crossref, Google Scholar
• Pia AD, Dey SS, Molinaro M (2017) Mixed-integer quadratic programming is in NP. Math. Programming 162(1–2):225–240.Crossref, Google Scholar
• Schaerf A (2002) Local search techniques for constrained portfolio selection problems. Comput. Econom. 20(3):177–190.Crossref, Google Scholar
• Selman B, Kautz HA, Cohen B (1993) Local search strategies for satisfiability testing. Johnson DS, Trick MA, eds. Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26 (American Mathematical Society, Providence, RI), 521–532.Google Scholar
• Shirai T, Togawa N (2024) Postprocessing variationally scheduled quantum algorithm for constrained combinatorial optimization problems. IEEE Trans. Quantum Engrg. 5(99):1–14.Google Scholar
• Wang Y, Lü Z, Glover F, Hao JK (2013) Probabilistic GRASP-Tabu search algorithms for the UBQP problem. Comput. Oper. Res. 40(12):3100–3107.Crossref, Google Scholar