Faster exact solution of sparse maxcut and QUBO problems. (English) Zbl 1519.90211
Summary: The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems – by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
Software:
ParaSCIP; QPLIB; McSparse; BiqMac; MQLib; Biq Mac; BiqCrunch; SCIP; CPLEX; Gurobi; MADAM; BiqBin; CirCutReferences:
| [1] | Achterberg, T.: Constraint integer programming. In: Ph.D. Thesis, Technische Universität Berlin (2007) · Zbl 1430.90427 |
| [2] | Achterberg, T.; Bixby, RE; Gu, Z.; Rothberg, E.; Weninger, D., Presolve reductions in mixed integer programming, INFORMS J. Comput., 32, 2, 473-506 (2020) · Zbl 07290858 · doi:10.1287/ijoc.2018.0857 |
| [3] | Barahona, F.; Grötschel, M.; Jünger, M.; Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res., 36, 3, 493-513 (1988) · Zbl 0646.90084 · doi:10.1287/opre.36.3.493 |
| [4] | Barahona, F.; Jünger, M.; Reinelt, G., Experiments in quadratic 0-1 programming, Math. Program., 44, 1-3, 127-137 (1989) · Zbl 0677.90046 · doi:10.1007/BF01587084 |
| [5] | Barahona, F.; Mahjoub, AR, On the cut polytope, Math. Program., 36, 2, 157-173 (1986) · Zbl 0616.90058 · doi:10.1007/BF02592023 |
| [6] | Beasley, J.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Tech. Rep. (1998) |
| [7] | Bestuzheva, K., Besançon, M., Chen, W.K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S.J., Matter, F., Mühmer, E., Müller, B., Pfetsch, M.E., Rehfeldt, D., Schlein, S., Schlösser, F., Serrano, F., Shinano, Y., Sofranac, B., Turner, M., Vigerske, S., Wegscheider, F., Wellner, P., Weninger, D., Witzig, J.: The SCIP Optimization Suite 8.0. ZIB-Report 21-41, Zuse Institute Berlin (2021). http://nbn-resolving.de/urn:nbn:de:0297-zib-85309 |
| [8] | Billionnet, A.; Elloumi, S., Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem, Math. Program., 109, 1, 55-68 (2007) · Zbl 1278.90263 · doi:10.1007/s10107-005-0637-9 |
| [9] | Bonato, T.; Jünger, M.; Reinelt, G.; Rinaldi, G., Lifting and separation procedures for the cut polytope, Math. Program., 146, 1-2, 351-378 (2014) · Zbl 1297.90133 · doi:10.1007/s10107-013-0688-2 |
| [10] | Boros, E., Hammer, P.L., Tavares, G.: Preprocessing of unconstrained quadratic binary optimization. Tech. Rep. (2006) |
| [11] | Burer, S.; Monteiro, RDC; Zhang, Y., Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs, SIAM J. Optim., 12, 2, 503-521 (2002) · Zbl 1152.90532 · doi:10.1137/S1052623400382467 |
| [12] | Charfreitag, J., Jünger, M., Mallach, S., Mutzel, P.: McSparse: Exact solutions of sparse maximum cut and sparse unconstrained binary quadratic optimization problems. In: Phillips, C.A., Speckmann, B. eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 2022), online first (2022) |
| [13] | Dunning, I.; Gupta, S.; Silberholz, J., What works best when? A systematic evaluation of heuristics for max-cut and QUBO, INFORMS J. Comput., 30, 3, 608-624 (2018) · Zbl 1528.90288 · doi:10.1287/ijoc.2017.0798 |
| [14] | Ferizovic, D., Hespe, D., Lamm, S., Mnich, M., Schulz, C., Strash, D.: Engineering Kernelization for Maximum Cut. In: Blelloch, G.E., Finocchi, I. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, January 5-6, 2020, pp. 27-41. SIAM (2020). doi:10.1137/1.9781611976007.3 · Zbl 07302418 |
| [15] | Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, AM; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, HD; Sahinidis, NV; Vigerske, S.; Wiegele, A., QPLIB: a library of quadratic programming instances, Math. Program. Comput., 11, 2, 237-265 (2019) · Zbl 1435.90099 · doi:10.1007/s12532-018-0147-4 |
| [16] | Gamrath, G.: Enhanced predictions and structure exploitation in branch-and-bound. Technische Universitaet Berlin (Germany) (2020) |
| [17] | Glover, F.; Kochenberger, GA; Alidaee, B., Adaptive memory tabu search for binary quadratic programs, Manag. Sci., 44, 3, 336-345 (1998) · Zbl 0989.90072 · doi:10.1287/mnsc.44.3.336 |
| [18] | Glover, FW; Lewis, MW; Kochenberger, GA, Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems, Eur. J. Oper. Res., 265, 3, 829-842 (2018) · Zbl 1374.90294 · doi:10.1016/j.ejor.2017.08.025 |
| [19] | Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2021). https://www.gurobi.com |
| [20] | Gusmeroli, N.; Hrga, T.; Lužar, B.; Povh, J.; Siebenhofer, M.; Wiegele, A., Biqbin: A parallel branch-and-bound solver for binary quadratic problems with linear constraints, ACM Trans. Math. Softw. (2022) · Zbl 07666973 · doi:10.1145/3514039 |
| [21] | Hammer, PL; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. Program., 28, 2, 121-155 (1984) · Zbl 0574.90066 · doi:10.1007/BF02612354 |
| [22] | Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer (1968) · Zbl 0155.28001 |
| [23] | Hrga, T.; Povh, J., MADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM, Comput. Optim. Appl., 80, 2, 347-375 (2021) · Zbl 1478.90079 · doi:10.1007/s10589-021-00310-6 |
| [24] | IBM: CPLEX (2020). https://www.ibm.com/analytics/cplex-optimizer |
| [25] | Jünger, M.; Lobe, E.; Mutzel, P.; Reinelt, G.; Rendl, F.; Rinaldi, G.; Stollenwerk, T., Quantum annealing versus digital computing: an experimental comparison, ACM J. Exp. Algorithmics (2021) · Zbl 1499.68123 · doi:10.1145/3459606 |
| [26] | Jünger, M., Mallach, S.: Odd-cycle separation for maximum cut and binary quadratic optimization. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, LIPIcs, vol. 144, pp. 63:1-63:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). doi:10.4230/LIPIcs.ESA.2019.63 · Zbl 07525500 |
| [27] | Jünger, M.; Mallach, S., Exact facetial odd-cycle separation for maximum cut and binary quadratic optimization, INFORMS J. Comput., 33, 4, 1419-1430 (2021) · Zbl 07549342 · doi:10.1287/ijoc.2020.1008 |
| [28] | Karp, R.: Reducibility among combinatorial problems. In: R. Miller, J. Thatcher (eds.) Complexity of Computer Computations, pp. 85-103. Plenum Press (1972). doi:10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [29] | Kepner, J.; Gilbert, J., Graph algorithms in the language of linear algebra, SIAM (2011) · Zbl 1221.05010 · doi:10.1137/1.9780898719918 |
| [30] | Kernighan, BW; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49, 2, 291-307 (1970) · Zbl 0333.05001 · doi:10.1002/j.1538-7305.1970.tb01770.x |
| [31] | Krislock, N.; Malick, J.; Roupin, F., Biqcrunch: a semidefinite branch-and-bound method for solving binary quadratic problems, ACM Trans. Math. Softw. (2017) · Zbl 1380.90284 · doi:10.1145/3005345 |
| [32] | Lange, J., Andres, B., Swoboda, P.: Combinatorial Persistency Criteria for Multicut and Max-Cut. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp. 6093-6102. Computer Vision Foundation / IEEE (2019). doi:10.1109/CVPR.2019.00625 |
| [33] | Liers, F.: Contributions to determining exact ground-states of ising spin-glasses and to their physics. In: Ph.D. Thesis, University of Cologne (2004) |
| [34] | Lin, J., Cai, S., Luo, C., Su, K.: A reduction based method for coloring very large graphs. In: Sierra, C. (ed.) Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 517-523. ijcai.org (2017). doi:10.24963/ijcai.2017/73 |
| [35] | Ralphs, T.; Shinano, Y.; Berthold, T.; Koch, T., Parallel Solvers for Mixed Integer Linear Optimization, 283-336 (2018), Cham: Springer International Publishing, Cham · doi:10.1007/978-3-319-63516-3_8 |
| [36] | Rehfeldt, D., Koch, T.: Implications, Conflicts, and Reductions for Steiner Trees. In: Singh, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19-21, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12707, pp. 473-487. Springer (2021). doi:10.1007/978-3-030-73879-2_33 · Zbl 1483.90144 |
| [37] | Rendl, F.; Rinaldi, G.; Wiegele, A., Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Program., 121, 2, 307-335 (2010) · Zbl 1184.90118 · doi:10.1007/s10107-008-0235-8 |
| [38] | Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving open MIP instances with parascip on supercomputers using up to 80, 000 cores. In: 2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016, Chicago, IL, USA, May 23-27, 2016, pp. 770-779. IEEE Computer Society (2016). doi:10.1109/IPDPS.2016.56 |
| [39] | Tavares, G.: New algorithms for quadratic unconstrained binary optimization (qubo) with applications in engineering and social sciences. In: Ph.D. Thesis, Rutgers, the State University of New Jersey-New Brunswick (2008) |
| [40] | Wiegele, A.: BiqMac Library: A collection of Max-Cut and quadratic 0-1 programming instances of medium size. Tech. Rep. (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
