An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating

References

• Billionnet A, Calmels F (1996) Linear programming for the 0–1 quadratic knapsack problem. Eur. J. Oper. Res. 92(2):310–325.Crossref, Google Scholar
• Billionnet A, Elloumi S (1995) An algorithm for finding the k-best allocations of a tree structured program. J. Parallel Distributed Comput. 26(2):225–232.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, 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
• Billionnet A, Soutif E (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
• Bretthauer KM, Shetty B (2002) The nonlinear knapsack problem—algorithms and applications. Eur. J. Oper. Res. 138(3):459–472.Crossref, Google Scholar
• Bretthauer KM, Shetty B, Syam S (1995) A branch and bound algorithm for integer quadratic knapsack problems. INFORMS J. Comput. 7(1):109–116.Link, Google Scholar
• Buchheim C, Traversi E (2013) Separable Non-convex Underestimators for Binary Quadratic Programming (Springer, Berlin, Heidelberg), 236–247.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
• Chen Y, Hao JK (2015) Iterated responsive threshold search for the quadratic multiple knapsack problem. Annual Oper. Res. 226(1):101–131.Crossref, Google Scholar
• Chen Y, Hao JK, Glover F (2016) An evolutionary path relinking approach for the quadratic multiple knapsack problem. Knowledge-Based Syst. 92(C):23–34.Crossref, Google Scholar
• Cordeau JF, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J. Comput. 18(4):433–443.Link, Google Scholar
• Cordeau JF, Gaudioso M, Laporte G, Moccia L (2007) The service allocation problem at the Gioia Tauro maritime terminal. Eur. J. Oper. Res. 176(2):1167–1184.Crossref, Google Scholar
• Dawande M, Kalagnanam J, Keskinocak P, Salman F, Ravi R (2000) Approximation algorithms for the multiple knapsack problem with assignment restrictions. J. Combin. Optim. 4(2):171–186.Crossref, Google Scholar
• Elhedhli S, Goffin JL (2005) Efficient production-distribution system design. Management Sci. 51(7):1151–1164.Link, Google Scholar
• Ferreira CE, Martin A, Weismantel R (1996) Solving multiple knapsack problems by cutting planes. SIAM J. Optim. 6(3):858–877.Crossref, Google Scholar
• Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26(1):173–182.Link, Google Scholar
• Fréville A, Hanafi S (2005) The multidimensional 0-1 knapsack problem—bounds and computational aspects. Annual Oper. Res. 139(1):195–227.Crossref, Google Scholar
• Gallo G, Hammer PL, Simeone B (1980) Quadratic Knapsack Problems (Springer, Berlin, Heidelberg), 132–149.Crossref, Google Scholar
• García-Martínez C, Glover F, Rodriguez FJ, Lozano M, Martí R (2014a) Strategic oscillation for the quadratic multiple knapsack problem. Comput. Optim. Appl. 58(1):161–185.Crossref, Google Scholar
• García-Martínez C, Rodriguez F, Lozano M (2014b) Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem. Eur. J. Oper. Res. 232(3):454–463.Crossref, Google Scholar
• Gerla M, Kleinrock L (1977) On the topological design of distributed computer networks. IEEE Trans. Comm. 25(1):48–60.Crossref, Google Scholar
• Gilmore P, Gomory R (1961) A linear programming approach to the cutting stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Glover F (1975) Improved linear integer programming formulations of nonlinear integer problems. Management Sci. 22(4):455–460.Link, Google Scholar
• Gunawan A, Ng KM, Poh K, Lau HC (2014) Hybrid metaheuristics for solving the quadratic assignment problem and the generalized quadratic assignment problem. 2014 IEEE Internat. Conf. Automation Sci. Engrg. (IEEE, New York), 119–124.Crossref, Google Scholar
• Gurobi Optimization I (2017) Gurobi optimizer reference manual. Accessed April 23, 2019, http://www.gurobi.com.Google Scholar
• Hahn PM, Kim B, Guignard M, Smith JM, Zhu Y (2008) An algorithm for the generalized quadratic assignment problem. Comput. Optim. Appl. 40(3):351–372.Crossref, Google Scholar
• Hiley A, Julstrom BA (2006) The quadratic multiple knapsack problem and three heuristic approaches to it. Proc. 8th Annual Conf. Genetic Evolutionary Comput. (ACM, New York), 547–552.Crossref, Google Scholar
• Hua Z, Huang F (2006) A variable-grouping based genetic algorithm for large-scale integer programming. Inform. Sci. 176(19):2869–2885.Crossref, Google Scholar
• Hung MS, Fisk JC (1978) An algorithm for 0-1 multiple-knapsack problems. Naval Res. Logist. Quart. 25(3):571–579.Crossref, Google Scholar
• IBM (2017) IBM ILOG CPLEX optimizer. Accessed April 23, 2019, https://www.ibm.com/analytics/cplex-optimizer.Google Scholar
• Julstrom BA (2005) Greedy, genetic, and greedy genetic algorithms for the quadratic knapsack problem. Proc. 7th Annual Conf. Genetic Evolutionary Comput. (ACM, New York), 607–614.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, New York).Crossref, Google Scholar
• Kim BJ (2006) Investigation of methods for solving new classes of quadratic assignment problems (QAPs). PhD thesis, University of Pennsylvania, Philadelphia.Google Scholar
• Koopmans T, Beckmann MJ (1955) Assignment Problems and the Location of Economic Activities, Cowles Foundation Discussion Papers, no. 4 (Yale University, New Haven, CT), https://EconPapers.repec.org/RePEc:cwl:cwldpp:4.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
• Krislock N, Malick J, Roupin F (2016) Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Comput. Oper. Res. 66:153–159.Crossref, Google Scholar
• Krislock N, Malick J, Roupin F (2017) Biqcrunch: A semidefinite branch-and-bound method for solving binary quadratic problems. ACM Trans. Math. Software 43(4):32:1–32:23.Crossref, Google Scholar
• Lawler EL (1963) The quadratic assignment problem. Management Sci. 9(4):586–599.Link, Google Scholar
• Lee CG, Ma Z (2004) The generalized quadratic assignment problem. Research report, Department of Mechanical and Industrial Engineering, University of Toronto, Toronto.Google Scholar
• Magirou V, Milis J (1989) An algorithm for the multiprocessor assignment problem. Oper. Res. Lett. 8(6):351–356.Crossref, Google Scholar
• Magirou VF (1992) An improved partial solution to the task assignment and multiway cut problems. Oper. Res. Lett. 12(1):3–10.Crossref, 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 140(1):99–124.Crossref, Google Scholar
• Martello S, Toth P (1981) Heuristic algorithms for the multiple knapsack problem. Computing 27(2):93–112.Crossref, Google Scholar
• Mateus GR, Resende MGC, Silva RMA (2011) Grasp with path-relinking for the generalized quadratic assignment problem. J. Heuristics 17(5):527–565.Crossref, Google Scholar
• Mathews GB (1896) On the partition of numbers. Proc. London Math. Soc. s1–28(1):486–490Crossref, Google Scholar
• Mathur K, Salkin HM, Morito S (1983) A branch and search algorithm for a class of nonlinear knapsack problems. Oper. Res. Lett. 2(4):155–160.Crossref, Google Scholar
• McKendall A, Li C (2017) A tabu search heuristic for a generalized quadratic assignment problem. J. Indust. Production Engrg. 34(3):221–231.Crossref, Google Scholar
• Michelon P, Maculan N (1993) Lagrangean methods for 0–1 quadratic problems. Discrete Appl. Math. 42(2):257–269.Crossref, Google Scholar
• Nakagawa Y, James RJW, Rego C, Edirisinghe C (2014) Entropy-based optimization of nonlinear separable discrete decision models. Management Sci. 60(3):695–707.Link, Google Scholar
• Pessoa AA, Hahn PM, Guignard M, Zhu Y (2010) Algorithms for the generalized quadratic assignment problem combining lagrangean decomposition and the reformulation-linearization technique. Eur. J. Oper. Res. 206(1):54–63.Crossref, Google Scholar
• Pisinger D (1999) An exact algorithm for large multiple knapsack problems. Eur. J. Oper. Res. 114(3):528–541.Crossref, Google Scholar
• Pisinger D (2007) The quadratic knapsack problem—a survey. Discrete Appl. Math. 155(5):623–648.Crossref, Google Scholar
• Pisinger D, Rasmussen AB, Sandvik R (2007) Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J. Comput. 19(2):280–290.Link, Google Scholar
• Pulikanti S, Singh A (2009) An Artificial Bee Colony Algorithm for the Quadratic Knapsack Problem (Springer, Berlin, Heidelberg), 196–205.Crossref, Google Scholar
• Qin J, Xu X, Wu Q, Cheng T (2016) Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem. Comput. Oper. Res. 66(February):199–214.Crossref, Google Scholar
• Rodrigues CD, Quadri D, Michelon P, Gueye S (2012) 0-1 quadratic knapsack problems: An exact approach based on a t-linearization. SIAM J. Optim. 22(4):1449–1468.Crossref, Google Scholar
• Ross GT, Soland RM (1975) A branch and bound algorithm for the generalized assignment problem. Math. Programming 8(1):91–103.Crossref, Google Scholar
• Roupin F (2004) From linear to semidefinite programming: An algorithm to obtain semidefinite relaxations for bivalent quadratic problems. J. Combin. Optim. 8(4):469–493.Crossref, Google Scholar
• Saraç T, Sipahioglu A (2014) Generalized quadratic multiple knapsack problem and two solution approaches. Comput. Oper. Res. 43(1):78–89.Crossref, Google Scholar
• Singh A, Baghel AS (2007) A new grouping genetic algorithm for the quadratic multiple knapsack problem. Cotta C, van Hemert J, eds. Evolutionary Comput. Combinatorial Optimization: Proc. 7th Eur. Conf. (Springer, Berlin, Heidelberg), 210–218.Crossref, Google Scholar
• Soak SM, Lee SW (2012) A memetic algorithm for the quadratic multiple container packing problem. Appl. Intelligence 36(1):119–135.Crossref, Google Scholar
• Sofianopoulou S (1992) The process allocation problem: A survey of the application of graph-theoretic and integer programming approaches. J. Oper. Res. Soc. 43(5):407–413.Crossref, Google Scholar
• Sundar S, Singh A (2010) A swarm intelligence approach to the quadratic multiple knapsack problem. Wong KW, Mendis BSU, Abdesselam B, eds. ICONIP: International Conf. Neural Inform. Processing: Theory Algorithms, Sydney, Australia, November 22–25. (Springer, Berlin, Heidelberg), 626–633.Crossref, Google Scholar
• Tlili T, Yahyaoui H, Krichen S (2016) An iterated variable neighborhood descent hyperheuristic for the quadratic multiple knapsack problem. Lee R, ed. Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, Studies in Computational Intelligence (Springer, New York), 245–251.Google Scholar
• Yang MJ, Xia Y, Zou HM (2016) On linearization techniques for budget-constrained binary quadratic programming problems. Oper. Res. Lett. 44(6):702–705.Crossref, Google Scholar