Btukfyl

I am trying to use MIP using pulp package to connect islands together or to a terminal. The desired solution is to find the minimum distances in the system.

The results of the MIP code below shows the minimum distance is to connect all islands to the terminal although the distances between the islands to the terminal is clearly high. The code should has connected some islands together.

What am I doing wrong ? Appreciate your support.

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

There are several issues with your code:

• you use for island in range(len(islands)) to add a constraint of 3 edges used, but never use island so not sure why you are doing that loop instead of just adding the constraint.


• You have no relation between x and p, l so as you are only minimizing relating to x, x values are all 0 because there are no constraints on it.


• I don´t see the need at all for p and l when you already have x to model if the edges are used or not.

All in all, here is what I would do:

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