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 [ ]: