Packages
fixpoint
0.20.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_covering3.ex
#
# Set covering problem in Elixir.
#
# Problem from
# Katta G. Murty: "Optimization Models for Decision Making", page 302f
# http://ioe.engin.umich.edu/people/fac/books/murty/opti_model/junior-7.pdf
#
# 10 senators making a committee, where there must at least be one
# representative from each group:
# group: senators:
# southern 1 2 3 4 5
# northern 6 7 8 9 10
# liberals 2 3 8 9 10
# conservative 1 5 6 7
# democrats 3 4 5 6 7 9
# republicans 1 2 8 10
#
# The objective is to minimize the number of senators.
# Solution:
# Found min_val:: 2
#
# Checking all optimal solutions:
# Choosen: [:b, :f]
# Choosen: [:e, :h]
# Choosen: [:a, :i]
# Choosen: [:b, :g]
# Choosen: [:e, :j]
#
#
# 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.SetCovering3 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 Belong matrix:
#
# 1 if a senator belongs to the group,
# 0 if senator don't belong to the group
#
def belongs() do
[[1, 1, 1, 1, 1, 0, 0, 0, 0, 0], # 1 southern
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1], # 2 northern
[0, 1, 1, 0, 0, 0, 0, 1, 1, 1], # 3 liberals
[1, 0, 0, 0, 1, 1, 1, 0, 0, 0], # 4 conservative
[0, 0, 1, 1, 1, 1, 1, 0, 1, 0], # 5 democrats
[1, 1, 0, 0, 0, 0, 0, 1, 0, 1]] # 6 republicans
end
def senators do
[:a,:b,:c,:d,:e,:f,:g,:h,:i,:j]
end
def run() do
belongs = belongs()
senators = senators()
min_val = set_covering3(belongs,senators)
IO.inspect(min_val, label: "Found min_val:")
IO.puts("\nChecking all optimal solutions:")
set_covering3(belongs,senators,min_val)
end
def set_covering3(belongs,senators, min_val \\ nil) do
num_groups = length(belongs)
num_senators = length(senators)
# Which senator to choose
x = for i <- 0..num_senators-1, do: IntVariable.new(0..1, name: "x[#{i}]")
z = IntVariable.new(0..num_senators, name: "z")
# cover all groups with the senators
group_constraints = for i <- 0..num_groups-1 do
{sum_var, sum_cons} = sum(for j <- 0..num_senators-1 do
mul(Enum.at(x,j), mat_at(belongs,i,j))
end)
leq = LessOrEqual.new(1,sum_var)
[sum_cons,leq]
end
z_cons = Sum.new(z,x)
all_vars = x ++ [z]
all_constraints = [z_cons | group_constraints] |> List.flatten
model = min_val != nil && Model.new(all_vars, [ Equal.new(z,min_val) | all_constraints] |> List.flatten )
|| Model.new(all_vars, all_constraints,
objective: Objective.minimize(z))
Logger.configure(level: :info)
opts = [
search: {:first_fail, :indomain_min},
# search: {:input_order, :indomain_min},
# search: {:first_fail, :indomain_random},
timeout: :infinity,
# stop_on: {:max_solutions, 2},
]
{:ok, res} = CPSolver.solve(model, opts)
for sol <- res.solutions do
choosen = Enum.with_index(sol)
|> Enum.take(num_senators)
|> Enum.filter(fn {s,_ix} -> s == 1 end)
|> Enum.map(fn {_s, ix} -> Enum.at(senators,ix) end)
if min_val != nil do
IO.inspect(choosen, label: "Choosen")
end
end
if min_val == nil do
res.objective
else
IO.inspect(res.statistics.solution_count, label: "Number of solutions:")
end
end
end