Quadratic Combinatorial Optimization Using Separable Underestimators

References

• Adams WP, Johnson TA (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. Pardalos PM, Wolkowicz H, eds. Quadratic Assignment and Related Problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 16 (American Mathematical Society, Providence, RI), 43–75.Crossref, Google Scholar
• Aggarwal A, Coppersmith D, Khanna S, Motwani R, Schieber B (1999) The angular-metric traveling salesman problem. SIAM J. Comput. 29(3):697–711.Crossref, Google Scholar
• Amaldi E, Galbiati G, Maffioli F (2011) On minimum reload cost paths, tours, and flows. Networks 57(3):254–260.Crossref, Google Scholar
• Anstreicher KM, Brixius NW, Goux JP, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math. Programming 91(3):563–588.Crossref, Google Scholar
• Assad A, Xu W (1992) The quadratic minimum spanning tree problem. Naval Res. Logist. 39(3):399–417.Crossref, Google Scholar
• Billionnet A, Soutif E (2004a) 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, Soutif E (2004b) Using a mixed integer programming tool for solving the 0–1 quadratic knapsack problem. INFORMS J. Comput. 16(2):188–197.Link, Google Scholar
• Billionnet A, Elloumi S, Plateau M-C (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
• Bonami P, Biegler LT, Conn AR, Cornuéjols G, Grossmann IE, Laird CD, Lee Jet al. (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim. 5(2):186–204.Crossref, Google Scholar
• Buchheim C, Traversi E (2013) Separable non-convex underestimators for binary quadratic programming. Bonifaci V, Demetrescu C, Marchetti-Spaccamela A, eds. Proc. 12th Internat. Sympos. Experiment. Algorithms—SEA 2013. Lecture Notes in Computer Science, Vol. 7933 (Springer, Berlin), 236–247.Google Scholar
• Buchheim C, Trieu L (2013) Quadratic outer approximation for convex integer programming. Bonifaci V, Demetrescu C, Marchetti-Spaccamela A, eds. Proc. 12th Internat. Sympos. Experiment. Algorithms—SEA 2013. Lecture Notes in Computer Science, Vol. 7933 (Springer, Berlin), 224–235.Google Scholar
• Buchheim C, Caprara A, Lodi A (2012) An effective branch-and-bound algorithm for convex quadratic integer programming. Math. Programming (Ser. A) 135(1–2):369–395.Crossref, Google Scholar
• Buchheim C, Wiegele A, Zheng L (2010) Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput. 22(1):168–177.Link, Google Scholar
• Buchheim C, De Santis M, Palagi L, Piacentini M (2013) An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations. SIAM J. Optim. 23(3):1867–1889.Crossref, Google Scholar
• Burkard RE, Karisch SE, Rendl F (1997) QAPLIB—A quadratic assignment problem library. J. Global Optim. 10(4):391–403.Crossref, Google Scholar
• Caprara A (2008) Constrained 0–1 quadratic programming: Basic approaches and extensions. Eur. J. Oper. Res. 187(3):1494–1503.Crossref, Google Scholar
• Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11(2):125–137.Link, Google Scholar
• CPLEX (2015) IBM ILOG CPLEX Optimizer 12.6. www.ibm.com/software/integration/optimization/cplex-optimizer.Google Scholar
• de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.Crossref, Google Scholar
• de Klerk E, Sotirov R, Truetsch U (2015) A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives. INFORMS J. Comput. 27(2):378–391.Link, Google Scholar
• Dong H (2016) Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM J. Optim. 26(3):1962–1985.Crossref, Google Scholar
• Gamvros I, Gouveia L, Raghavan S (2012) Reload cost trees and network design. Networks 59(4):365–379.Crossref, Google Scholar
• Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. J. Soc. Indust. Appl. Math. 10(2):305–313.Crossref, Google Scholar
• Gourvès L, Lyra A, Martinhon C, Monnot J (2010) The minimum reload s–t path, trail and walk problems. Discrete Appl. Math. 158(13):1404–1417.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
• Hu H, Sotirov R (2016) Special cases of the quadratic shortest path problem. Technical report, https://arxiv.org/abs/1611.07682.Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Kruskal JB Jr (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7(1):48–50.Crossref, Google Scholar
• Lawler EL (1963) The quadratic assignment problem. Management Sci. 9(4):586–599.Link, Google Scholar
• Malick J, Roupin F (2013) On the bridge between combinatorial optimization and nonlinear optimization: A family of semidefinite bounds for 0–1 quadratic problems leading to quasi-Newton methods. Math. Programming B 140(1):99–124.Crossref, Google Scholar
• Palagi L, Piccialli V, Rendl F, Rinaldi G, Wiegele A (2012) Computational approaches to max-cut. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research and Management Science (Springer, New York), 821–849.Crossref, Google Scholar
• Pisinger D (2007) The quadratic knapsack problem—A survey. Discrete Appl. Math. 155(5):623–648.Crossref, Google Scholar
• Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. Bampis E, ed. Proc. 14th Internat. Sympos. Experiment. Algorithms—SEA 2015. Lecture Notes in Computer Science, Vol. 9125 (Springer, New York), 379–390.Crossref, Google Scholar
• Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2(1):71–109.Crossref, Google Scholar