This notebook demostrates using JuMP to solve PuzzlOR's July-15 campsite selection problem using linear programming for constraint satisfaction.


In [1]:
using GLPKMathProgInterface # Loading the GLPK module for using its solver
using JuMP

In [2]:
# Define Data


Water = [0	0	0	1	0	0	0	0	;
        0	0	0	0	0	0	0	0	;
        0	0	0	0	0	0	0	0	;
        0	1	1	0	0	0	1	0	;
        0	0	0	1	0	0	0	0	;
        1	0	0	0	1	0	1	0	;
        0	0	0	1	1	1	0	0	;
        0	0	0	0	0	0	0	0	]

Wood= [0	0	0	0	0	0	0	1	;
        1	0	0	0	0	0	0	0	;
        0	0	0	0	0	0	0	0	;
        0	0	0	0	1	0	0	0	;
        0	0	1	0	0	0	0	1	;
        0	0	0	0	0	0	1	1	;
        0	0	0	0	0	0	0	0	;
        0	0	0	0	0	0	0	0	]

Swamp = [0	0	0	0	0	0	1	0	;
        0	0	0	1	0	0	0	0	;
        1	0	0	0	0	0	0	0	;
        1	0	1	0	0	0	0	0	;
        0	0	0	0	0	0	1	0	;
        0	0	0	0	0	0	0	1	;
        0	0	0	1	0	1	0	0	;
        0	1	0	0	0	0	0	0	]


Mosquitos = [0	0	1	0	0	0	0	0;
            0	0	0	0	0	0	0	0;
            1	0	0	0	0	0	0	1;
            0	0	1	0	0	0	0	0;
            0	0	0	0	0	0	0	0;
            1	0	0	0	0	0	1	0;
            0	1	0	0	0	0	0	0;
            0	0	0	0	0	0	1	0]


Out[2]:
8x8 Array{Int64,2}:
 0  0  1  0  0  0  0  0
 0  0  0  0  0  0  0  0
 1  0  0  0  0  0  0  1
 0  0  1  0  0  0  0  0
 0  0  0  0  0  0  0  0
 1  0  0  0  0  0  1  0
 0  1  0  0  0  0  0  0
 0  0  0  0  0  0  1  0

In [3]:
elements = ["Water","Wood","Swamp", "Mosquitos"]


Out[3]:
4-element Array{ASCIIString,1}:
 "Water"    
 "Wood"     
 "Swamp"    
 "Mosquitos"

In [4]:
CostAt = ["Water"=> 3, "Wood"=> 2,  "Swamp" => -2 , "Mosquitos"=>-3]


Out[4]:
Dict{ASCIIString,Int64} with 4 entries:
  "Water"     => 3
  "Swamp"     => -2
  "Wood"      => 2
  "Mosquitos" => -3

In [7]:
CostNear = ["Water"=> 1, "Wood"=> 1, "Swamp" => -1,"Mosquitos"=>-2, ]


Out[7]:
Dict{ASCIIString,Int64} with 4 entries:
  "Water"     => 1
  "Swamp"     => -1
  "Wood"      => 1
  "Mosquitos" => -2

In [9]:
#MODEL CONSTRUCTION
#--------------------
m = Model(solver=GLPKSolverLP()) 


#define initial variables
@defVar(m, quality[elements,1:8,1:8] )

@defVar(m, score[1:8,1:8] )


Out[9]:
$$ score_{i,j} free \quad\forall i \in \{1,2,\dots,7,8\}, j \in \{1,2,\dots,7,8\} $$

In [11]:
#define quality constraint
for i = 1:8
    for j = 1:8
        for ki in [0,1, -1]
            for kj in [0,1,-1]
                if i + ki >= 1 && i + ki <= 8 && j + kj >= 1 && j+kj <= 8
                    for e in elements
                        if kj == 0 && ki == 0
                            if e == "Water"
                                @addConstraint(m, quality[e,i,j] >= Water[i + ki, j + kj] * CostAt["Water"]) 
                            elseif e == "Wood"
                                @addConstraint(m, quality[e,i,j] >= Wood[i + ki, j + kj] * CostAt["Wood"])
                            elseif e == "Swamp"
                                @addConstraint(m, quality[e,i,j] <= Swamp[i + ki, j + kj] * CostAt["Swamp"])
                            elseif e == "Mosquitos"
                                @addConstraint(m, quality[e,i,j] <= Mosquitos[i + ki, j + kj] * CostAt["Mosquitos"])
                            end
                        else
                            if e == "Water"
                                @addConstraint(m, quality[e,i,j] >= Water[i + ki, j + kj] * CostNear["Water"]) 
                            elseif e == "Wood"
                                @addConstraint(m, quality[e,i,j] >= Wood[i + ki, j + kj] * CostNear["Wood"])
                            elseif e == "Swamp"
                                @addConstraint(m, quality[e,i,j] <= Swamp[i + ki, j + kj] * CostNear["Swamp"])
                            elseif e == "Mosquitos"
                                @addConstraint(m, quality[e,i,j] <= Mosquitos[i + ki, j + kj] * CostNear["Mosquitos"])
                            end
                        end
                    end
                end
            end
        end
    end
end

In [12]:
for i in 1:8
    for j in 1:8
        @addConstraint(m, score[i,j] ==  sum{quality[e,i,j] , e in ["Water","Wood"]} 
                                          -sum{quality[e,i,j] , e in ["Swamp","Mosquitos"]}
        )

    end
end

In [13]:
#define objective
@setObjective(m, Min, sum{score[i,j], i=1:8, j=1:8})


Out[13]:
$$ score_{1,1} + score_{1,2} + score_{1,3} + score_{1,4} + score_{1,5} + score_{1,6} + score_{1,7} + score_{1,8} + score_{2,1} + score_{2,2} + score_{2,3} + score_{2,4} + score_{2,5} + score_{2,6} + score_{2,7} + score_{2,8} + score_{3,1} + score_{3,2} + score_{3,3} + score_{3,4} + score_{3,5} + score_{3,6} + score_{3,7} + score_{3,8} + score_{4,1} + score_{4,2} + score_{4,3} + score_{4,4} + score_{4,5} + score_{4,6} + score_{4,7} + score_{4,8} + score_{5,1} + score_{5,2} + score_{5,3} + score_{5,4} + score_{5,5} + score_{5,6} + score_{5,7} + score_{5,8} + score_{6,1} + score_{6,2} + score_{6,3} + score_{6,4} + score_{6,5} + score_{6,6} + score_{6,7} + score_{6,8} + score_{7,1} + score_{7,2} + score_{7,3} + score_{7,4} + score_{7,5} + score_{7,6} + score_{7,7} + score_{7,8} + score_{8,1} + score_{8,2} + score_{8,3} + score_{8,4} + score_{8,5} + score_{8,6} + score_{8,7} + score_{8,8} $$

In [14]:
#print(m)

In [15]:
#print(m)

status = solve(m)


Out[15]:
:Optimal

In [16]:
max_x = 1
max_y = 1
maxval = 0
sumquality = zeros(8,8)
for i in 1:8
    for j in 1:8

        for e in elements
            sumquality[i,j] += getValue(quality[e,i,j])
        end
        print(sumquality[i,j])
        print("\t")
        if maxval <= sumquality[i,j]
            max_x = i
            max_y = j
            maxval = sumquality[i,j]
        end
    end
    println()
end

print("best campsite is at $(max_x), $(max_y)")


1.0	-1.0	-3.0	0.0	0.0	-1.0	-1.0	1.0	
-1.0	-2.0	-2.0	-3.0	0.0	-1.0	-2.0	-2.0	
-3.0	-1.0	-2.0	-1.0	0.0	2.0	-1.0	-2.0	
-3.0	1.0	-1.0	-1.0	3.0	1.0	1.0	-1.0	
-2.0	-1.0	0.0	1.0	2.0	-1.0	-2.0	0.0	
0.0	0.0	-1.0	1.0	2.0	-1.0	1.0	-1.0	
-2.0	-3.0	-2.0	1.0	2.0	0.0	-1.0	-1.0	
-3.0	-4.0	-2.0	0.0	0.0	-2.0	-3.0	-2.0	
best campsite is at 4, 5

In [27]:


In [ ]: