Sunday, April 16, 2017

Puzzlor | Any Port | Julia/JuMP

AnyPortInAStorm

Puzzlor: Any Port In A Storm

Solution using Julia / JuMP

http://puzzlor.com/2017-02_PortInAStorm.html

In [1]:
using JuMP

m = Model()

@variable(m, Boat2Dock[i=1:20,j=1:20], Bin)
Out[1]:
$$ Boat2Dock_{i,j} \in \{0,1\} \quad\forall i \in \{1,2,\dots,19,20\}, j \in \{1,2,\dots,19,20\} $$
In [2]:
# Distance Data
Distances = [1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             1 1 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2;
             2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1;
             3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1]
Out[2]:
20x20 Array{Int64,2}:
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 1  1  1  1  3  3  3  3  3  3  3  2  2  2  2  2  2  2  2  2
 2  2  2  2  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 2  2  2  2  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 2  2  2  2  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 2  2  2  2  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 2  2  2  2  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
 3  3  3  3  2  2  2  2  2  2  2  1  1  1  1  1  1  1  1  1
In [3]:
# set the Objective Function : Min Total Distance
@objective(m,Min,sum{Boat2Dock[i,j]*Distances[i,j], i=1:20, j=1:20})

# Each Boat can only occupy one Dock space
for i = 1:20
    @constraint(m, sum{Boat2Dock[i,j],j=1:20}==1)
end

# Each Dock space contains only one Boat
for j = 1:20
    @constraint(m, sum{Boat2Dock[i,j],i=1:20}==1)
end
In [4]:
status = solve(m)
#print(m)

# Print the solution
println("Objective is: ",m.objVal)
println("\nSolution:")
   
for r = 1:20, i = 1:20
    x = getvalue(Boat2Dock[r,i])
    if x > 0 
        println(" boat ", r, " to dock space ", i, " distance ", Distances[r,i])
    end
end

Objective is: 31.0

Solution:
 boat 1 to dock space 2 distance 1
 boat 2 to dock space 1 distance 1
 boat 3 to dock space 3 distance 1
 boat 4 to dock space 16 distance 2
 boat 5 to dock space 5 distance 3
 boat 6 to dock space 11 distance 3
 boat 7 to dock space 4 distance 1
 boat 8 to dock space 12 distance 2
 boat 9 to dock space 14 distance 1
 boat 10 to dock space 17 distance 1
 boat 11 to dock space 10 distance 2
 boat 12 to dock space 19 distance 1
 boat 13 to dock space 7 distance 2
 boat 14 to dock space 20 distance 1
 boat 15 to dock space 6 distance 2
 boat 16 to dock space 15 distance 1
 boat 17 to dock space 8 distance 2
 boat 18 to dock space 18 distance 1
 boat 19 to dock space 13 distance 1
 boat 20 to dock space 9 distance 2
Posted by at