Exact Solution of the Quadratic Knapsack Problem

References

• Adams W.P., Sherali H.D. A tight linearization and an algorithm for zero-one quadratic programming problems. Management Sci. (1986) 32:1274–1290Link, Google Scholar
• Balas E., Ceria S., Cornuéjols G. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming (1993) 58:295–324Crossref, Google Scholar
• Balas E., Ceria S., Cornuéjols G., Pataki G., Johnson D.S., Trick M.A. Polyhedral methods for the maximum clique problem. Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge (1996) (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Press)11–28Crossref, Google Scholar
• Balas E., Zemel E. An algorithm for large zero-one Knapsack problems. Oper. Res. (1980) 28:1130–1154Link, Google Scholar
• Bellare M., Goldreich O., Sudan M. Free bits, PCPs and non-approximability—Towards tight results. (1995) Proc. 36th Annual IEEE Sympos. Foundations Comput. Sci.(IEEE Computer Society Press)422–431Crossref, 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, presented at. 15th Internat. Sympos. Math. Programming (1997) (Lausanne, EPFL)24–29AugustGoogle Scholar
• Bretthauer K.M., Shetty B., Syam S. A branch-and-bound algorithm for integer quadratic Knapsack problems. ORSA J. Comput. (1995) 7:109–116Link, Google Scholar
• Chaillou P., Hansen P., Mahieu Y. Best network flow bounds for the quadratic knapsack problem. Lecture Notes in Mathematics 1403 (1986) (Springer-Verlag, Berlin) 226–235Google Scholar
• Carraresi P., Malucelli F., Pardalos P.M., Wolkowicz H. A reformulation scheme and new lower bounds for the QAP. Quadratic Assignment and Related Problems (1994) (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Press)147–160Crossref, Google Scholar
• Dijkhuizen G., Faigle U. A cutting-plane approach to the edge-weighted maximal clique problem. Eur. J. Oper. Res. (1993) 69:121–130Crossref, Google Scholar
• Fisher M.L. The Lagrangian relaxation method for solving integer programming problems. Management Sci. (1981) 27:1–18Link, Google Scholar
• Gallo G., Hammer P.L., Simeone B. Quadratic Knapsack problems. Math. Programming (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
• Held M., Karp R.M. The traveling salesman problem and minimum spanning trees: Part II. Math. Programming (1971) 1:6–25Crossref, Google Scholar
• Held M., Wolfe P., Crowder H.P. Validation of subgradient optimization. Math. Programming (1974) 6:62–88Crossref, Google 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. 5th MPS Conf. Integer Programming Combin. Optim. (1996) (Springer Verlag, Berlin) 175–189Lecture Notes in Computer Science 1084Crossref, Google Scholar
• Johnson E.L., Mehrotra A., Nemhauser G.L. Min-cut clustering. Math. Programming (1993) 62:133–152Crossref, Google Scholar
• Johnson D.S., Trick M.A.Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge (1996) (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS Press)Crossref, Google Scholar
• Lovász L., Schrijver A. Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. (1991) 1:166–190Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (J. Wiley & Sons, Chichester, UK) Google Scholar
• Martello S., Pisinger D., Toth P. Dynamic programming and tight bounds for the 0-1 Knapsack problem. (1997) . DIKU Report 97/11, University of Copenhagen, to appear in Management Sci.Google Scholar
• Michelon P., Maculan N. Lagrangean methods for 0-1 quadratic programming. Discrete Appl. Math. (1993) 42:257–269Crossref, 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
• Rhys J. A selection problem of shared fixed costs and network flows. Management Sci. (1970) 17:200–207Link, Google Scholar
• Witzgall C. Mathematical methods of ite selection for electronic message systems (EMS). (1975) . NBS Internal ReportGoogle Scholar