A Dual Bounding Framework Through Cost Splitting for Binary Quadratic Optimization

References

• Adams WP, Forrester RJ (2005) A simple recipe for concise mixed 0-1 linearizations. Oper. Res. Lett. 33(1):55–61.Crossref, Google Scholar
• Adams WP, Sherali HD (1990) Linearization strategies for a class of zero-one mixed integer programming problems. Oper. Res. 38(2):217–226.Link, Google Scholar
• Aloise D, Cafieri S, Caporossi G, Hansen P, Perron S, Liberti L (2010) Column generation algorithms for exact modularity maximization in networks. Phys. Rev. E 82(4):046112.Crossref, Google Scholar
• Amor HB, Desrosiers J, Frangioni A (2004) Stabilization in column generation. Les Cahiers du GERAD 711:2440.Google Scholar
• Assad A, Xu W (1992) The quadratic minimum spanning tree problem. Naval Res. Logist. 39(3):399–417.Crossref, Google Scholar
• Assari SM, Idrees H, Shah M (2016) Human re-identification in crowd videos using personal, social and environmental constraints. Leibe B, Matas J, Sebe N, Welling M, eds. Computer Vision–ECCV 2016. Lecture Notes in Computer Science, vol. 9906 (Springer, Cham, Switzerland), 119–136.Crossref, Google Scholar
• Barahona F (1983) The max-cut problem on graphs not contractible to K5. Oper. Res. Lett. 2(3):107–111.Crossref, Google Scholar
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, Google Scholar
• Bergner M, Caprara A, Ceselli A, Furini F, Lübbecke ME, Malaguti E, Traversi E (2015) Automatic Dantzig-Wolfe reformulation of mixed integer programs. Math. Programming 149(1–2):391–424.Crossref, Google Scholar
• Bettiol E, Bomze I, Létocart L, Rinaldi F, Traversi E (2022) Mining for diamonds—Matrix generation algorithms for binary quadratically constrained quadratic problems. Comput. Oper. Res. 142(C):105735.Crossref, Google Scholar
• Billionnet A, Elloumi S (2001) Best reduction of the quadratic semi-assignment problem. Discrete Appl. Math. 109(3):197–213.Crossref, Google Scholar
• Billionnet A, Soutif É (2004) An exact method based on Lagrangian decomposition for the 0–1 quadratic knapsack problem. Eur. J. Oper. Res. 157(3):565–575.Crossref, Google Scholar
• Billionnet A, Elloumi S, Plateau MC (2009) Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method. Discrete Appl. Math. 157(6):1185–1197.Crossref, Google Scholar
• Bonizzoni P, Della Vedova G, Dondi R, Jiang T (2008) On the approximation of correlation clustering and consensus clustering. J. Comput. System Sci. 74(5):671–696.Crossref, Google Scholar
• Booth M, Reinhardt SP, Roy A (2017) Partitioning optimization problems for hybrid classical/quantum execution. GitHub repository URL https://github.com/dwavesystems/qbsolv/blob/master/qbsolv_techReport.pdf.Google Scholar
• Çela E (2013) The Quadratic Assignment Problem: Theory and Algorithms, vol. 1 (Springer Science & Business Media, Berlin).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. 2022 Proc. Sympos. Algorithm Engrg. Experiments (ALENEX) (SIAM, Philadelphia), 54–66.Google Scholar
• Chen WA, Zhu Z, Kong N (2018) A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs. Optim. Lett. 12:155–169.Crossref, Google Scholar
• Chrétienne P (1989) A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. Eur. J. Oper. Res. 43(2):225–230.Crossref, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• De Fréminville PDLP, Desaulniers G, Rousseau LM, Perron S (2015) A column generation heuristic for districting the price of a financial product. J. Oper. Res. Soc. 66(6):965–978.Crossref, Google Scholar
• Dehghan A, Shah M (2017) Binary quadratic programing for online tracking of hundreds of people in extremely crowded scenes. IEEE Trans. Pattern Anal. Machine Intelligence 40(3):568–581.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation, vol. 5 (Springer Science & Business Media, Berlin).Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Drwal M (2014) Algorithm for quadratic semi-assignment problem with partition size coefficients. Optim. Lett. 8(3):1183–1190.Crossref, Google Scholar
• Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1):229–237.Crossref, Google Scholar
• Emami P, Pardalos PM, Elefteriadou L, Ranka S (2018) Machine learning methods for solving assignment problems in multi-target tracking. Preprint, submitted February 19, https://arxiv.org/abs/1802.06897.Google Scholar
• Escoffier B, Hammer PL (2007) Approximation of the quadratic set covering problem. Discrete Optim. 4(3–4):378–386.Crossref, Google Scholar
• Fischer A (2014) An analysis of the asymmetric quadratic traveling salesman polytope. SIAM J. Discrete Math. 28(1):240–276.Crossref, Google Scholar
• Fischer F, Jaeger G, Lau A, Molitor P (2009) Complexity and algorithms for the traveling salesman problem and the assignment problem of second order. Lecture Notes Comput. Sci. 5165:211–224.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
• Glover F, Woolsey E (1974) Converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res. 22(1):180–182.Link, Google Scholar
• Hahn PM, Zhu YR, Guignard M, Hightower WL, Saltzman MJ (2012) A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J. Comput. 24(2):202–209.Link, Google Scholar
• Hansen P, Lih KW (1992) Improved algorithms for partitioning problems in parallel, pipelined, and distributed computing. IEEE Trans. Comput. 41(6):769–771.Crossref, Google Scholar
• Helmberg C, Rendl F, Weismantel R (2000) A semidefinite programming approach to the Quadratic Knapsack Problem. J. Combin. Optim. 4(2):197–215.Crossref, Google Scholar
• Henschel R, Leal-Taixé L, Cremers D, Rosenhahn B (2018) Fusion of head and full-body detectors for multi-object tracking. Proc. IEEE Conf. Comput. Vision Pattern Recognition Workshops (IEEE, Piscataway, NJ), 1428–1437.Google Scholar
• Hu H, Sotirov R (2018) Special cases of the quadratic shortest path problem. J. Combin. Optim. 35(3):754–777.Crossref, Google Scholar
• Hu H, Sotirov R (2021) The linearization problem of a binary quadratic problem and its applications. Ann. Oper. Res. 307(1):229–249.Crossref, Google Scholar
• Jünger M, Mallach S (2021) Exact facetial odd-cycle separation for maximum cut and binary quadratic optimization. INFORMS J. Comput. 33(4):1419–1430.Abstract, Google Scholar
• Khaniyev T (2018) Data-driven structure detection in optimization: Decomposition, hub location, and brain connectivity. PhD thesis, University of Waterloo, Waterloo, ON.Google Scholar
• Khaniyev T, Elhedhli S, Erenay FS (2018) Structure detection in mixed-integer programs. INFORMS J. Comput. 30(3):570–587.Link, Google Scholar
• Khaniyev T, Elhedhli S, Erenay FS (2020) Spatial separability in hub location problems with an application to brain connectivity networks. INFORMS J. Optim. 2(4):320–346.Link, Google Scholar
• Kochenberger G, Hao JK, Glover F, Lewis M, Lü Z, Wang H, Wang Y (2014) The unconstrained binary quadratic programming problem: A survey. J. Combin. Optim. 28(1):58–81.Crossref, Google Scholar
• Leal-Taixe L, Pons-Moll G, Rosenhahn B (2012) Branch-and-price global optimization for multi-view multi-target tracking. 2012 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 1987–1994.Google Scholar
• Lemaréchal C, Oustry F (2001) SDP relaxations in combinatorial optimization from a Lagrangian viewpoint. Hadjisavvas N, Pardalos PM, eds. Advances in Convex Analysis and Global Optimization. Nonconvex Optimization and Its Applications, vol. 54 (Springer, Boston), 119–134.Crossref, Google Scholar
• Liberti L (2007) Compact linearization for binary quadratic problems. 4OR 5(3):231–245.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Magirou V, Milis J (1989) An algorithm for the multiprocessor assignment problem. Oper. Res. Lett. 8(6):351–356.Crossref, Google Scholar
• Mallach S (2018) Compact linearization for binary quadratic problems subject to assignment constraints. 4OR 16(3):295–309.Crossref, Google Scholar
• Mallach S (2023) Inductive linearization for binary quadratic programs with linear constraints: A computational study. 4OR, 1–41.Google Scholar
• Malucelli F (1996) A polynomially solvable class of quadratic semi-assignment problems. Eur. J. Oper. Res. 91(3):619–622.Crossref, Google Scholar
• Mauri GR, Lorena LAN (2011) Lagrangean decompositions for the unconstrained binary quadratic programming problem. Internat. Trans. Oper. Res. 18(2):257–270.Crossref, Google Scholar
• Mauri GR, Lorena LAN (2012) A column generation approach for the unconstrained binary quadratic programming problem. Eur. J. Oper. Res. 217(1):69–74.Crossref, Google Scholar
• Meier JF, Clausen U, Rostami B, Buchheim C (2016) A compact linearisation of Euclidean single allocation hub location problems. Electronic Notes Discrete Math. 52:37–44.Crossref, Google Scholar
• Milan A, Leal-Taixe L, Reid I, Roth S, Schindler K (2016) MOT16: A benchmark for multi-object tracking. Preprint, submitted March 2, https://arxiv.org/abs/1603.00831.Google Scholar
• O’Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32(3):393–404.Crossref, Google Scholar
• Pereira DL, da Cunha AS (2018) Polyhedral results, branch-and-cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem. Networks 71(1):31–50.Crossref, Google Scholar
• Pereira DL, da Cunha AS (2020) Dynamic intersection of multiple implicit Dantzig–Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem. Eur. J. Oper. Res. 284(2):413–426.Crossref, Google Scholar
• Pereira DL, Gendreau M, Salles da Cunha A (2013) Stronger lower bounds for the quadratic minimum spanning tree problem with adjacency costs. Electronic Notes Discrete Math. 41(5):229–236.Crossref, Google Scholar
• Pereira DL, Gendreau M, Salles da Cunha A (2015) Branch-and-cut and branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem. Networks 65(4):367–379.Crossref, Google Scholar
• Pisinger D (2007) The quadratic knapsack problem—A survey. Discrete Appl. Math. 155(5):623–648.Crossref, Google Scholar
• Punnen AP, Pandey P, Friesen M (2019) Representations of quadratic combinatorial optimization problems: A case study using quadratic set covering and quadratic knapsack problems. Comput. Oper. Res. 112:104769.Crossref, Google Scholar
• Punnen AP, Walter M, Woods BD (2017) A characterization of linearizable instances of the quadratic traveling salesman problem. Preprint, submitted August 23, https://arxiv.org/abs/1708.07217.Google Scholar
• Rostami B, Malucelli F (2015) Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation. Comput. Oper. Res. 64:178–188.Crossref, Google Scholar
• Rostami B, Errico F, Lodi A (2023) A convex reformulation and an outer approximation for a large class of binary quadratic programs. Oper. Res. 71(2):471–486.Link, Google Scholar
• Rostami B, Malucelli F, Belotti P, Gualandi S (2016) Lower bounding procedure for the asymmetric quadratic traveling salesman problem. Eur. J. Oper. Res. 253(3):584–592.Crossref, Google Scholar
• Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. Bampis E, ed. Proc. 14th Internat. Sympo. Experiment. Algorithms, SEA 2015 (Springer International Publishing, Cham, Switzerland), 379–390.Crossref, Google Scholar
• Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F, Goerigk M (2018) The quadratic shortest path problem: Complexity, approximability, and solution methods. Eur. J. Oper. Res. 268(2):473–485.Crossref, Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.Crossref, Google Scholar
• Sahni S, Gonzalez T (1976) P-complete approximation problems. J. ACM 23(3):555–565.Crossref, Google Scholar
• Saito H, Fujie T, Matsui T, Matuura S (2009) A study of the quadratic semi-assignment polytope. Discrete Optim. 6(1):37–50.Crossref, Google Scholar
• Schüle I, Ewe H, Küfer KH (2009) Finding tight RLT formulations for quadratic semi-assignment problems. Proc. 8th Cologne-Twente Workshop Graphs Combin. Optim. (Ecole Polytechnique and CNAM, Paris), 109–112.Google Scholar
• Shen H, Huang L, Huang C, Xu W (2018) Tracklet association tracker: An end-to-end learning-based association approach for multi-object tracking. Preprint, submitted August 5, https://arxiv.org/abs/1808.01562.Google Scholar
• Sherali HD, Adams WP (2013) A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Nonconvex Optimization and Its Applications, vol. 31 (Springer Science & Business Media, Berlin).Google Scholar
• Sherali HD, Smith JC (2007) An improved linearization strategy for zero-one quadratic programming problems. Optim. Lett. 1(1):33–47.Crossref, Google Scholar
• Silva A, Coelho LC, Darvish M (2021) Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search. Eur. J. Oper. Res. 292(3):1066–1084.Crossref, Google Scholar
• Stone HS (1977) Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Software Engrg. SE-3(1):85–93.Crossref, Google Scholar
• Tang S, Andriluka M, Andres B, Schiele B (2017) Multiple people tracking by lifted multicut and person re-identification. Proc. 30th IEEE Conf. Comput. Vision Pattern Recognition, CVPR 2017 (IEEE, Piscataway, NJ), 3539–3548.Google Scholar
• Wang S, Wolf S, Fowlkes CC, Yarkony J (2017) Tracking objects with higher order interactions via delayed column generation. Proc. 20th Internat. Conf. Artificial Intelligence Statist. (AISTATS 2017) (PMLR, New York), 1132–1140.Google Scholar
• Yarkony J, Adulyasak Y, Singh M, Desaulniers G (2020) Data association via set packing for computer vision applications. INFORMS J. Optim. 2(3):167–191.Link, Google Scholar