基于线性规划的“设施选址问题”的整数规划建模、线性规划松弛与舍入算法求解示例

题目描述

设施选址问题（Uncapacitated Facility Location Problem, UFLP）是运筹学和组合优化中的一个经典问题。假设有 \(m\) 个潜在的设施点（例如，仓库、服务中心）和 \(n\) 个客户。每个设施点 \(i\) 如果被开设，需要支付固定的开设成本 \(f_i\)。将客户 \(j\) 分配到开设的设施点 \(i\) 提供服务，会产生服务成本（或连接成本） \(c_{ij}\)。我们的目标是：决定开设哪些设施点，并将每个客户分配给一个开设的设施点，使得开设成本和所有客户的服务总成本之和最小。所有设施点的服务能力视为无容量限制（Uncapacitated），即一个设施点可以为任意数量的客户服务。

这是一个 NP-hard 问题。我们需要：

1. 建立其整数线性规划模型。
2. 对整数规划进行线性规划松弛，得到一个多项式时间可解的线性规划。
3. 设计一个基于线性规划松弛解的舍入算法，获得一个整数可行解，并分析其近似比。

解题过程

第1步：建立整数线性规划模型

首先定义决策变量：

• \(y_i \in \{0, 1\}\)：二进制变量。如果设施点 \(i\) 被开设，则 \(y_i = 1\)；否则为 0。
• \(x_{ij} \in \{0, 1\}\)：二进制变量。如果客户 \(j\) 被分配到设施点 \(i\)，则 \(x_{ij} = 1\)；否则为 0。

优化目标：最小化总成本（开设成本 + 服务成本）。

\[\text{Minimize} \quad \sum_{i=1}^{m} f_i y_i + \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \]

约束条件：

1. 每个客户必须被分配给一个开设的设施点：对每个客户 \(j\)，必须恰好有一个设施点 \(i\) 为其服务。同时，只有在设施点 \(i\) 开设时，客户 \(j\) 才能被分配给它。这可以用一个约束表示：

\[ \sum_{i=1}^{m} x_{ij} = 1, \quad \forall j=1,\dots,n \]

\[ x_{ij} \le y_i, \quad \forall i=1,\dots,m, \quad \forall j=1,\dots,n \]

第二组约束确保了如果 $ y_i = 0 $（设施未开），则任何 $ x_{ij} $ 都必须为 0；如果 $ y_i = 1 $，则 $ x_{ij} $ 可以为 0 或 1。

2. 变量类型约束：

\[ y_i \in \{0, 1\}, \quad x_{ij} \in \{0, 1\} \]

完整整数规划模型 (IP) 如下：

\[\begin{aligned} \min \quad & \sum_{i=1}^{m} f_i y_i + \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{i=1}^{m} x_{ij} = 1, \quad \forall j=1,\dots,n \\ & x_{ij} \le y_i, \quad \forall i=1,\dots,m, \; \forall j=1,\dots,n \\ & y_i \in \{0, 1\}, \quad \forall i=1,\dots,m \\ & x_{ij} \in \{0, 1\}, \quad \forall i=1,\dots,m, \; \forall j=1,\dots,n \end{aligned} \]

第2步：线性规划松弛

整数规划是 NP-hard 的，直接求解困难。我们可以将其松弛为一个线性规划 (LP)，即把整数约束放松为连续非负约束：

\[y_i \ge 0, \quad x_{ij} \ge 0 \]

同时，注意约束 \(x_{ij} \le y_i\) 和 \(y_i \le 1\)（后者隐含在整数模型中，但松弛后需要显式加入吗？）。在整数模型中，\(y_i \in \{0,1\}\) 意味着 \(y_i \le 1\) 自然成立。但在 LP 松弛中，\(y_i\) 可以是任意非负数，我们是否需要显式加上 \(y_i \le 1\) 的约束？

检查一下：在 IP 中，如果 \(y_i > 1\)，但又是整数，则只能是 0 或 1，所以 \(y_i \le 1\) 是多余的。但在 LP 松弛中，\(y_i\) 可以大于 1。然而，目标函数是求最小化，其中 \(f_i > 0\)。如果允许 \(y_i > 1\)，会不必要地增加目标值（因为要乘以 \(f_i\)），并且约束 \(x_{ij} \le y_i\) 在 \(y_i > 1\) 时比 \(y_i = 1\) 更宽松，但这并不会带来好处，因为我们可以将 \(y_i\) 减小到 1 而不违反 \(x_{ij} \le y_i\)（只要 \(x_{ij} \le 1\)），同时降低目标值。所以，在 LP 松弛的最优解中，必然有 \(0 \le y_i \le 1\)。因此，我们可以不加 \(y_i \le 1\) 的约束，它会被自动满足。同理，对 \(x_{ij}\)，约束 \(\sum_i x_{ij} = 1\) 和 \(x_{ij} \le y_i \le 1\) 隐含了 \(x_{ij} \le 1\)。所以松弛后的线性规划 (LP) 为：

\[\begin{aligned} \min \quad & \sum_{i=1}^{m} f_i y_i + \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{i=1}^{m} x_{ij} = 1, \quad \forall j=1,\dots,n \\ & x_{ij} \le y_i, \quad \forall i,j \\ & y_i \ge 0, \quad \forall i \\ & x_{ij} \ge 0, \quad \forall i,j \end{aligned} \]

这个线性规划可以在多项式时间内求解（例如，使用内点法），设其最优解为 \((x^*, y^*)\)，最优目标值为 \(OPT_{LP}\)。显然，因为这是原整数规划的松弛，有 \(OPT_{LP} \le OPT_{IP}\)，其中 \(OPT_{IP}\) 是原整数规划的最优值。

第3步：设计舍入算法（一种简单的随机舍入）

我们介绍一种经典且分析简单的随机舍入算法。其思想是利用 LP 解 \((x^*, y^*)\) 来随机决定开设哪些设施，然后分配客户。

算法步骤：

1. 求解 LP 松弛：得到最优分数解 \((x^*, y^*)\)。
2. 设施随机开设：
   • 对每个设施点 \(i\)，以概率 \(y_i^*\) 独立地决定是否开设它。也就是说，我们生成一个随机数 \(\theta_i \in [0,1]\)，如果 \(\theta_i \le y_i^*\)，则开设设施 \(i\)（设 \(\hat{y}_i = 1\)），否则不开（\(\hat{y}_i = 0\)）。
   • 注意，\(y_i^* \in [0,1]\)，可以视为概率。这个步骤是“随机舍入”的核心。
3. 客户分配：
   • 对于每个客户 \(j\)，我们需要将其分配给一个开设的设施。
   • 在 LP 解中，客户 \(j\) 的需求被分数地分配给了多个设施（因为 \(\sum_i x_{ij}^* = 1\)）。一个自然的想法是，将客户 \(j\) 分配给“在随机开设步骤中实际被开设的、且在 LP 解中为其服务份额（\(x_{ij}^*\)）最大的那个设施”。但为了简化分析和保证可行性，我们采用以下分配规则：
   • 考虑客户 \(j\) 在 LP 解中的“服务模式”。我们定义客户 \(j\) 的“邻域”为所有满足 \(x_{ij}^* > 0\) 的设施点 \(i\) 的集合。在随机开设设施后，客户 \(j\) 至少有一个邻居设施被开设的概率很高（因为 \(\sum_i x_{ij}^* = 1\) 且 \(x_{ij}^* \le y_i^*\)，所以邻居设施的开设概率之和至少为 1？ 实际上，由 \(x_{ij}^* \le y_i^*\)，有 \(\sum_i y_i^* \ge \sum_i x_{ij}^* = 1\)。但设施是独立随机开设的，所以客户 \(j\) 的所有邻居设施都没被开设的概率是 \(\prod_{i: x_{ij}^* > 0} (1 - y_i^*)\)。这个概率可能大于 0，导致客户无设施可分配。
   • 为了解决这个问题，可以采用“两步法”：如果一个客户在第一次随机开设后没有邻居设施被开设，则我们强制开设其“最佳”邻居设施（例如，选择 \(y_i^*\) 最大的那个，或者以某种条件概率补充开设）。但为了保持算法简单且可分析，我们采用另一种更系统的随机舍入方法：将客户 \(j\) 的分配与设施开设进行耦合。

改进的随机舍入算法（经典方法）：

1. 求解 LP 松弛，得到 \((x^*, y^*)\)。

2. 排序：对每个客户 \(j\)，将其可能的设施点 \(i\) 按照连接成本 \(c_{ij}\) 非递减排序。为简化，假设所有 \(c_{ij} \ge 0\)。

3. 设施依赖的客户分配：算法将顺序处理每个客户 \(j\)，并为其“选择”一个设施。但这会导致客户间分配耦合。更标准的方法是独立处理每个设施的开店决策，但客户分配基于开店结果。然而，为了获得有理论保证的近似比，我们采用以下由 Shmoys, Tardos, Aardal 提出的算法思路（常称为“滤波舍入”或“条件概率舍入”）的简化版：

   a. 设施预选：独立地以概率 \(y_i^*\) 开设每个设施 \(i\)，得到开设集合 \(S\)。
   b. 客户临时分配：对于每个客户 \(j\)，在 LP 解中，其被分配到各个设施的概率分布由 \(x_{ij}^*\) 给出。但我们需要一个整数分配。一种方法是：将客户 \(j\) 分配给集合 \(S\) 中“最便宜”的设施（即 \(\arg\min_{i \in S} c_{ij}\)）。然而，这可能导致某个客户被分配到一个连接成本很高的设施（如果其便宜的邻居都没开）。
   c. 为了控制连接成本，我们可以采用以下策略：对于一个客户 \(j\)，在 LP 解中，我们可以定义一个“预算”或“期望连接成本”。具体地，令 \(C_j^* = \sum_i c_{ij} x_{ij}^*\) 是客户 \(j\) 在 LP 解中的期望连接成本。然后，在舍入后，我们希望每个客户的实际连接成本不要比 \(C_j^*\) 大太多。我们可以证明，如果以概率 \(x_{ij}^* / y_i^*\) （当 \(i \in S\) 时）将客户 \(j\) 分配给设施 \(i\)，但需要处理 \(y_i^*\) 可能为 0 的情况。实际上，经典算法采用以下步骤：

标准随机舍入算法描述（近似比为 4 的算法）：

1. 求解 LP，得到 \((x^*, y^*)\)。
2. 设施阶段：对每个设施 \(i\)，以概率 \(\min(1, 4 y_i^*)\) 开设它？不对，这样会超过概率 1。实际上，常用的是：以概率 \(y_i^*\) 独立开设。但这样得到的近似比不是常数。为了获得常数近似比，需要更复杂的技术，如“滤波舍入”(Filtering Rounding) 或“原始对偶”方法。由于我们重点是展示基于 LP 舍入的思想，我们下面描述一个简化版本的随机舍入，并给出直观解释，而不深入复杂证明。

简化但可分析的随机舍入（需假设三角不等式）：
如果服务成本 \(c_{ij}\) 满足三角不等式（即 \(c_{ij} \le c_{ik} + c_{kj}\) 对于任意 \(i,j,k\)），则存在著名的 4-近似算法（由 Chudak & Shmoys 提出）。其步骤如下：

a. 求解 LP 松弛。
b. 对每个客户 $ j $，计算其“平均连接成本”：$ \bar{C}_j = \sum_i c_{ij} x_{ij}^* $。
c. 对每个客户 $ j $，定义其“可接受”的设施集合为 $ F_j = \{ i : c_{ij} \le 2 \bar{C}_j \} $。（滤波步骤）
d. 对于每个客户 $ j $，将其 LP 分配集中到可接受设施上：即定义新的分数解 $ \tilde{x}_{ij} = x_{ij}^* $ 如果 $ i \in F_j $，否则为 0。然后重新调整使其和为 1：令 $ \tilde{x}_{ij} = \frac{x_{ij}^*}{\sum_{k \in F_j} x_{kj}^*} $ 对于 $ i \in F_j $，这样 $ \sum_{i \in F_j} \tilde{x}_{ij} = 1 $。
e. 现在，注意到对于每个客户 $ j $，其所有“有效”设施 $ i $（即 $ \tilde{x}_{ij} > 0 $）都有 $ c_{ij} \le 2 \bar{C}_j $，并且 $ \tilde{x}_{ij} \le y_i^* / \gamma $ 对某个 $ \gamma $（可以证明，经过调整，有 $ \tilde{x}_{ij} \le 2 y_i^* $，因为被过滤掉的部分最多占一半）。
f. 然后进行随机舍入：以概率 $ y_i^* $ 独立开设设施 $ i $。对于客户 $ j $，从集合 $ F_j $ 中随机选择一个设施 $ i $，选择概率与 $ \tilde{x}_{ij} $ 成比例。但设施可能没开，所以需要条件概率调整。最终可以证明，每个客户以至少某个常数概率被分配到一个开设的、成本可控的设施。通过重复实验或使用联合界，可以得到一个整体代价的期望值不超过 $ 4 \cdot OPT_{LP} $。

由于完整的算法和证明较为复杂，我们回到最基础的随机舍入思想，并给出一个简单的启发式舍入方案，它虽然不能保证理论近似比，但实践中有效：

实用启发式舍入：

1. 求解 LP 松弛。
2. 阈值舍入设施：选择一个阈值 \(\theta \in (0,1]\)，例如 \(\theta = 0.5\)。对于每个设施 \(i\)，如果 \(y_i^* \ge \theta\)，则开设它（令 \(\hat{y}_i = 1\)），否则不开（\(\hat{y}_i = 0\)）。这个步骤是确定性舍入。
3. 贪婪分配客户：对于每个客户 \(j\)，将其分配给开设的设施中连接成本 \(c_{ij}\) 最小的那个。

这个方法的合理性：

• 开设成本：由于我们只开设了 \(y_i^*\) 较大的设施，而这些 \(y_i^*\) 的和不会太大（因为目标函数最小化），所以总开设成本不会超过 \((1/\theta) \sum_i f_i y_i^*\)。
• 连接成本：对于客户 \(j\)，在 LP 解中，其连接成本期望为 \(C_j^* = \sum_i c_{ij} x_{ij}^*\)。在整数解中，如果其被分配到的设施不在 LP 解的主要支持集中，成本可能增加。但通过将客户分配给最近的开设施，可以控制成本。可以证明，如果设施开设决策是独立的随机事件，则期望连接成本有上界。在确定性阈值舍入中，我们可以通过分析 \(x_{ij}^*\) 和 \(y_i^*\) 的关系来估计。

实际上，著名的 3-近似算法（由 Chudak 提出，对度量成本）就是基于随机舍入，然后进行贪婪分配。其分析表明，期望总成本不超过 \(OPT_{LP} + 2 \sum_j C_j^* \le 3 \cdot OPT_{LP}\)。

第4步：算法近似比分析（概述）

对于度量 UFLP（即 \(c_{ij}\) 满足三角不等式，且 \(c_{ij} = c_{ji}\)，非负），上述随机舍入算法（以概率 \(y_i^*\) 独立开设设施，然后每个客户分配到最近的开设施）可以达到期望近似比 1.74 甚至更优（后续研究改进）。其分析思路如下：

1. 期望开设成本：由于设施 \(i\) 以概率 \(y_i^*\) 独立开设，所以期望开设成本为 \(\sum_i f_i \cdot y_i^*\)。
2. 期望连接成本：对于客户 \(j\)，我们需要计算其期望连接成本。设 \(S\) 是随机开设的设施集合。客户 \(j\) 将被分配给 \(S\) 中距离最近的设施。我们需要比较这个距离与 LP 解中的连接成本分布。
3. 关键引理：在度量条件下，可以证明客户 \(j\) 的期望连接成本 \(E[c_{\min}(j, S)] \le 3 C_j^*\)，其中 \(C_j^* = \sum_i c_{ij} x_{ij}^*\)。
   • 直观原因：在 LP 解中，客户 \(j\) 的需求被分散到多个设施，每个设施 \(i\) 承担了 \(x_{ij}^*\) 的份额。如果这些设施以概率 \(y_i^* \ge x_{ij}^*\) 独立开设，那么客户 \(j\) 的“最近开设设施”的期望距离可以通过将 \(C_j^*\) 与到其他设施的“备份”成本联系起来，利用三角不等式得到上界。
4. 总期望成本：因此，总期望成本 \(E[ALG] = E[\text{开设成本}] + E[\text{连接成本}] \le \sum_i f_i y_i^* + 3 \sum_j C_j^* = OPT_{LP} + 3 \cdot (OPT_{LP} - \sum_i f_i y_i^*) \le 3 \cdot OPT_{LP}\)。所以这是一个 3-近似算法。

更精细的分析可以将系数降低到 1.736 或更好，但这涉及更复杂的概率分析和补偿步骤。

总结

本题展示了如何对 NP-hard 的设施选址问题建立整数规划模型，然后通过线性规划松弛获得下界，并基于 LP 解设计舍入算法（如随机舍入）来获得高质量的可行整数解。对于度量成本的设施选址问题，基于 LP 舍入的随机算法可以在多项式时间内给出具有常数近似比（例如 3 或 1.5）的解。这种方法的核心在于利用分数解的结构信息来指导整数决策，并通过概率分析或构造性方法保证解的质量。