如何使用 Pulp 解决网络流量问题？

Question

考虑以下网络流量模型并假设有 1000 名司机，我们如何通过分配使用每条可能路线的司机数量来计算模型的社会最优值。

我知道这个问题可以通过使用 Pulp 的线性规划来解决。但是，我的代码已损坏。

from pulp import *

prob = LpProblem("Network",LpMinimize)
a = LpVariable('A',lowBound=0,upBound=None,cat=LpInteger)
b = LpVariable('B',lowBound=0,upBound=None,cat=LpInteger)
c = LpVariable('C',lowBound=0,upBound=None,cat=LpInteger)

# objective function
prob +=  a * (((a+b)/100) + 20 + 5) + b * (((a+b)/100) + 10 + ((b+c)/100)) + c * (10 + 20 + ((b+c)/100))

#constraints
prob += a + b + c == 1000

prob.solve()

print("Status: ", LpStatus[prob.status])
for v in prob.variables():
    print(v.name,'=',v.varValue)

错误：

TypeError: Non-constant expressions cannot be multiplied

解法：
ABCF = 201
ABEF = 798
ADEF = 1

Answer 1

删除非线性项的一个选项是用二元决策变量替换非线性成本弧上的整数决策变量，用于沿着该弧的每个可能数量的驱动程序（将严重扩展 - 但没有问题对于这个小问题）。

下面给出了示例代码。请注意，此 returns 的解决方案与您在问题中给出的解决方案不同（我得到 ABCF=250、ABEF=750），我将此解决方案的 objective 值设为29375 VS 你引用的价格略高于 29399 - 除非我误解了？...

from pulp import *

prob = LpProblem("Network",LpMinimize)

nodes = ['A', 'B', 'C', 'D', 'E', 'F']

arc_costs = [[('A', 'D'), 10],
             [('B', 'C'), 20],
             [('B', 'E'), 10],
             [('D', 'E'), 20],
             [('C', 'F'), 5]]

ab_cost = LpVariable('ab_cost', lowBound=0, upBound=None, cat=LpContinuous)
ef_cost = LpVariable('ef_cost', lowBound=0, upBound=None, cat=LpContinuous)

# Binary variable == 1 iff number of drivers along arc = index value
ab_flow = LpVariable.dicts('ab_flow', range(1001), cat=LpBinary)
ef_flow = LpVariable.dicts('ef_flow', range(1001), cat=LpBinary)

# Variables to contain the selected Number of drivers
ab_flow_val = LpVariable('ab_flow_val', lowBound=0, upBound=None, cat=LpContinuous)
ef_flow_val = LpVariable('ef_flow_val', lowBound=0, upBound=None, cat=LpContinuous)


arc_flow_val = LpVariable.dicts('arc_flow_val', [i[0] for i in arc_costs],
                             lowBound=0, upBound=None, cat=LpInteger)

# objective function
prob +=  lpSum([arc_flow_val[i]*j for i, j in arc_costs] + ab_cost + ef_cost)

#constraints

# costs for the non-linear costed arcs:
prob += ab_cost == lpSum([ab_flow[x]*((x**2)/100) for x in range(1001)])
prob += ef_cost == lpSum([ef_flow[x]*((x**2)/100) for x in range(1001)])

# only one of binary variables can be true for each of the non-linear arcs
prob += lpSum([ab_flow[i] for i in range(1001)]) == 1
prob += lpSum([ef_flow[i] for i in range(1001)]) == 1

# set flow values from the binary variables:
prob += ab_flow_val == lpSum([ab_flow[i]*i for i in range(1001)])
prob += ef_flow_val == lpSum([ef_flow[i]*i for i in range(1001)])

# 1000 must leave and 1000 must arrive
prob += ab_flow_val + arc_flow_val[('A', 'D')] == 1000
prob += arc_flow_val[('C', 'F')] + ef_flow_val == 1000

# Non terminal nodes must have flow balance
for n in nodes[1:-1]:
    if n == 'B':
        prob += ab_flow_val == arc_flow_val[('B', 'C')] + arc_flow_val[('B', 'E')]
    elif n == 'E':
        prob +=  arc_flow_val[('B', 'E')] + arc_flow_val[('D', 'E')] == ef_flow_val
    else:
        # flow into node == flow out of node
        prob += lpSum([arc_flow_val[i] for i in arc_flow_val.keys() if i[0] == n]) == lpSum([arc_flow_val[j] for j in arc_flow_val.keys() if j[1] == n])

prob.solve()

print("Status: ", LpStatus[prob.status])
for v in prob.variables():
    if ('_val' in v.name) or ('cost' in v.name):
        print(v.name,'=',v.varValue)

如何使用 Pulp 解决网络流量问题？

How to solve a Network Traffic Problem using Pulp?

python

game-theory

pulp