A geometric characterization of “optimality-equivalent” relaxations

1. Alizadeh F. and Goldfarb D. (2003). Second-order cone programming. Math. Program. Ser. B 95: 3–51

   Article  Google Scholar 

2. Balas E., Ceria S. and Cornuéjols G. (1993). A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58: 295–324

   Article  Google Scholar 

3. Ben-Ameur W. and Neto J. (2006). A constraint generation algorithm for large scale linear programs using multiple-points separation. Math. Program. Ser. A 107: 517–537

   Article  Google Scholar 

4. Ben-Ameur W. and Neto J. (2007). Acceleration of cutting plane and column generation algorithms: applications to network design. Networks 49: 3–17

   Article  Google Scholar 

5. Ben-Ameur, W., Neto, J.: A geometric characterization of good relaxations. Technical report, Institut National des Telecommunications (2007)

6. Ben-Ameur W. and Ouorou A. (2006). Mathematical models of the delay constrained routing problem. Algorithmic Oper. Res. 1(2): 94–103

   Google Scholar 

7. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)

8. Chvátal V. (1973). Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4: 305–337

   Article  Google Scholar 

9. Elzinga J. and Moore T.G. (1973). A central cutting plane algorithm for the convex programming problem. Math. Program. 8: 134–145

   Article  Google Scholar 

10. Goemans M. and Williamson D. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42: 1115–1145

    Article  Google Scholar 

11. Goffin J.L. and Vial J.P. (2002). Convex nondifferentiable optimization: a survey focussed on the analytic center cutting plane method. Optim. Method Softw. 17: 805–867

    Google Scholar 

12. Gomory R.E. (1958). Outline of an algorithm for integer solutions to linear programs. Bull. Am. Soc. 64: 275–278

    Article  Google Scholar 

13. Hiriart-Urruty, J., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer (1993)

14. Kelley J.E. (1960). The cutting-plane method for solving convex programs. J. SIAM 8: 703–712

    Google Scholar 

15. Lovász L. and Schrijver A. (1991). Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1: 166–190

    Article  Google Scholar 

16. Lemaréchal C. (1975). An extension of Davidon methods to nondifferentiable problems. Math. program. 3: 95–109

    Google Scholar 

17. Lemaréchal C. (2003). The omnipresence of Lagrange. 4OR 1(1): 7–25

    Article  Google Scholar 

18. Nemhauser G.L. and Wolsey L.A. (1988). Integer and Combinatorial Optimization. Wiley, New-York

    Google Scholar 

19. Ouorou A. (2004). Epsilon-proximal decomposition method. Math. program. 99(1): 89–108

    Article  Google Scholar 

20. Padberg, M.: Linear Optimization and Extensions. Springer (1995)

21. Pochet, Y., Wolsey, L.: Algorithms and reformulations for lot-sizing problems in combinatorial optimization. In: Cook, W., Lovasz, L., Seymour, P. (eds.) Papers from the DIMACS Special Year, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20. American Mathematical Society (1995)

22. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer (2003)

23. Sherali H. and Adams W. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3: 411–430

    Article  Google Scholar 

24. Todd M. (2001). Semidefinite optimization. Acta Numer. 10: 515–560

    Article  Google Scholar 

25. Vaidya P.M. (1996). A new algorithm for minimizing convex functions over convex sets. Math. Program. 73: 291–341

    Google Scholar 

Download references