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

Could you more precisely describe your objective value and constraints? Is your question the same as https://stackoverflow.com/q/30555606/3093387 ? — josliber, Nov 25 '18 at 05:39
Hello, I saw your solution to the other island problem. I have a similar problem to that one posted in this link https://stackoverflow.com/questions/53440953/connect-islands-and-their-intersections-to-a-terminal-using-mip The connection is very similar with a few different assumptions. I need help to formulate proper constraints to make it work. I would appreciate if you can take a look given that you had a really great solution to the problem you shared. — M.Khaled, Nov 27 '18 at 00:36

score 1 · Accepted Answer · answered Nov 26 '18 at 15:19

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

Mixed Integer to connect islands together or to a terminal

1 Answers1