Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation

References

• Aardal K. Capacitated facility location: Separation algorithm and computational experience. Math. Programming (1998) 81:149–175Crossref, Google Scholar
• Aardal K., Pochet Y., Wolsey L. A. Capacitated facility location: Valid inequalities and facets. Math. Oper. Res. (1995) 20:552–582Link, Google Scholar
• Beasley J. E. OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. (1990) 41:1069–1072Crossref, Google Scholar
• Carraresi P., Frangioni A., Nonato M. Applying bundle methods to the optimization of polyhedral functions: An applications-oriented development. Ric. Oper. (1995) 25:5–49Google Scholar
• Chen B., Guignard M. Polyhedral analysis and decompositions for capacitated plant location-type problems. Discrete Appl. Math. (1998) 82:79–91Crossref, Google Scholar
• Cornuéjols G., Sridharan R., Thizy J.-M. A comparison of heuristics and relaxations for the capacitated plant location problem. Eur. J. Oper. Res. (1991) 50:280–297Crossref, Google Scholar
• 1997CPLEX Division, ILOG Inc.Google Scholar
• Dantzig G. B., Wolfe P. Decomposition principle for linear programs. Oper. Res. (1960) 8:101–111Link, Google Scholar
• du Merle O., Villeneuve D., Desrosiers J., Hansen P. Stabilized column generation. Discrete Math. (1999) 194:229–237Crossref, Google Scholar
• Frangioni A., Gallo G. A bundle type dual-ascent approach to linear multi-commodity min cost flow problems. INFORMS J. Comput. (1999) 11:370–393Link, Google Scholar
• Goffin J.-L., Vial J.-P. Shallow, deep and very deep cuts in the analytic center cutting plane method. Math. Programming (1999) 84:89–103Crossref, Google Scholar
• Goffin J.-L., Haurie A., Vial J.-P. Decomposition and nondifferentiable optimization with the projective algorithm. Management Sci. (1992) 38:284–302Link, Google Scholar
• Goffin J.-L., Haurie A., Vial J.-P., Zhu D. L. Using central prices in the decomposition of linear programs. Eur. J. Oper. Res. (1993) 64:593–409Crossref, Google Scholar
• Gondzio J., Sarkissian R. (1996) . Column generation with a primal-dual method. Technical report 1996:6. LogiLab, Haute École de Commerce, Section of Management Studies, University of Geneva, Geneva, Switzerland. http://ecolu-info.unige.ch/˜logilab/reports Google Scholar
• Gondzio J., du Merle O., Sarkissian R., Vial J.-P. ACCPM—A library for convex optimization based on an analytic center cutting plane method. Eur. J. Oper. Res. (1996) 94:206–211Crossref, Google Scholar
• Gu Z., Nemhauser G. L., Savelsbergh M. W. P. Lifted cover inequalities for 0-1 integer programs: Complexity. INFORMS J. Comput. (1999) 11:117–123Link, Google Scholar
• Guignard M., Zhu S. (1994) . A two-phase dual algorithm for solving Lagrangean duals in mixed integer programming. Report 94-10-03, Operations and Information Management Department, The Wharton School, University of Pennsylvania, Philadelphia, PAGoogle Scholar
• Kelley J. E. The cutting-plane method for solving convex programs. J. SIAM (1960) 8:703–712Google Scholar
• Klose A. A branch and bound algorithm for an uncapacitated facility location problem with a side constraint. Internat. Trans. Oper. Res. (1998) 5:155–168Crossref, Google Scholar
• Klose A. An LP-based heuristic for two-stage capacitated facility location problems. J. Oper. Res. Soc. (1999) 50:157–166Crossref, Google Scholar
• Klose A., Drexl A., Klose A., Van Wassenhove L. N., Speranza M. G. Combinatorial optimization problems of the assignment type and a partitioning approach. Quantitative Approaches to Distribution Logistics and Supply Chain Management (2002) 519(Springer-Verlag, Berlin, Heidelberg, New York) 215–245Crossref, Google Scholar
• Kochmann G. A., McCallum C. J. Facility location models for planning a transatlantic communications network. Eur. J. Oper. Res. (1981) 6:205–211Crossref, Google Scholar
• Lemaréchal C., Nemhauser G. L., Rinnooy Kan A. H. G., Todd M. J. Nondifferentiable optimization. Optimization, Vol. 1. Handbooks in Operations Research and Management Science (1989) (North-Holland, Amsterdam, The Netherlands) 529–572Google Scholar
• Marsten R. E., Hogan W. W., Blankenship J. W. The Boxstep method for large-scale optimization. Oper. Res. (1975) 23:389–405Link, Google Scholar
• Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Sci. (1999) 45:414–424Link, Google Scholar
• Martinson R. K., Tind J. An interior point method in Dantzig-Wolfe decomposition. Comput. Oper. Res. (1999) 26:1195–1216Crossref, Google Scholar
• Mirzaian A. Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds. Networks (1985) 15:1–20Crossref, Google Scholar
• Neame P., Boland N., Ralph D. (1998) . A unifying framework for column generation stabilization methods. Working paper, Department of Mathematics, University of Melbourne, Melbourne, AustraliaGoogle Scholar
• Pochet Y., Wolsey L. A. Lot-size models with backlogging: Strong reformulations and cutting planes. Math. Programming (1988) 40:317–335Crossref, Google Scholar
• Ryu C., Guignard M. (1992) . An efficient algorithm for the capacitated plant location problem. Working paper 92-11-02, Decision Sciences Department, The Wharton School, University of Pennsylvania, Philadelphia, PAGoogle Scholar
• Sridharan R. The capacitated plant location problem. Eur. J. Oper. Res. (1995) 87:203–213Crossref, Google Scholar
• Van Roy T. J. Cross decomposition for mixed integer programming. Math. Programming (1983) 25:46–63Crossref, Google Scholar
• Van Roy T. J. A cross decomposition algorithm for capacitated facility location. Oper. Res. (1986) 34:145–163Link, Google Scholar
• Wentges P. Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. (1997) 4:151–162Crossref, Google Scholar