Solving the p-Median Problem with a Semi-Lagrangian Relaxation

1. P. Avella and A. Sassano, “On the p-median polytope,” Mathematical Programming, vol. 89, pp. 395–411, 2001.

   Article  MATH  MathSciNet  Google Scholar 

2. P. Avella, A. Sassano, and I. Vasil’ev, “Computational study of large-scale p-median problems,” Technical Report, Dipartimento Di Informatica e Sistemistica, Università di Roma “La Sapienza,” 2003.

3. O. Briant and D. Naddef, “The optimal diversity management problem,” Operations Research, vol. 52, no. 4, 2004.

4. Christofides, Graph Theory: An Algorithmic Approach. Academic Press, New York, 1975.

5. I.R.J. de Farias, “A family of facets for the uncapacitated p-median polytope,” Operations Research Letters, vol. 28, pp. 161–167, 2001.

   Article  MATH  MathSciNet  Google Scholar 

6. O. du Merle and J.-P. Vial, “Proximal-ACCPM, a cutting plane method for column generation and lagrangian relaxation: Application to the p-median problem,” Technical Report, Logilab, HEC, University of Geneva, 2002.

7. H. Everett III, “Generalized lagrange multiplier method for solving problems of optimum allocation of resources,” Operations Research, vol. 11, no. 3, pp. 399–471, 1963.

   Article  MathSciNet  MATH  Google Scholar 

8. A.M. Geoffrion, “Lagrangean relaxation for integer programming,” Mathematical Programming Study, vol. 2, pp. 82–114, 1974.

   MATH  MathSciNet  Google Scholar 

9. J.L. Goffin, A. Haurie, and J.P. Vial, “Decomposition and nondifferentiable optimization with the projective algorithm,” Management Science, vol. 37, pp. 284–302, 1992.

   Article  Google Scholar 

10. J.-L. Goffin and J. Vial, “Convex nondifferentiable optimization: A survey focussed on the analytic center cutting plane method,” Technical Report 99.02, Geneva University—HEC—Logilab, 1999.

11. M. Guignard and S. Kim, “Lagrangean decomposition: A model yielding stronger Lagrangean bounds,” Mathematical Programming, vol. 39, pp. 215–228, 1987.

    MATH  MathSciNet  Google Scholar 

12. P. Hansen and B. Jaumard, “Cluster analysis and mathematical programming,” Mathematical Programming, vol. 79, pp. 191–215, 1997.

    Article  MATH  MathSciNet  Google Scholar 

13. P. Hansen, N. Mladenovic, and D. Perez-Brito, “Variable neighborhood decomposition search,” Journal of Heuristics, vol. 7, pp. 335–350, 2001.

    Article  MATH  Google Scholar 

14. D.J. Higham and N.J. Higham, MATLAB Guide, SIAM, Philadelphia, Pennsilvania, USA, 2000.

15. J.B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, volume I and II. Springer-Verlag, Berlin, 1996.

16. E. Johnson, “Mathematical programming,” Chapter cyclic groups, cutting planes and shortest path, Academic press, pp. 185–211, 1973.

17. O. Kariv and L. Hakimi, “An algorithmic approach to network location problems. ii: The p-medians,” SIAM Journal of Applied Mathematics, vol. 37, no. 3, pp. 539–560, 1979.

    Article  MATH  MathSciNet  Google Scholar 

18. J.E. Kelley, “The cutting-plane method for solving convex programs,” Journal of the SIAM, vol. 8, pp. 703–712, 1960.

    MathSciNet  Google Scholar 

19. D. Klabjan, “A new subadditive approach to integer programming,” in W. Cook and A.S. Schulz, (eds.), Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27–29, 2002, Proceedings, volume 2337 of Lecture Notes in Computer Science. Springer, 2002.

20. D. Klabjan, “A practical algorithm for computing a subadditive dual function for set partitioning,” Computational Optimization and Applications, vol. 29, pp. 347–368, 2004.

    Article  MATH  MathSciNet  Google Scholar 

21. C. Lemaréchal and A. Renaud, “A geometric study of duality gaps, with applications,” Mathematical Programming, Ser. A, vol. 90, pp. 399–427, 2001.

    Article  MATH  Google Scholar 

22. J.M. Mulvey and H.P. Crowder, “Cluster analysis: An application of lagrangian relaxation,” Management Science, vol. 25, pp. 329–340, 1979.

    MATH  Google Scholar 

23. D.R. Musicant, “Matlab/cplex mex-files,” 2000. http://www.cs.wisc.edu/∼musicant/data/cplex/.

24. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, John Wiley and Sons, 1988.

25. G. Reinelt, “Tsplib,” 2001. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.

26. C. Tadonki, “Using cplex with matlab,” 2003. http://www.omegacomputer.com/staff/tadonki/using_cplex_with_matlab.htm.

Download references