×

zbMATH — the first resource for mathematics

Solving the staircase cost facility location problem with decomposition and piecewise linearization. (English) Zbl 0809.90093
Summary: Facility location problems with staircase costs, i.e. fixed costs that appear at several levels of production, are large structured mixed integer programming problems, which often are quite hard to solve. In this paper solution methods based on convex piecewise linearization and Benders decomposition are investigated. Using convex piecewise linearization, only the integer variables that are needed to improve the approximation are introduced, and computational tests show that in average only a few are needed. Benders decomposition can be used to solve the resulting problems, and we show how to recalculate Benders cuts when new variables are introduced, so they still can be used when the approximation is improved.

MSC:
90B85 Continuous location
90C11 Mixed integer programming
Software:
XMP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beale, E.M.L., Two transportation problems, (), 780-788 · Zbl 0578.90070
[2] Benders, J.F., Partitioning procedures for solving mixed-variables programming problems, Numerische matematik, 4, 238-252, (1962) · Zbl 0109.38302
[3] Bertsekas, D.P.; Tseng, P., The RELAX codes for linear minimum cost network flow problems, Annals of operations research 7: FORTRAN codes for network optimization, 125-190, (1988)
[4] Cornuejols, G.; Sridharan, R.; Thizy, J.M., A comparison of heuristics and relaxations for the capacitated plant location problem, European journal of operational research, 50, 280-297, (1991) · Zbl 0734.90046
[5] Efroymson, M.A.; Ray, T.L., A branch-bound algorithm for plant location, Operations research, 14, 361-368, (1966)
[6] Falk, J.E.; Soland, R.M., An algorithm for separable nonconvex programming problems, Management science, 15, 550-569, (1969) · Zbl 0172.43802
[7] Francis, R.L.; McGinnis, L.F.; White, J.A., Locational analysis, European journal of operational research, 12, 220-252, (1983) · Zbl 0502.90019
[8] Geoffrion, A.M.; McBride, R., Lagrangean relaxation applied to capacitated facility location problems, AIIE transactions, 10, 40-47, (1978)
[9] Holmberg, K., Capacitated facility location with staircase costs, ()
[10] Holmberg, K., Decomposition in large scale mathematical programming, (), No. 131 · Zbl 0817.90070
[11] Holmberg, K., Transportation and location problems with staircase costs, ()
[12] Holmberg, K., Staircase cost problems: solution methods based on convex piecewise linearization, benders decomposition, Lagrangean relaxation and cross decomposition, ()
[13] Holmberg, K., Linearizations of the staircase cost facility location problem, ()
[14] Jacobsen, S.K., Heuristics for the capacitated plant location model, European journal of operational research, 12, 253-261, (1983) · Zbl 0514.90018
[15] Marsten, R.E., The design of the XMP linear programming library, ACM transactions on mathematical software, 7, 481-497, (1981)
[16] Rech, P.; Barton, L.G., A non-convex transportation algorithm, (), 250-260
[17] Rönnqvist, M., En jämförelse mellan benders dekomposition och allmän trädsökning för kapaciterad anläggningslokalisering med trappstegskostnader, (), (in Swedish)
[18] Van Roy, T.J., Cross decomposition for mixed integer programming, Mathematical programming, 25, 46-63, (1983) · Zbl 0505.90057
[19] Van Roy, T.J., A cross decomposition algorithm for capacitated facility location, Operations research, 34, 145-163, (1986) · Zbl 0594.90022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.