A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs

1. Al-Khayyal, F.A.: Generalized bilinear programming, part I: Models, applications, and linear programming relaxation. European Journal on Operations Research 60, 306–314 (1992)

   Article  MATH  Google Scholar 

2. Al-Khayyal, F.A., Falk., J.E.: Jointly constrained biconvex programming. Mathematics of Operations Research 8, 273–286 (1983)

   Article  MATH  MathSciNet  Google Scholar 

3. Al-Khayyal, F.A., Larsen, C., Van Voorhis., T.: A relaxation method for nonconvex quadratically constrained programs. Journal of Global Optimization 6, 215–230 (1995)

   Article  MATH  MathSciNet  Google Scholar 

4. Androulakis, I.P., Maranas, C.D., Floudas., C.A.: aBB : A global optimization method for general constrained nonconvex problems. Journal of Global Optimization 7, 337–363 (1995)

   Article  MathSciNet  MATH  Google Scholar 

5. Audet, C., Hansen, P., Jaumard, B., Savard., G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programs. Mathematical Programming 87, 131–152 (2000)

   MATH  MathSciNet  Google Scholar 

6. Ben-Tal, A., Nemirovski., A.: On polyhedral approximations of the second-order cone. Mathematics of Operations Research 26, 193–205 (2001)

   Article  MATH  MathSciNet  Google Scholar 

7. The COCONUT benchmark: A benchmark for global optimization and constraint satisfaction, 2004. http://www.mat.univie.ac.at{/∼n}eum/glopt/coconut/benchmark.html.

8. COIN-OR: Computational Infrastructure for Operations Research, 2004. http://www.coin-or.org.

9. Conn, A.R., Gould, N.I.M., Toint. Ph.L.: LANCELOT: A Fortran Package for Large-scale Nonlinear Optimization (Release A). Springer–Verlag, 1992

10. Dolan, E., Moré., J.: Benchmarking optimization software with performance profiles. Mathematical Programming 91, 201–213 (2002)

    Article  MATH  MathSciNet  Google Scholar 

11. Foster, I., Kesselman, C.: Computational grids. In: I. Foster, C. Kesselman (eds.), The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, 1999, Chapter 2.

12. Globallib, 2004. http://www.gamsworld.org/global/globallib.htm.

13. Goux, J.-P., Kulkarni, S., Linderoth, J.T., Yoder., M.: Master-Worker : An enabling framework for master-worker applications on the computational grid. Cluster Computing 4, 63–70 (2001)

    Article  Google Scholar 

14. Van Hentenryck, P., Michel, L., Deville, Y.: Numerica. A Modeling Language for Global Optimization. MIT Press, Cambridge, MA, 1997

15. Horst., R.: An algorithm for nonconvex programming problems. Mathematical Programming 10, 312–321 (1976)

    Article  MathSciNet  Google Scholar 

16. Horst, R., Tuy, H.: Global Optimization. Springer-Verlag, New York, 1993

17. Jansson., C.: Rigorous lower and upper bounds in linear programming. SIAM Journal on Optimization 14, 914–935 (2004)

    Article  Google Scholar 

18. Kearfott, R.B.: Rigorous Global Search: Continuous Problems. Kluwer, Dordrecht, 1996

19. Kim, S., Kojima., M.: Second order cone programming relaxation methods of nonconvex quadratic optimization problems. Optimization Methods and Software 15, 201–224 (2001)

    MATH  MathSciNet  Google Scholar 

20. Lebbeh, Y., Rueher, M., Michel, C.: A global filtering algorithm for handling systes of quadratic equations and inequations. In: P. van Hentenryck (ed.), Lecture Notes in Computer Science: Principles and Practice of Constraint Programming: CP 2002, vol. 2470, Springer, 2002, pp. 109–123

21. Linderoth, J.T.: Applying integer programming techniques to global optimization problems, 2003. Presentation at INFORMS National Meeting.

22. McCormick., G.P.: Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Mathematical Programming 10, 147–175 (1976)

    Article  MathSciNet  Google Scholar 

23. Mosek ApS, 2004. http://www.mosek.com.

24. Raber., U.: A simplicial branch-and-bound method for solving nonconvex all-quadratic programs. Journal of Global Optimization 13, 417–432 (1998)

    Article  Google Scholar 

25. Raber, U.: Nonconvex All-Quadratic Global Optimization Problems: Solution Methods, Application and Related Topics. PhD thesis, Universität Trier, Germany, 1999

26. Rote., G.: The convergence of the sandwich algorithm for approximating convex functions. Computing 48, 337–361 (1992)

    MathSciNet  Google Scholar 

27. Ryoo, H.S., Sahinidis., N.V.: A branch-and-reduce approach to global optimization. Journal of Global Optimization 8, 107–139 (1996)

    Article  MATH  MathSciNet  Google Scholar 

28. Sahinidis., N.V.: BARON: A general purpose global optimization software package. Journal of Global Optimization 8, 201–205 (1996)

    Article  Google Scholar 

29. Sherali, H.D., Alameddine., A.R.: An explicit characterization of the convex envelope of a bivariate function over special polytopes. Annals of Operations Research, Computational Methods in Global Optimization, 197–210 (1990)

30. Sherali, H.D., Alameddine., A.R.: A new reformulation linearization technique for bilinear programming problems. Journal of Global Optimization 2, 379–410 (1992)

    Article  MATH  MathSciNet  Google Scholar 

31. Sturm., J.F.: Using SeDuMi 1. 02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11 (12), 625–653 (1999)

    Google Scholar 

32. Tawarmalani, M., Sahinidis., N.V.: Semidefinite relaxations of fractional programs via novel convexifications techniques. Journal of Global Optimization 20, 137–158 (2001)

    Article  MATH  MathSciNet  Google Scholar 

33. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Boston MA, 2002

34. Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 2004, to appear

35. Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Research report, IBM T. J. Watson Research Center, Yorktown, USA, 2004

Download references