Смешанное целое число для соединения островов вместе или с терминалом - PullRequest
Новая
       54

Смешанное целое число для соединения островов вместе или с терминалом

0 голосов
/ 25 ноября 2018

Я пытаюсь использовать 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()

1 Ответ

0 голосов
/ 26 ноября 2018

Есть несколько проблем с вашим кодом:

  • вы используете for island in range(len(islands)), чтобы добавить ограничение из 3 используемых ребер, но никогда не используйте остров, поэтому не уверены, почему вы делаете этот цикл, а не простодобавление ограничения.
  • Вы не имеете отношения между x и p, l, так как вы только минимизируете относящиеся к x, все значения x равны 0, потому что для него нет ограничений.
  • Iвообще не вижу необходимости в p и l, когда у вас уже есть x для моделирования, если используются ребра или нет.

В общем, вот что я бы сделал: 

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())
...