Packages
fixpoint
0.9.1
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/stable_marriage.ex
defmodule CPSolver.Examples.StableMarriage do
@doc """
Stable marriage problem.
https://en.wikipedia.org/wiki/Stable_marriage_problem.
"""
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Model
alias CPSolver.Constraint.{ElementVar, Less}
alias CPSolver.Constraint.Factory, as: ConstraintFactory
alias CPSolver.Constraint.AllDifferent.DC, as: AllDifferent
def instances() do
%{
van_hentenryck: %{
rankWomen: [
[1, 2, 4, 3, 5],
[3, 5, 1, 2, 4],
[5, 4, 2, 1, 3],
[1, 3, 5, 4, 2],
[4, 2, 3, 5, 1]
],
rankMen: [
[5, 1, 2, 4, 3],
[4, 1, 3, 2, 5],
[5, 3, 2, 4, 1],
[1, 5, 4, 3, 2],
[4, 3, 2, 1, 5]
]
},
# http://mathworld.wolfram.com/StableMarriageProblem.html
mathworld: %{
rankWomen: [
[3, 1, 5, 2, 8, 7, 6, 9, 4],
[9, 4, 8, 1, 7, 6, 3, 2, 5],
[3, 1, 8, 9, 5, 4, 2, 6, 7],
[8, 7, 5, 3, 2, 6, 4, 9, 1],
[6, 9, 2, 5, 1, 4, 7, 3, 8],
[2, 4, 5, 1, 6, 8, 3, 9, 7],
[9, 3, 8, 2, 7, 5, 4, 6, 1],
[6, 3, 2, 1, 8, 4, 5, 9, 7],
[8, 2, 6, 4, 9, 1, 3, 7, 5]
],
rankMen: [
[7, 3, 8, 9, 6, 4, 2, 1, 5],
[5, 4, 8, 3, 1, 2, 6, 7, 9],
[4, 8, 3, 9, 7, 5, 6, 1, 2],
[9, 7, 4, 2, 5, 8, 3, 1, 6],
[2, 6, 4, 9, 8, 7, 5, 1, 3],
[2, 7, 8, 6, 5, 3, 4, 1, 9],
[1, 6, 2, 3, 8, 5, 4, 9, 7],
[5, 6, 9, 1, 2, 8, 4, 3, 7],
[6, 1, 4, 7, 5, 8, 3, 9, 2]
]
},
problem3: %{
rankWomen: [
[1, 2, 3, 4],
[4, 3, 2, 1],
[1, 2, 3, 4],
[3, 4, 1, 2]
],
rankMen: [
[1, 2, 3, 4],
[2, 1, 3, 4],
[1, 4, 3, 2],
[4, 3, 1, 2]
]
},
problem4: %{
rankWomen:
[[1, 5, 4, 6, 2, 3], [4, 1, 5, 2, 6, 3], [6, 4, 2, 1, 5, 3], [1, 5, 2, 4, 3, 6],
[4, 2, 1, 5, 6, 3], [2, 6, 3, 5, 1, 4]],
rankMen:
[[1, 4, 2, 5, 6, 3], [3, 4, 6, 1, 5, 2], [1, 6, 4, 2, 3, 5], [6, 5, 3, 4, 2, 1],
[3, 1, 2, 4, 5, 6], [2, 3, 1, 6, 5, 4]]
}
}
end
def solve(instance, opts \\ []) do
{:ok, res} = CPSolver.solve(model(instance), opts)
res.solutions
|> Enum.each(fn solution ->
Enum.zip(res.variables, solution)
|> print(instance_dimension(instances()|>
Map.get(instance)))
end)
{:ok, res}
end
def model(instance) do
data = Map.get(instances(), instance)
dim = instance_dimension(data)
range = 0..dim-1
wife = Enum.map(range, fn i -> Variable.new(range, name: "wife#{i+1}") end)
husband = Enum.map(range, fn i -> Variable.new(range, name: "husband#{i+1}") end)
## Bijection (1-to-1) husband <-> wife
bijections = for h <- range do
#husband[wife[m]] = m
ElementVar.new(husband, Enum.at(wife, h), h)
end ++
for w <- range do
#[wife[husband[m]] = m
ElementVar.new(wife, Enum.at(husband, w), w)
end
pref_constraints = for w <- range, h <- range, reduce: [] do
constraints_acc ->
rankMen_h = Map.get(data, :rankMen) |> Enum.at(h)
rankMen_h_w = rankMen_h |> Enum.at(w)
{rankMen_h_w_var, elementRankMen} = ConstraintFactory.element(rankMen_h, Enum.at(wife, h))
rankWomen_w = Map.get(data, :rankWomen) |> Enum.at(w)
rankWomen_w_h = rankWomen_w |> Enum.at(h)
{rankWomen_w_h_var, elementRankWomen} = ConstraintFactory.element(rankWomen_w, Enum.at(husband,w))
impl_submodel = ConstraintFactory.impl(
Less.new([rankMen_h_w, rankMen_h_w_var]),
Less.new([rankWomen_w_h_var, rankWomen_w_h]))
constraints_acc ++
impl_submodel.constraints ++
[elementRankMen, elementRankWomen]
end
|> List.flatten
Model.new(wife ++ husband,
bijections ++ pref_constraints ++ [AllDifferent.new(husband), AllDifferent.new(wife)] )
end
defp instance_dimension(data) do
Map.get(data, :rankWomen) |> length
end
def print(solution, n) do
IO.puts("\n")
solution
|> Enum.take(n)
|> Enum.with_index(0)
|> Enum.each(fn {{_wife_name, h}, w} -> IO.puts("\u2640:#{w+1} #{IO.ANSI.red}\u26ad#{IO.ANSI.reset} #{h+1}:\u2642") end)
end
@doc """
Pseudocode for checking stability
(https://stackoverflow.com/questions/58439880/algorithm-to-verify-stable-matching)
for w in women:
for m in [men w would prefer over current_partner(w)]:
if m prefers w to current_partner(m) return false
return true
"""
def check_solution(solution, instance) do
data = instances()[instance]
women_prefs = Map.get(data, :rankWomen)
men_prefs = Map.get(data, :rankMen)
n = instance_dimension(data)
{women_assignments, men_assignments} = Enum.take(solution, 2*n) |> Enum.split(n)
men_lookup = Enum.with_index(men_assignments, 0) |> Map.new(fn {partner, idx} -> {idx, partner} end)
women_assignments
|> Enum.with_index(0)
|> Enum.take(1)
|> Enum.all?(fn {current_partner, w} ->
w_prefs = Enum.at(women_prefs, w) |> Enum.map(fn p -> p - 1 end)
current_partner_rank = Enum.find_index(w_prefs, fn p -> p == current_partner end)
## Walk over candidates with higher ranks.
## If any of candidates prefers w over his current partner, stability doesn't hold
Enum.take(w_prefs, current_partner_rank)
|> Enum.all?(fn candidate ->
candidate_prefs = Enum.at(men_prefs, candidate) |> Enum.map(fn p -> p - 1 end)
candidate_current_partner = Map.get(men_lookup, candidate)
candidate_current_partner_rank = Enum.find_index(candidate_prefs, fn p -> p == candidate_current_partner end)
candidate_w_rank = Enum.find_index(candidate_prefs, fn p -> p == w end)
## Candidate prefers current partner to w
candidate_w_rank < candidate_current_partner_rank
end)
end)
end
end