Packages
fixpoint
0.19.5
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/examples/hakank/set_covering_deployment.ex
#
# Set covering deployment in Elixir.
#
# From http://mathworld.wolfram.com/SetCoveringDeployment.html
# """
# Set covering deployment (sometimes written "set-covering deployment"
# and abbreviated SCDP for "set covering deployment problem") seeks
# an optimal stationing of troops in a set of regions so that a
# relatively small number of troop units can control a large
# geographic region. ReVelle and Rosing (2000) first described
# this in a study of Emperor Constantine the Great's mobile field
# army placements to secure the Roman Empire.
# """
#
# Cf http://hakank.org/minizinc/set_covering_deployment.mzn
#
# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
## Boris Okner: modified to sync with the latest API,
## change naming and result handling.
##
defmodule CPSolver.Examples.Hakank.SetCoveringDeployment do
import Hakank.CPUtils
alias CPSolver.IntVariable
# alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
# alias CPSolver.Constraint.Sum
alias CPSolver.Constraint.LessOrEqual
# alias CPSolver.Constraint.Circuit
# alias CPSolver.Constraint.Element
# alias CPSolver.Constraint.NotEqual
# alias CPSolver.Constraint.Equal
alias CPSolver.Model
alias CPSolver.Objective
# Defines:
# add/2-3,element/2-3,element2d/3-4,mod/2-3,
# subtract/2-3,sum/1-2
# (Note: add/2 is also defined in CPSolver.Variable.View.Factory)
import CPSolver.Constraint.Factory
# Defines: add/2,linear/3,minus/1,mul/2
# (Note: add/2 is also defined in CPSolver.Constraint.Factory)
# import CPSolver.Variable.View.Factory
# The connection matrix
def problem(1) do
[[0, 1, 0, 1, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 1, 1],
[1, 0, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0]]
end
def run() do
mat = problem(1)
n = length(mat)
# First army
xs = for i <- 0..n-1 do IntVariable.new(0..1, name: "xs[#{i}]") end
# Second army
ys = for i <- 0..n-1 do IntVariable.new(0..1, name: "ys[#{i}]") end
#
# Constraint 1: There is always an army in a city (+ maybe a backup)
# Or rather: Is there a backup, there must be an
# an army
#
constraint1 = for {x,y} <- Enum.zip(xs,ys), do: LessOrEqual.new(y,x)
#
# Constraint 2: There should always be an backup army near
# every city
#
constraint2 = for {x,row} <- Enum.zip(xs,mat) do
{s_var, s_cons} = sum(for {m,y} <- Enum.zip(row,ys) do CPSolver.Variable.View.Factory.mul(y,m) end)
{add_var,add_cons} = add(x,s_var)
leq_cons = LessOrEqual.new(1,add_var)
[s_cons,leq_cons,add_cons]
end
|> List.flatten
# Thanks to Boris Okner for this neat solution.
all_armies = xs ++ ys
# objective: minimize the number of armies
{sum_var, sum_constraint} = sum(all_armies)
model = Model.new(all_armies,
[sum_constraint | (constraint1 ++ constraint2) |> List.flatten ],
objective: Objective.minimize(sum_var)
)
Logger.configure(level: :info)
opts = [
search: {:first_fail, :indomain_min},
# search: {:input_order, :indomain_min},
# search: {:first_fail, :indomain_random},
space_threads: 12,
timeout: :infinity,
# stop_on: {:max_solutions, 2},
]
{:ok, res} = CPSolver.solve(model,
opts
)
IO.inspect(res.statistics)
sol = res.solutions |> hd
# IO.inspect(sol, label: "sol")
# x_val = Enum.slice(sol,0,n)
# y_val = Enum.slice(sol,n,n)
# z_val = Enum.at(sol,n*2)
# IO.inspect(x_val, label: "x")
# IO.inspect(y_val, label: "y")
# IO.inspect(z_val, label: "z")
IO.inspect(res.objective, label: "objective")
xs_val = for i <- 0..n-1, do: get_solution_value(res,sol,"xs[#{i}]")
ys_val = for i <- 0..n-1, do: get_solution_value(res,sol,"ys[#{i}]")
IO.inspect(xs_val, label: "x")
IO.inspect(ys_val, label: "y")
# res
end
end