将岛屿连接在一起或连接到终端的混合整数
Mixed Integer to connect islands together or to a terminal
我正在尝试使用使用纸浆包的 MIP 将岛连接在一起或连接到终端。所需的解决方案是找到系统中的最小距离。
下面 MIP 代码的结果显示最小距离是将所有岛屿连接到终端,尽管岛屿与终端之间的距离显然很高。该代码应该将一些岛屿连接在一起。
我做错了什么?感谢您的支持。
import itertools
import pulp
islands = {0: [(0, 0)], 1: [(0, 7)], 2: [(3, 3)]} ## islands id = 0,1,2 and their locations
terminal = {3: [(1,1)]} ## the terminal id = 3 and its location
distances = {(0,1): 1.0, (0,2): 2.0, (1,2): 3.0, (0,3): 33.0, (1,3): 34.0, (2,3): 23.0} ## distances of connecting islands together and islands to terminal
islandsPair = [(m, n) for m in islands for n in islands if m < n] ## islands pair
terminalPair = [(b, c) for b in islands for c in terminal] ## island-terminal pair
x = pulp.LpVariable.dicts("x", distances.keys(), lowBound=0, upBound=1)
p = pulp.LpVariable.dicts("p", islandsPair, lowBound=0, upBound=1)
l = pulp.LpVariable.dicts("l", terminalPair, lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)
# Objective
mod += sum([distances[k] * x[k] for k in distances])
## constraint that there has to be at least 3 connections in the system:
for island in range(len(islands)):
mod += sum(p[(m, n)] for m in islands for n in islands if m < n) + sum(l[(b, c)] for b in islands for c in terminal) >= 3
# Solve and output
mod.solve()
## printing the solutions:
print pulp.LpStatus[mod.status]
print '0,3',l[(0, 3)].value()
print '1,3',l[(1, 3)].value()
print '2,3',l[(2, 3)].value()
print '0,1',p[(0, 1)].value()
print '0,2',p[(0, 2)].value()
print '1,2',p[(1, 2)].value()
您的代码存在几个问题:
- 您使用
for island in range(len(islands))
添加了使用的 3 条边的约束,但从未使用岛,因此不确定为什么要执行该循环而不是仅添加约束。
- x 和 p,l 之间没有关系,所以你只是最小化与 x 的相关性,x 值全为 0,因为它没有约束。
- 当你已经有 x 来建模时,无论是否使用边缘,我都看不到 p 和 l 的必要性。
总而言之,我会这样做:
import itertools
import pulp
distances = {(0,1): 1.0, (0,2): 2.0, (1,2): 3.0, (0,3): 33.0, (1,3): 34.0, (2,3): 23.0} ## distances of connecting islands together and islands to terminal
x = pulp.LpVariable.dicts("x", distances.keys(), lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)
y = pulp.LpVariable("y", lowBound=0, upBound = sum(distances.values()))
y = sum([distances[k] * x[k] for k in distances])
# Objective
mod += y
## constraint that there has to be at least 3 connections in the system:
mod += sum(x[edge] for edge in distances) >= 3
# Solve and output
mod.solve()
## printing the solutions:
print (pulp.LpStatus[mod.status], y.value())
for edge in distances:
print (edge, x[edge].value())
我正在尝试使用使用纸浆包的 MIP 将岛连接在一起或连接到终端。所需的解决方案是找到系统中的最小距离。
下面 MIP 代码的结果显示最小距离是将所有岛屿连接到终端,尽管岛屿与终端之间的距离显然很高。该代码应该将一些岛屿连接在一起。
我做错了什么?感谢您的支持。
import itertools
import pulp
islands = {0: [(0, 0)], 1: [(0, 7)], 2: [(3, 3)]} ## islands id = 0,1,2 and their locations
terminal = {3: [(1,1)]} ## the terminal id = 3 and its location
distances = {(0,1): 1.0, (0,2): 2.0, (1,2): 3.0, (0,3): 33.0, (1,3): 34.0, (2,3): 23.0} ## distances of connecting islands together and islands to terminal
islandsPair = [(m, n) for m in islands for n in islands if m < n] ## islands pair
terminalPair = [(b, c) for b in islands for c in terminal] ## island-terminal pair
x = pulp.LpVariable.dicts("x", distances.keys(), lowBound=0, upBound=1)
p = pulp.LpVariable.dicts("p", islandsPair, lowBound=0, upBound=1)
l = pulp.LpVariable.dicts("l", terminalPair, lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)
# Objective
mod += sum([distances[k] * x[k] for k in distances])
## constraint that there has to be at least 3 connections in the system:
for island in range(len(islands)):
mod += sum(p[(m, n)] for m in islands for n in islands if m < n) + sum(l[(b, c)] for b in islands for c in terminal) >= 3
# Solve and output
mod.solve()
## printing the solutions:
print pulp.LpStatus[mod.status]
print '0,3',l[(0, 3)].value()
print '1,3',l[(1, 3)].value()
print '2,3',l[(2, 3)].value()
print '0,1',p[(0, 1)].value()
print '0,2',p[(0, 2)].value()
print '1,2',p[(1, 2)].value()
您的代码存在几个问题:
- 您使用
for island in range(len(islands))
添加了使用的 3 条边的约束,但从未使用岛,因此不确定为什么要执行该循环而不是仅添加约束。 - x 和 p,l 之间没有关系,所以你只是最小化与 x 的相关性,x 值全为 0,因为它没有约束。
- 当你已经有 x 来建模时,无论是否使用边缘,我都看不到 p 和 l 的必要性。
总而言之,我会这样做:
import itertools
import pulp
distances = {(0,1): 1.0, (0,2): 2.0, (1,2): 3.0, (0,3): 33.0, (1,3): 34.0, (2,3): 23.0} ## distances of connecting islands together and islands to terminal
x = pulp.LpVariable.dicts("x", distances.keys(), lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)
y = pulp.LpVariable("y", lowBound=0, upBound = sum(distances.values()))
y = sum([distances[k] * x[k] for k in distances])
# Objective
mod += y
## constraint that there has to be at least 3 connections in the system:
mod += sum(x[edge] for edge in distances) >= 3
# Solve and output
mod.solve()
## printing the solutions:
print (pulp.LpStatus[mod.status], y.value())
for edge in distances:
print (edge, x[edge].value())