Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction

References

• Balas E., Zemel E. An algorithm for large zero-one knapsack problems. Oper. Res. (1980) 28:1130–1154Link, Google Scholar
• Billionnet A., Calmels F. Linear programming for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. (1996) 92:310–325Crossref, Google Scholar
• Billionnet A., Faye A., Soutif E. A new upper-bound and an exact algorithm for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. (1999) 112:664–672Crossref, Google Scholar
• Caprara A., Pisinger D., Toth P. Exact solution of the quadratic knapsack problem. INFORMS J. Comput. (1999) 11:125–137Link, Google Scholar
• Chaillou P. P. Hansen, Mahieu Y., Simeone B. Best network flow bound for the quadratic knapsack problem. Combinatorial Optimization, Lecture Notes in Mathematics (1989) 1403(Springer Verlag, Heidelberg, Germany) 225–235Crossref, Google Scholar
• Cook W., Seymour P. Tour mergining via branch-decomposition. INFORMS J. Comput. (2003) 15:233–248Link, Google Scholar
• Erkut E. The discrete p-dispersion problem. Eur. J. Oper. Res. (1990) 46:48–60Crossref, Google Scholar
• Ferreira C. E., Martin A., de Souza C. C., Weismantel R., Wolsey L. A. Formulations and valid inequalities for node capacitated graph partitioning. Math. Programming (1996) 74:247–266Crossref, Google Scholar
• Gallo G., Hammer P. L., Simeone B. Quadratic knapsack problems. Math. Programming Stud. (1980) 12:132–149Crossref, Google Scholar
• Hammer P. L., Rader D. J. Efficient methods for solving quadratic 0-1 knapsack problems. INFOR (1997) 35:170–182Google Scholar
• Helmberg C., Rendl F., Weismantel R., Cunningham W. H., McCormick S. T., Queyranne M. Quadratic knapsack relaxations using cutting planes and semidefinite programming. Proc. Fifth IPCO Conf. (1996) 1084(Springer Verlag, Heidelberg, Germany) 175–189Crossref, Google Scholar
• Johnson E. L., Mehrotra A., Nemhauser G. L. Min-cut clustering. Math. Programming (1993) 62:133–152Crossref, Google Scholar
• Kellerer H., Pferschy U., Pisinger D.Knapsack Problems (2004) (Springer Verlag, Heidelberg, Germany) Crossref, Google Scholar
• Kincaid R. K. Good solutions to discrete noxious location problems via metaheuristics. Ann. Oper. Res. (1992) 40:265–281Crossref, Google Scholar
• Michelon P., Veilleux L. Lagrangean methods for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. (1996) 92:326–341Crossref, Google Scholar
• Park K., Lee K., Park S. An extended formulation approach to the edge-weighted maximal clique problem. Eur. J. Oper. Res. (1996) 95:671–682Crossref, Google Scholar
• Pisinger D. Upper bounds and exact algorithms for p-dispersion problems. Comput. Oper. Res. (2006) 33:1380–1398Crossref, Google Scholar
• Polzin T., Vahdati S., Möhring R. H., Raman R. Extending reduction techniques for the Steiner tree problem: A combination of alternative-and bound-based approaches. Algorithms—ESA 2002, Lecture Notes in Computer Science (2002) 2461(Springer Verlag, Heidelberg, Germany) 795–807Crossref, Google Scholar
• Rasmussen A. B., Sandvik R. Kvaliteten af grænsev ærdier for det kvadratiske knapsack problem. (2002) . Working Paper Project 02-09-7, (D. Pisinger, supervisor), DIKU, University of Copenhagen, Copenhagen, DenmarkGoogle Scholar
• Rhys J. A selection problem of shared fixed costs and network flows. Management Sci. (1970) 17:200–207Link, Google Scholar
• Thomadsen T., Larsen J. A hub location problem with fully interconnected backbone and access networks. Comput. Oper. Res. (2007) 34:2520–2531Crossref, Google Scholar
• Witzgall C. Mathematical methods of site selection for electronic message systems (EMS). (1975) . Technical Report, National Bureau of Standards, Gaithersburg, MDGoogle Scholar