SSS Algorithms for Max-Cut

References

• Alkhamis TM, Hasan M, Ahmed MA (1998) Simulated annealing for the unconstrained quadratic pseudo-Boolean function. Eur. J. Oper. Res. 108(3):641–652.Crossref, Google Scholar
• Barahona F, Ladányi L (2006) Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut. RAIRO Oper. Res. 40(1):53–73.Crossref, Google Scholar
• Barahona F, Grötschel M, Jünger M, Reinelt G (1988) An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3):493–513.Link, Google Scholar
• Beasley JE (1998) Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical report, Imperial College, London.Google Scholar
• Bodlaender HL, Koster AM (2008) Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3):255–269.Crossref, Google Scholar
• Bodlaender HL, Bonsma P, Lokshtanov D (2013) The fine details of fast dynamic programming over tree decompositions. Gutin G, Szeider S, eds. Parametrized Exact Comput. 8th Internat. Sympos., IPEC 2013, Lecture Notes in Computer Science, vol. 8246 (Springer, Cham, Switzerland), 41–53.Crossref, Google Scholar
• Boykov Y, Kolmogorov V (2004) An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Machine Intelligence 26(9):1124–1137.Crossref, Google Scholar
• Burer S, Monteiro RD, Zhang Y (2002) Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12(2):503–521.Crossref, Google Scholar
• Charfreitag J, Mallach S, Mutzel P (2023) Integer programming for the maximum cut problem: A refined model and implications for branching. Berry J, Shmoys D, Cowen L, Naumann U, eds. SIAM Conf. Appl. Comput. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 63–74.Crossref, Google Scholar
• Charfreitag J, Jünger M, Mallach S, Mutzel P (2022) McSparse: Exact solutions of sparse maximum cut and sparse unconstrained binary quadratic optimization problems. Phillips CA, Speckmann B, eds. 2022 Proc. Sympos. Algorithm Engrg. Experiments (SIAM, Philadelphia), 54–66.Crossref, Google Scholar
• De Simone C, Diehl M, Jünger M, Mutzel P, Reinelt G, Rinaldi G (1995) Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm. J. Statist. Phys. 80(1):487–496.Crossref, Google Scholar
• De Simone C, Diehl M, Jünger M, Mutzel P, Reinelt G, Rinaldi G (1996) Exact ground states of two-dimensional ±J Ising spin glasses. J. Statist. Phys. 84(5):1363–1371.Crossref, Google Scholar
• Deza MM, Laurent M (1997) Geometry of Cuts and Metrics, vol. 2 (Springer, Berlin).Crossref, Google Scholar
• Duarte A, Sánchez Á, Fernández F, Cabido R (2005) A low-level hybridization between memetic algorithm and VNS for the max-cut problem. Proc. Seventh Annual Conf. Genetic Evolutionary Comput. (ACM, New York), 999–1006.Google Scholar
• Dunning I, Gupta S, Silberholz J (2018) What works best when? A systematic evaluation of heuristics for max-cut and QUBO. INFORMS J. Comput. 30(3):608–624.Link, Google Scholar
• Fan C, Shen M, Nussinov Z, Liu Z, Sun Y, Liu YY (2023) Searching for spin glass ground states through deep reinforcement learning. Nature Comm. 14(1):725.Crossref, Google Scholar
• Festa P, Pardalos PM, Resende MG, Ribeiro CC (2002) Randomized heuristics for the max-cut problem. Optim. Methods Software 17(4):1033–1058.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
• Galluccio A, Loebl M, Vondrák J (2001) Optimization via enumeration: A new algorithm for the max cut problem. Math. Programming 90(2):273–290.Crossref, Google Scholar
• Gentile C, Rinaldi G, Salgado E (2024) SSS algorithms for max-cut. https://doi.org/10.1287/ijoc.2024.0812.cd, https://github.com/INFORMSJoC/2024.0812.Google Scholar
• Glover F, Kochenberger GA, Alidaee B (1998) Adaptive memory tabu search for binary quadratic programs. Management Sci. 44(3):336–345.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
• Grossman L (2014) The quantum quest for a revolutionary computer. Time (February 17), https://time.com/magazine/us/4789/february-17th-2014-vol-183-no-6-u-s/.Google Scholar
• Hamze F, de Freitas N (2004) From fields to trees. Proc. 20th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 243–250.Google Scholar
• Hasan M, Alkhamis T, Ali J (2000) A comparison between simulated annealing, genetic algorithm and tabu search methods for the unconstrained quadratic pseudo-Boolean function. Comput. Indust. Engrg. 38(4):323–340.Crossref, Google Scholar
• Imanaga T, Nakano K, Yasudo R, Ito Y, Kawamata Y, Katsuki R, Ozaki S, Yazane T, Hamano K (2021) Solving the sparse QUBO on multiple GPUs for simulating a quantum annealer. 2021 Ninth Internat. Sympos. Comput. Networking (IEEE, Piscataway, NJ), 19–28.Google Scholar
• Johnson D, Pataki G (2000) Workshop “seventh DIMACS implementation challenge: Semidefinite and related optimization problems.” Accessed January 2024, http://dimacs.rutgers.edu/archive/Challenges/Seventh.Google Scholar
• Johnson DS, Papadimitriou CH, Yannakakis M (1988) How easy is local search? J. Comput. System Sci. 37(1):79–100.Crossref, Google Scholar
• Jünger M, Lobe E, Mutzel P, Reinelt G, Rendl F, Rinaldi G, Stollenwerk T (2021) Quantum annealing versus digital computing: An experimental comparison. ACM J. Experiment. Algorithmics 26:1–30.Crossref, Google Scholar
• Katayama K, Narihisa H (2001) Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem. Eur. J. Oper. Res. 134(1):103–119.Crossref, Google Scholar
• Katayama K, Tani M, Narihisa H (2000) Solving large binary quadratic programming problems by effective genetic local search algorithm. Whitley LD, Goldberg DE, Cantú-Paz E, Spector L, Parmee IC, eds. GECCO’00: Proc. 2nd Annual Conf. Genetic Evolutionary Comput. (ACM) (Morgan Kaufmann Publishers Inc., San Francisco), 643–650.Google Scholar
• King AD, Raymond J, Lanting T, Isakov SV, Mohseni M, Poulin-Lamarre G, Ejtemaee S, et al. (2021) Scaling advantage over path-integral Monte Carlo in quantum simulation of geometrically frustrated magnets. Nature Comm. 12(1):1113.Crossref, Google Scholar
• Kolmogorov V (2009) Blossom V: A new implementation of a minimum cost perfect matching algorithm. Math. Programming Comput. 1(1):43–67.Crossref, Google Scholar
• Krislock N, Malick J, Roupin F (2014) Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Programming 143(1):61–86.Crossref, Google Scholar
• Laguna M, Duarte A, Martínez R (2009) Hybridizing the cross-entropy method: An application to the max-cut problem. Comput. Oper. Res. 36(2):487–498.Crossref, Google Scholar
• Liers F, Pardella G (2012) Partitioning planar graphs: A fast combinatorial approach for max-cut. Comput. Optim. Appl. 51(1):323–344.Crossref, Google Scholar
• Liers F, Jünger M, Reinelt G, Rinaldi G (2004) Computing exact ground states of hard Ising spin glass problems by branch-and-cut. Hartmann AK, Rieger H, eds. New Optimization Algorithms in Physics (John Wiley & Sons, Ltd., Chichester, UK), 47–69.Crossref, Google Scholar
• Lobe E, Lutz A (2024) Minor embedding in broken chimera and derived graphs is NP-complete. Theoret. Comput. Sci. 989:114369.Crossref, Google Scholar
• Lodi A, Allemand K, Liebling TM (1999) An evolutionary heuristic for quadratic 0–1 programming. Eur. J. Oper. Res. 119(3):662–670.Crossref, Google Scholar
• Lü Z, Glover F, Hao JK (2010) A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. 207(3):1254–1262.Crossref, Google Scholar
• Lukic J, Galluccio A, Marinari E, Martin OC, Rinaldi G (2004) Critical thermodynamics of the two-dimensional ±J Ising spin glass. Phys. Rev. Lett. 92(11):117202.Crossref, Google Scholar
• McCormick S, Rao M, Rinaldi G (2003) Easy and difficult objective functions for max cut. Math. Programming 94(2):459–466.Crossref, Google Scholar
• McGeoch CC, Wang C (2013) Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. CF ’13 Proc. ACM Internat. Conf. Comput. Frontiers (ACM, New York), 1–11.Google Scholar
• Merz P, Freisleben B (1999) Genetic algorithms for binary quadratic programming. Banzhaf W, Daida M, Eiben AE, Garzon MH, Honavar V, eds. GECCO’99: Proc. 1st Annual Conf. Genetic Evolutionary Comput., vol. 1 (ACM) (Morgan Kaufmann Publishers Inc., San Francisco), 417–424.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 (2024) Non-convex QUBO-QPLIB benchmark (10-9-2024). https://plato.asu.edu/ftp/qubo.html.Google Scholar
• MQLib (2020) Accessed January 2024, https://github.com/MQLib/MQLib.Google Scholar
• Nath RK, Thapliyal H, Humble TS (2021) A review of machine learning classification using quantum annealing for real-world applications. SN Comput. Sci. 2(5):365.Crossref, Google Scholar
• Nguyen VH, Minoux M (2021) Linear size MIP formulation of max-cut: New properties, links with cycle inequalities and computational results. Optim. Lett. 15(3):1041–1060.Crossref, Google Scholar
• Palubeckis G (2004) Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131(1):259–282.Crossref, Google Scholar
• Palubeckis G (2006) Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17(2):279–296.Crossref, Google Scholar
• Pardalos PM, Prokopyev OA, Shylo OV, Shylo VP (2008) Global equilibrium search applied to the unconstrained binary quadratic optimization problem. Optim. Methods Software 23(1):129–140.Crossref, Google Scholar
• Punnen AP, ed. (2022) The Quadratic Unconstrained Binary Optimization Problem—Theory, Algorithms, and Applications (Springer, Cham, Switzerland).Crossref, Google Scholar
• Rehfeldt D, Koch T, Shinano Y (2023) Faster exact solution of sparse maxcut and QUBO problems. Math. Programming Comput. 15(3):445–470.Crossref, Google Scholar
• Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming 121(2):307–335.Crossref, Google Scholar
• Rinaldi G (1995) Rudy: A rudimental graph generator. https://github.com/g-rinaldi/rudy.Google Scholar
• Schäffer AA (1991) Simple local search problems that are hard to solve. SIAM J. Comput. 20(1):56–87.Crossref, Google Scholar
• Selby A (2014a) Efficient subgraph-based sampling of Ising-type models with frustration. Preprint, submitted September 13, https://arxiv.org/abs/1409.3934.Google Scholar
• Selby A (2014b) QUBO-chimera. https://github.com/alex1770/QUBO-Chimera.Google Scholar
• Yarkoni S, Raponi E, Bäck T, Schmitt S (2022) Quantum annealing for industry applications: Introduction and review. Rep. Progress Phys. 85(10):104001.Crossref, Google Scholar