Packages
fixpoint
0.8.42
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
test/objective/objective_test.exs
defmodule CpSolverTest.Objective do
use ExUnit.Case
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Model
alias CPSolver.Objective
alias CPSolver.Propagator
alias CPSolver.Variable.Interface
import CPSolver.Test.Helpers
describe "Objective API" do
test "low-level operations" do
handle = Objective.init_bound_handle()
Objective.update_bound(handle, 100)
assert 100 == Objective.get_bound(handle)
## Updates the bound with the lower value
Objective.update_bound(handle, 10)
assert 10 == Objective.get_bound(handle)
## Doesn't update the bound with the higher value
Objective.update_bound(handle, 100)
assert 10 == Objective.get_bound(handle)
end
test "concurrent updates to the bound result in setting the lowest bound value" do
handle = Objective.init_bound_handle()
refute 1 == Objective.get_bound(handle)
num_updates = 1000
bounds = Enum.shuffle(1..num_updates)
results =
Task.async_stream(bounds, fn b ->
Objective.update_bound(handle, b)
end)
|> Enum.to_list()
assert num_updates == length(results)
assert 1 == Objective.get_bound(handle)
end
test "Propagation and tightening" do
{:ok, [objective_variable], _store} =
create_store([Variable.new(1..10)])
min_objective =
%{propagator: min_propagator, bound_handle: min_handle} =
Objective.minimize(objective_variable)
assert %{changes: nil, active?: true, state: nil} ==
Propagator.filter(min_propagator)
## Tighten the bound (this will set the bound to objective_variable.max() - 1)
Objective.tighten(min_objective)
assert Objective.get_bound(min_handle) == 9
## Propagation will result in :max_change, :fixed, or :fail for the objective variable, if the global bound changes
assert %{
changes: %{Interface.id(objective_variable) => :max_change},
active?: true,
state: nil
} ==
Propagator.filter(min_propagator)
## Propagation doesn't change a global bound
assert Objective.get_bound(min_handle) == 9
Objective.update_bound(min_handle, Interface.min(objective_variable))
assert %{changes: %{Interface.id(objective_variable) => :fixed}, active?: true, state: nil} ==
Propagator.filter(min_propagator)
## Tightening bound when the objective variable is fixed
Objective.tighten(min_objective)
assert :fail == Propagator.filter(min_propagator)
end
end
describe "Objectives in solutions" do
alias CPSolver.Constraint.{LessOrEqual, Sum}
alias CPSolver.Examples.Knapsack
test "sanity test for minimization and maximization" do
sum_bound = 1000
x_bound = 100
y_bound = 200
x = Variable.new(1..x_bound, name: "x")
y = Variable.new(1..y_bound, name: "y")
z = Variable.new(1..sum_bound)
variables = [x, y]
constraints = [LessOrEqual.new(x, y), Sum.new(z, [x, y])]
minimization_model =
Model.new(
variables,
constraints,
objective: Objective.minimize(z)
)
maximization_model =
Model.new(
variables,
constraints,
objective: Objective.maximize(z)
)
{:ok, min_res} = CPSolver.solve_sync(minimization_model)
assert min_res.objective == 2
assert List.last(min_res.solutions) == [1, 1, 2]
{:ok, max_res} = CPSolver.solve_sync(maximization_model)
assert max_res.objective == min(sum_bound, x_bound + y_bound)
[x_val, y_val, sum_bound] = List.last(max_res.solutions)
assert x_val + y_val == sum_bound
end
test "The best solution with respect to optimization criterion will be the last in the list" do
## We use a small knapsack instance that is known to emit 2 solutions
model_instance = "data/knapsack/ks_4_0"
## Value maximization model
value_knapsack_model = Knapsack.model(model_instance, :value_maximization)
{:ok, value_res} = CPSolver.solve_sync(value_knapsack_model)
total_value_idx = Enum.find_index(value_res.variables, fn name -> name == "total_value" end)
assert List.last(value_res.solutions) |> Enum.at(total_value_idx) == value_res.objective
## Free space minimization model
space_minimization_model =
Knapsack.model(model_instance, :free_space_minimization)
{:ok, space_res} = CPSolver.solve_sync(space_minimization_model)
total_value_idx =
Enum.find_index(space_res.variables, fn name -> name == "total_weight" end)
## Note: the solution contains variable values, but not the objective (view) values.
## Thus for the purpose of asserting that the fixed value for the objective variable
## corresponds to the objective value, we will map one onto another.
assert List.last(space_res.solutions) |> Enum.at(total_value_idx) ==
Interface.map(space_minimization_model.objective.variable, space_res.objective)
end
end
end