<p>The soft capacitated facility location problem (SCFLP) is a fundamental model in logistics, supply chain management, and network design, capturing the trade-off between facility opening costs and service flexibility under capacity constraints. This paper studies a variant, the soft capacitated facility location problem with submodular penalties (SCFLPSP), where unserved clients incur submodular penalty costs and where each client’s demand is integer-splittable across multiple facilities. We develop an LP-rounding-based algorithm that achieves a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(\lambda R + 4)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>λ</mi> <mi>R</mi> <mo>+</mo> <mn>4</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$R = \frac{\max _{i \in \mathcal {F}} f_i}{\min _{i \in \mathcal {F}} f_i}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>=</mo> <mfrac> <mrow> <msub> <mo movablelimits="true">max</mo> <mrow> <mi>i</mi> <mo>∈</mo> <mi mathvariant="script">F</mi> </mrow> </msub> <msub> <mi>f</mi> <mi>i</mi> </msub> </mrow> <mrow> <msub> <mo movablelimits="true">min</mo> <mrow> <mi>i</mi> <mo>∈</mo> <mi mathvariant="script">F</mi> </mrow> </msub> <msub> <mi>f</mi> <mi>i</mi> </msub> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\lambda = \frac{R + \sqrt{R^2 + 8R}}{2R}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>λ</mi> <mo>=</mo> <mfrac> <mrow> <mi>R</mi> <mo>+</mo> <msqrt> <mrow> <msup> <mi>R</mi> <mn>2</mn> </msup> <mo>+</mo> <mn>8</mn> <mi>R</mi> </mrow> </msqrt> </mrow> <mrow> <mn>2</mn> <mi>R</mi> </mrow> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$f_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>f</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> is the opening cost of facility <i>i</i>. When <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$R=1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, that is, when the opening costs are uniform, the approximation ratio simplifies to 6. Extensive experiments on publicly available datasets demonstrate that the proposed algorithm significantly improves computational efficiency compared with optimal solutions while maintaining high solution quality. Moreover, it exhibits more stable performance than greedy and ant colony optimization approaches and provides an explicit approximation guarantee, confirming both its effectiveness and reliability.</p>

An Lp-rounding Based Algorithm for Soft Capacitated Facility Location Problem with Submodular Penalties

期刊论文
发表日期：

2026年4月1日

查看全文

Hanyin Xiao,
Zhikang Zhang,
Weidong Li

摘要

The soft capacitated facility location problem (SCFLP) is a fundamental model in logistics, supply chain management, and network design, capturing the trade-off between facility opening costs and service flexibility under capacity constraints. This paper studies a variant, the soft capacitated facility location problem with submodular penalties (SCFLPSP), where unserved clients incur submodular penalty costs and where each client’s demand is integer-splittable across multiple facilities. We develop an LP-rounding-based algorithm that achieves a $(\lambda R + 4)$ $(λ R + 4)$ -approximation, where $R = \frac{\max _{i \in \mathcal {F}} f_i}{\min _{i \in \mathcal {F}} f_i}$ $R = \frac{{max}_{i \in F} f_{i}}{{min}_{i \in F} f_{i}}$ , $\lambda = \frac{R + \sqrt{R^2 + 8R}}{2R}$ $λ = \frac{R + \sqrt{R^{2} + 8 R}}{2 R}$ , and $f_i$ $f_{i}$ is the opening cost of facility i. When $R=1$ $R = 1$ , that is, when the opening costs are uniform, the approximation ratio simplifies to 6. Extensive experiments on publicly available datasets demonstrate that the proposed algorithm significantly improves computational efficiency compared with optimal solutions while maintaining high solution quality. Moreover, it exhibits more stable performance than greedy and ant colony optimization approaches and provides an explicit approximation guarantee, confirming both its effectiveness and reliability.