We studied the single-source capacitated facility location problem (SSCFLP), which can also be viewed as a representative structured binary optimization model with assignment, activation, and capacity constraints. The main difficulty comes from the discrete structure of the model and the coupling constraints, which make large-scale instances hard to solve. To exploit this structure, we introduced a split formulation that separates the original variables into two blocks connected by an equality constraint. For the reformulated model, we proposed an augmented Lagrangian decomposition method with tractable primal subproblems. We further showed that the augmented Lagrangian dual has zero duality gap with the original binary problem when the penalty parameter is sufficiently large. This result provides a theoretical basis for applying the augmented Lagrangian method to this discrete optimization problem. In addition, we used a primal recovery step and a final refinement step to improve feasible solutions. Numerical results demonstrated that the proposed method can produce high-quality feasible solutions on both synthetic and benchmark instances, especially for large instances in time-limited settings.
Citation: Deshan Hong, Rui Wang. An augmented Lagrangian decomposition method for the single-source capacitated facility location problem[J]. Journal of Industrial and Management Optimization, 2026, 22(7): 3284-3309. doi: 10.3934/jimo.2026120
We studied the single-source capacitated facility location problem (SSCFLP), which can also be viewed as a representative structured binary optimization model with assignment, activation, and capacity constraints. The main difficulty comes from the discrete structure of the model and the coupling constraints, which make large-scale instances hard to solve. To exploit this structure, we introduced a split formulation that separates the original variables into two blocks connected by an equality constraint. For the reformulated model, we proposed an augmented Lagrangian decomposition method with tractable primal subproblems. We further showed that the augmented Lagrangian dual has zero duality gap with the original binary problem when the penalty parameter is sufficiently large. This result provides a theoretical basis for applying the augmented Lagrangian method to this discrete optimization problem. In addition, we used a primal recovery step and a final refinement step to improve feasible solutions. Numerical results demonstrated that the proposed method can produce high-quality feasible solutions on both synthetic and benchmark instances, especially for large instances in time-limited settings.
| [1] |
A. Klose, A. Drexl, Facility location models for distribution system design, European J. Oper. Res., 162 (2005), 4–29. https://doi.org/10.1016/j.ejor.2003.10.031 doi: 10.1016/j.ejor.2003.10.031
|
| [2] |
Z.-J. M. Shen, Integrated supply chain design models: A survey and future research directions, J. Ind. Manag. Optim., 3 (2007), 1–27. https://doi.org/10.3934/jimo.2007.3.1 doi: 10.3934/jimo.2007.3.1
|
| [3] |
M. T. Melo, S. Nickel, F. Saldanha-da-Gama, Facility location and supply chain management — A review, European J. Oper. Res., 196 (2009), 401–412. https://doi.org/10.1016/j.ejor.2008.05.007 doi: 10.1016/j.ejor.2008.05.007
|
| [4] | Y. Costa, T. Melo, Facility location modeling in supply chain network design: Current state and emerging trends, In: The Palgrave Handbook of Supply Chain Management, Palgrave Macmillan, Cham, 2022, 1–36. https://doi.org/10.1007/978-3-030-89822-9_101-1 |
| [5] |
K. Holmberg, M. Rönnqvist, D. Yuan, An exact algorithm for the capacitated facility location problems with single sourcing, European J. Oper. Res., 113 (1999), 544–559. https://doi.org/10.1016/S0377-2217(98)00008-3 doi: 10.1016/S0377-2217(98)00008-3
|
| [6] |
Z. Yang, F. Chu, H. Chen, A cut-and-solve based algorithm for the single-source capacitated facility location problem, European J. Oper. Res., 221 (2012), 521–532. https://doi.org/10.1016/j.ejor.2012.03.047 doi: 10.1016/j.ejor.2012.03.047
|
| [7] |
S. L. Gadegaard, A. Klose, L. R. Nielsen, An improved cut-and-solve algorithm for the single-source capacitated facility location problem, EURO J. Comput. Optim., 6 (2018), 1–27. https://doi.org/10.1007/s13675-017-0084-4 doi: 10.1007/s13675-017-0084-4
|
| [8] |
D. Weninger, L. A. Wolsey, Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing, European J. Oper. Res., 310 (2023), 84–99. https://doi.org/10.1016/j.ejor.2023.02.042 doi: 10.1016/j.ejor.2023.02.042
|
| [9] |
R. K. Ahuja, J. B. Orlin, S. Pallottino, M. P. Scaparra, M. G. Scutellà, A multi-exchange heuristic for the single-source capacitated facility location problem, Manage. Sci., 50 (2004), 749–760. https://doi.org/10.1287/mnsc.1030.0193 doi: 10.1287/mnsc.1030.0193
|
| [10] |
I. A. Contreras, J. A. Díaz, Scatter search for the single source capacitated facility location problem, Ann. Oper. Res., 157 (2008), 73–89. https://doi.org/10.1007/s10479-007-0193-1 doi: 10.1007/s10479-007-0193-1
|
| [11] |
S. C. Ho, An iterated tabu search heuristic for the single source capacitated facility location problem, Appl. Soft Comput., 27 (2015), 169–178. https://doi.org/10.1016/j.asoc.2014.11.004 doi: 10.1016/j.asoc.2014.11.004
|
| [12] | R. D. Galvão, V. Marianov, Lagrangean relaxation-based techniques for solving facility location problems, In: Foundations of Location Analysis, Springer, 2011,391–420. https://doi.org/10.1007/978-1-4419-7572-0_17 |
| [13] |
M. L. Fisher, The Lagrangian relaxation method for solving integer programming problems, Manage. Sci., 27 (1981), 1–18. https://doi.org/10.1287/mnsc.27.1.1 doi: 10.1287/mnsc.27.1.1
|
| [14] |
G. B. Dantzig, P. Wolfe, Decomposition principle for linear programs, Oper. Res., 8 (1960), 101–111. https://doi.org/10.1287/opre.8.1.101 doi: 10.1287/opre.8.1.101
|
| [15] |
J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4 (1962), 238–252. https://doi.org/10.1007/BF01386316 doi: 10.1007/BF01386316
|
| [16] | F. Vanderbeck, L. A. Wolsey, Reformulation and decomposition of integer programs, In: 50 Years of Integer Programming 1958–2008, Springer, Berlin, Heidelberg, 2010,431–502. https://doi.org/10.1007/978-3-540-68279-0_13 |
| [17] |
F. Vanderbeck, M. W. P. Savelsbergh, A generic view of Dantzig–Wolfe decomposition in mixed integer programming, Oper. Res. Lett., 34 (2006), 296–306. https://doi.org/10.1016/j.orl.2005.05.009 doi: 10.1016/j.orl.2005.05.009
|
| [18] |
R. Rahmaniani, T. G. Crainic, M. Gendreau, W. Rei, The Benders decomposition algorithm: A literature review, European J. Oper. Res., 259 (2017), 801–817. https://doi.org/10.1016/j.ejor.2016.12.005 doi: 10.1016/j.ejor.2016.12.005
|
| [19] |
J. P. Vielma, Mixed integer linear programming formulation techniques, SIAM Rev., 57 (2015), 3–57. https://doi.org/10.1137/130915303 doi: 10.1137/130915303
|
| [20] |
R. Wang, C. Zhang, S. Pu, J. Gao, Z. Wen, A customized augmented Lagrangian method for block-structured integer programming, IEEE Trans. Pattern Anal. Mach. Intell., 46 (2024), 9439–9455. https://doi.org/10.1109/TPAMI.2024.3416514 doi: 10.1109/TPAMI.2024.3416514
|
| [21] |
R. Takapoui, N. Moehle, S. Boyd, A. Bemporad, A simple effective heuristic for embedded mixed-integer quadratic programming, Internat. J. Control, 93 (2020), 2–12. https://doi.org/10.1080/00207179.2017.1316016 doi: 10.1080/00207179.2017.1316016
|
| [22] |
N. L. Boland, A. C. Eberhard, On the augmented Lagrangian dual for integer programming, Math. Program., 150 (2015), 491–509. https://doi.org/10.1007/s10107-014-0763-3 doi: 10.1007/s10107-014-0763-3
|
| [23] |
M. J. Feizollahi, S. Ahmed, A. Sun, Exact augmented Lagrangian duality for mixed integer linear programming, Math. Program., 161 (2017), 365–387. https://doi.org/10.1007/s10107-016-1012-8 doi: 10.1007/s10107-016-1012-8
|
| [24] |
K. Sun, M. Sun, W. Yin, Decomposition methods for global solution of mixed-integer linear programs, SIAM J. Optim., 34 (2024), 1206–1235. https://doi.org/10.1137/22M1487321 doi: 10.1137/22M1487321
|
| [25] | C.-H. Chen, C.-J. Ting, Applying multiple ant colony system to solve single source capacitated facility location problem, In: Proceedings of the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence (ANTS 2006), Lecture Notes in Computer Science, Springer, 2006,508–509. https://doi.org/10.1007/11839088_55 |
| [26] |
E. S. Correa, M. T. A. Steiner, A. A. Freitas, C. Carnieri, A genetic algorithm for solving a capacitated $p$-median problem, Numer. Algorithms, 35 (2004), 373–388. https://doi.org/10.1023/B:NUMA.0000021767.42899.31 doi: 10.1023/B:NUMA.0000021767.42899.31
|
| [27] |
J. E. Beasley, Lagrangean heuristics for location problems, European J. Oper. Res., 65 (1993), 383–399. https://doi.org/10.1016/0377-2217(93)90118-7 doi: 10.1016/0377-2217(93)90118-7
|
| [28] |
X. Gu, S. Ahmed, S. S. Dey, Exact augmented Lagrangian duality for mixed integer quadratic programming, SIAM J. Optim., 30 (2020), 781–797. https://doi.org/10.1137/19M1271695 doi: 10.1137/19M1271695
|
| [29] |
X. Bai, J. Sun, X. Zheng, An augmented Lagrangian decomposition method for chance-constrained optimization problems, INFORMS J. Comput., 33 (2021), 1056–1069. https://doi.org/10.1287/ijoc.2020.1001 doi: 10.1287/ijoc.2020.1001
|
| [30] | K. O. Jörnsten, M. Näsberg, P. A. Smeds, Variable splitting: A new Lagrangean relaxation approach to some mathematical programming models, Technical Report MAT-R-85-04, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1985. |
| [31] |
M. Guignard, S. Kim, Lagrangean decomposition: A model yielding stronger Lagrangean bounds, Math. Program., 39 (1987), 215–228. https://doi.org/10.1007/BF02592954 doi: 10.1007/BF02592954
|
| [32] |
J. Barcelo, E. Fernandez, K. O. Jörnsten, Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem, European J. Oper. Res., 53 (1991), 38–45. https://doi.org/10.1016/0377-2217(91)90091-9 doi: 10.1016/0377-2217(91)90091-9
|
| [33] |
E. J. Alenezy, Solving capacitated facility location problem using Lagrangian decomposition and volume algorithm, Adv. Oper. Res., 2020 (2020), 1–7. https://doi.org/10.1155/2020/5239176 doi: 10.1155/2020/5239176
|
| [34] |
B. Wu, B. Ghanem, Lp-Box ADMM: A versatile framework for integer programming, IEEE Trans. Pattern Anal. Mach. Intell., 41 (2019), 1695–1708. https://doi.org/10.1109/TPAMI.2018.2845842 doi: 10.1109/TPAMI.2018.2845842
|
| [35] |
J. E. Beasley, OR-Library: Distributing test problems by electronic mail, J. Oper. Res. Soc., 41 (1990), 1069–1072. https://doi.org/10.1057/jors.1990.166 doi: 10.1057/jors.1990.166
|
| [36] |
D. G. Cattrysse, L. N. Van Wassenhove, A survey of algorithms for the generalized assignment problem, European J. Oper. Res., 60 (1992), 260–272. https://doi.org/10.1016/0377-2217(92)90077-M doi: 10.1016/0377-2217(92)90077-M
|
| [37] |
A. Ceselli, G. Righini, A branch-and-price algorithm for the capacitated $p$-median problem, Networks, 45 (2005), 125–142. https://doi.org/10.1002/net.20059 doi: 10.1002/net.20059
|
| [38] |
L. Lozano, J. C. Smith, A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs, Math. Program., 191 (2022), 381–404. https://doi.org/10.1007/s10107-018-1315-z doi: 10.1007/s10107-018-1315-z
|
Figures(3) / Tables(5)
Deshan Hong, Rui Wang. An augmented Lagrangian decomposition method for the single-source capacitated facility location problem[J]. Journal of Industrial and Management Optimization, 2026, 22(7): 3284-3309. doi: 10.3934/jimo.2026120
DownLoad: