在覆盖所有客户的同时最大限度地减少商店数量
Minimize number of shops while reaching all customers
在这个特定的问题中，我有一个虚构的城市，分为正方形 - 基本上是 MxN 正方形网格覆盖城市. M 和 N 可以比较大，所以我有超过 40,000 个方形单元格的案例。
我有一些客户 Z 分布在这个网格中，一些单元格将包含很多客户，而另一些则为空。我想找到一种方法来放置 最少 数量的商店（每个单元格只有一个），以便能够为所有客户提供服务，但限制所有客户都必须“触手可及”一家商店，所有 位顾客都需要包括在内。
作为额外的一些变化，我有这些 constraints/issues:
- 客户可以移动的最大距离 - 如果商店位于太远的单元格中，则客户无法与该商店相关联。 编辑：这不是真正的距离，它是衡量顾客到达商店的难易程度，所以我不能使用圆圈...
- 在尊重上述条件（1）的情况下，很可能有多个商店到达同一客户的距离。在这种情况下，最近的商店应该获胜。
目前我试图忽略成本问题 - 许多客户意味着更大的商店和更高的成本 - 但也许在某个时候我也会考虑这个问题。问题是，我不知道我正在查看的问题的名称，也不知道可能的算法解决方案：这可以作为线性规划问题来解决吗？
我通常在 Python 中编写代码，因此对于可能的算法方法的任何建议 and/or 一些 code/libraries 将不胜感激。
提前致谢。
编辑：作为后续，我有点发现我可以解决这个问题作为 MINLP“无能力设施问题”，但我找到的所有信息都是这样太复杂：我不关心哪家商店为哪个客户提供服务，我只关心是否以及在哪里建了一家商店。我有第二种方法 - 作为 post 处理 - 将客户关联到最合适的商店。
我发现的所有代码都建立了这个巨大的线性系统，将每个顾客每个商店的约束关联起来（如此处“解释”：https://en.m.wikipedia.org/wiki/Facility_location_problem#Uncapacitated_facility_location），所以在像我这样的情况下，我很容易得到一个具有数百万行和列的线性系统，具有 integer/binary 个变量，大约需要宇宙年龄才能求解。
一定有更简单的方法来处理这个...
我认为这可以表述为集合覆盖问题 link.
你说：
in a situation like mine I could easily end up with a linear system
with millions of rows and columns, which with integer/binary variables
will take about the age of the universe to solve
让我们看看这是否属实。
第 1 步：生成一些数据
我生成了一个 200 x 200 的网格，产生了 40,000 个单元格。我随机放置 M=500 个客户。这看起来像：
---- 22 PARAMETER cloc customer locations
x y
cust1 35 75
cust2 169 84
cust3 111 18
cust4 61 163
cust5 59 102
...
cust497 196 148
cust498 115 136
cust499 63 101
cust500 92 87
第 2 步：计算每个客户的覆盖面
下一步是为每个客户 c 确定可到达的允许位置 (i,j)。我为此创建了一个 large sparse boolean matrix reach(c,i,j)。我使用了规则：如果曼哈顿距离是
|i-cloc(c,'x')|+|j-cloc(c,'y')| <= 10
然后 (i,j) 的商店可以为客户 c 提供服务。我的数据如下：
（不存储零）。这个数据结构有 106k 个元素。
第 3 步：形成 MIP 模型
我们构建了一个简单的 MIP 模型：
不等式约束表示：我们需要至少有一家商店在每位顾客都可以到达的范围内。这是一个非常容易制定和实施的模型。
第 4 步：求解
这是一个大而简单的 MIP。它有 40,000 个二进制变量。它解决得非常快。在我的笔记本电脑上，使用商业求解器只需不到 1 秒（使用开源求解器 CBC 只需 3 秒）。
解决方案如下：
---- 47 VARIABLE numStores.L = 113 number of stores
---- 47 VARIABLE placeStore.L store locations
j1 j6 j7 j8 j9 j15 j16 j17 j18
i4 1
i18 1
i40 1
i70 1
i79 1
i80 1
i107 1
i118 1
i136 1
i157 1
i167 1
i193 1
+ j21 j23 j26 j28 j29 j31 j32 j36 j38
i10 1
i28 1
i54 1
i72 1
i96 1
i113 1
i147 1
i158 1
i179 1
i184 1
i198 1
+ j39 j44 j45 j46 j49 j50 j56 j58 j59
i5 1
i18 1
i39 1
i62 1
i85 1
i102 1
i104 1
i133 1
i166 1
i195 1
+ j62 j66 j67 j68 j69 j73 j74 j76 j80
i11 1
i16 1
i36 1
i61 1
i76 1
i105 1
i112 1
i117 1
i128 1
i146 1
i190 1
+ j82 j84 j85 j88 j90 j92 j95 j96 j97
i17 1
i26 1
i35 1
i48 1
i68 1
i79 1
i97 1
i136 1
i156 1
i170 1
i183 1
i191 1
+ j98 j102 j107 j111 j112 j114 j115 j116 j118
i4 1
i22 1
i36 1
i56 1
i63 1
i68 1
i88 1
i100 1
i101 1
i111 1
i129 1
i140 1
+ j119 j121 j126 j127 j132 j133 j134 j136 j139
i11 1
i30 1
i53 1
i72 1
i111 1
i129 1
i144 1
i159 1
i183 1
i191 1
+ j140 j147 j149 j150 j152 j153 j154 j156 j158
i14 1
i35 1
i48 1
i83 1
i98 1
i117 1
i158 1
i174 1
i194 1
+ j161 j162 j163 j164 j166 j170 j172 j174 j175
i5 1
i32 1
i42 1
i61 1
i69 1
i103 1
i143 1
i145 1
i158 1
i192 1
i198 1
+ j176 j178 j179 j180 j182 j183 j184 j188 j191
i6 1
i13 1
i23 1
i47 1
i61 1
i81 1
i93 1
i103 1
i125 1
i182 1
i193 1
+ j192 j193 j196
i73 1
i120 1
i138 1
i167 1
我认为我们已经驳斥了您关于 MIP 模型不是解决此问题的可行方法的说法。
请注意，宇宙年龄为137亿年或4.3e17秒。所以我们已经实现了大约 1e17 的加速。这是我的记录。
请注意，此模型不会找到商店的最佳位置，而只会找到一种配置，该配置可以最大限度地减少为所有客户提供服务所需的商店数量。从这个意义上说，它是最佳的。但该解决方案不会缩短客户与商店之间的距离。
在这个特定的问题中，我有一个虚构的城市，分为正方形 - 基本上是 MxN 正方形网格覆盖城市. M 和 N 可以比较大，所以我有超过 40,000 个方形单元格的案例。
我有一些客户 Z 分布在这个网格中，一些单元格将包含很多客户，而另一些则为空。我想找到一种方法来放置 最少 数量的商店（每个单元格只有一个），以便能够为所有客户提供服务，但限制所有客户都必须“触手可及”一家商店，所有 位顾客都需要包括在内。
作为额外的一些变化，我有这些 constraints/issues:
- 客户可以移动的最大距离 - 如果商店位于太远的单元格中，则客户无法与该商店相关联。 编辑：这不是真正的距离，它是衡量顾客到达商店的难易程度，所以我不能使用圆圈...
- 在尊重上述条件（1）的情况下，很可能有多个商店到达同一客户的距离。在这种情况下，最近的商店应该获胜。
目前我试图忽略成本问题 - 许多客户意味着更大的商店和更高的成本 - 但也许在某个时候我也会考虑这个问题。问题是，我不知道我正在查看的问题的名称，也不知道可能的算法解决方案：这可以作为线性规划问题来解决吗？
我通常在 Python 中编写代码，因此对于可能的算法方法的任何建议 and/or 一些 code/libraries 将不胜感激。
提前致谢。
编辑：作为后续，我有点发现我可以解决这个问题作为 MINLP“无能力设施问题”，但我找到的所有信息都是这样太复杂：我不关心哪家商店为哪个客户提供服务，我只关心是否以及在哪里建了一家商店。我有第二种方法 - 作为 post 处理 - 将客户关联到最合适的商店。
我发现的所有代码都建立了这个巨大的线性系统，将每个顾客每个商店的约束关联起来（如此处“解释”：https://en.m.wikipedia.org/wiki/Facility_location_problem#Uncapacitated_facility_location），所以在像我这样的情况下，我很容易得到一个具有数百万行和列的线性系统，具有 integer/binary 个变量，大约需要宇宙年龄才能求解。
一定有更简单的方法来处理这个...
我认为这可以表述为集合覆盖问题 link.
你说：
in a situation like mine I could easily end up with a linear system with millions of rows and columns, which with integer/binary variables will take about the age of the universe to solve
让我们看看这是否属实。
第 1 步：生成一些数据
我生成了一个 200 x 200 的网格，产生了 40,000 个单元格。我随机放置 M=500 个客户。这看起来像：
---- 22 PARAMETER cloc customer locations
x y
cust1 35 75
cust2 169 84
cust3 111 18
cust4 61 163
cust5 59 102
...
cust497 196 148
cust498 115 136
cust499 63 101
cust500 92 87
第 2 步：计算每个客户的覆盖面
下一步是为每个客户 c 确定可到达的允许位置 (i,j)。我为此创建了一个 large sparse boolean matrix reach(c,i,j)。我使用了规则：如果曼哈顿距离是
|i-cloc(c,'x')|+|j-cloc(c,'y')| <= 10
然后 (i,j) 的商店可以为客户 c 提供服务。我的数据如下：
（不存储零）。这个数据结构有 106k 个元素。
第 3 步：形成 MIP 模型
我们构建了一个简单的 MIP 模型：
不等式约束表示：我们需要至少有一家商店在每位顾客都可以到达的范围内。这是一个非常容易制定和实施的模型。
第 4 步：求解
这是一个大而简单的 MIP。它有 40,000 个二进制变量。它解决得非常快。在我的笔记本电脑上，使用商业求解器只需不到 1 秒（使用开源求解器 CBC 只需 3 秒）。
解决方案如下：
---- 47 VARIABLE numStores.L = 113 number of stores
---- 47 VARIABLE placeStore.L store locations
j1 j6 j7 j8 j9 j15 j16 j17 j18
i4 1
i18 1
i40 1
i70 1
i79 1
i80 1
i107 1
i118 1
i136 1
i157 1
i167 1
i193 1
+ j21 j23 j26 j28 j29 j31 j32 j36 j38
i10 1
i28 1
i54 1
i72 1
i96 1
i113 1
i147 1
i158 1
i179 1
i184 1
i198 1
+ j39 j44 j45 j46 j49 j50 j56 j58 j59
i5 1
i18 1
i39 1
i62 1
i85 1
i102 1
i104 1
i133 1
i166 1
i195 1
+ j62 j66 j67 j68 j69 j73 j74 j76 j80
i11 1
i16 1
i36 1
i61 1
i76 1
i105 1
i112 1
i117 1
i128 1
i146 1
i190 1
+ j82 j84 j85 j88 j90 j92 j95 j96 j97
i17 1
i26 1
i35 1
i48 1
i68 1
i79 1
i97 1
i136 1
i156 1
i170 1
i183 1
i191 1
+ j98 j102 j107 j111 j112 j114 j115 j116 j118
i4 1
i22 1
i36 1
i56 1
i63 1
i68 1
i88 1
i100 1
i101 1
i111 1
i129 1
i140 1
+ j119 j121 j126 j127 j132 j133 j134 j136 j139
i11 1
i30 1
i53 1
i72 1
i111 1
i129 1
i144 1
i159 1
i183 1
i191 1
+ j140 j147 j149 j150 j152 j153 j154 j156 j158
i14 1
i35 1
i48 1
i83 1
i98 1
i117 1
i158 1
i174 1
i194 1
+ j161 j162 j163 j164 j166 j170 j172 j174 j175
i5 1
i32 1
i42 1
i61 1
i69 1
i103 1
i143 1
i145 1
i158 1
i192 1
i198 1
+ j176 j178 j179 j180 j182 j183 j184 j188 j191
i6 1
i13 1
i23 1
i47 1
i61 1
i81 1
i93 1
i103 1
i125 1
i182 1
i193 1
+ j192 j193 j196
i73 1
i120 1
i138 1
i167 1
我认为我们已经驳斥了您关于 MIP 模型不是解决此问题的可行方法的说法。
请注意，宇宙年龄为137亿年或4.3e17秒。所以我们已经实现了大约 1e17 的加速。这是我的记录。
请注意，此模型不会找到商店的最佳位置，而只会找到一种配置，该配置可以最大限度地减少为所有客户提供服务所需的商店数量。从这个意义上说，它是最佳的。但该解决方案不会缩短客户与商店之间的距离。