PuLP：如何构造这个工厂覆盖问题

Question

努力为 PuLP 中的以下 MIP 场景制定 objective 函数。

Each city is populated by N number of people.
Each factory location can facilitate a set of cities.
Minimize the number factories to open, such that the number of people facilitated is >= 4000

我的主要问题是不同的工厂可以为同一个城市提供服务。所以把每个工厂的可服务人口population加起来单独考虑是不公平的。

cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Vienna', 'Prague']
factories = ['A', 'B', 'C', 'D']

city_populations = {'London': 898, 'Paris': 222, 'Berlin': 767, 'Amsterdam': 111, 'Vienna': 854, 'Prague': 908}

factories_service = {'A': ['London', 'Prague'], 'B': ['London', 'Paris', 'Vienna'], 'C': ['Amsterdam', 'Vienna', 'Prague'], 'D': ['London', 'Vienna', 'Prague']}

这是我目前拥有的，但它不正确，因为它只选择了最大的城市，没有考虑人口重叠。

prob = pl.LpProblem("Factory Coverage",pl.LpMinimize)

decision_vars = pl.LpVariable.dicts("Factories", factories, cat='Binary')

prob += pl.lpSum(decision_vars)
prob += pl.lpSum([sum([city_populations[x] for x in factories_service[i]])*decision_vars[i] for i in factories]) >= 4000


prob.solve()

输出：
Factories_A, 0.0
Factories_B, 1.0
Factories_C, 0.0
Factories_D, 1.0

Answer 1

主要问题是你重复计算了人口。如果两个工厂为同一个城市服务，并且都被建造，那么该城市的人口应该只被计算为服务一次。

您可以通过为城市创建另一组二进制变量来完成此操作，以指示该城市是否提供服务。然后添加逻辑，确定只有在有工厂为城市提供服务时才为城市提供服务。

您遇到的另一个小问题是自 sum(city_populations.values()) == 3760

以来您的整个模型中没有 4000 名公民

尽管这不是最有效的实施方式，但这是您如何解决此问题的示例：

prob = pl.LpProblem("Factory Coverage",pl.LpMinimize)

factories_vars = pl.LpVariable.dicts("Factories", factories, cat='Binary')
cities_vars = pl.LpVariable.dicts("Cities", cities, cat='Binary')

# Objective function
prob += pl.lpSum(factories_vars)
# Population served is greater than 4000
prob += pl.lpSum([city_populations[c]*cities_vars[c] for c in cities]) >= 2000
# City is served only if there is a factory that serves it
bigM = len(factories)
for c in cities:
    prob +=  bigM * cities_vars[c] >= pl.lpSum([factories_vars[f] for f in factories_vars if c in factories_service[f]])
    prob +=  cities_vars[c] <= pl.lpSum([factories_vars[f] for f in factories_vars if c in factories_service[f]])

prob.solve()

结果：

for f in factories_vars:
    print(f, factories_vars[f].value())
for c in cities_vars:
    print(c, cities_vars[c].value())

A 0.0
B 0.0
C 0.0
D 1.0
London 1.0
Paris 0.0
Berlin 0.0
Amsterdam 0.0
Vienna 1.0
Prague 1.0

PuLP：如何构造这个工厂覆盖问题

PuLP: How to structure this factory coverage problem

python

mathematical-optimization

python-3.x

pulp

mixed-integer-programming