Mixed Integer to connect islands together or to a terminal

Question

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

Answer 1

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