Closed matbesancon closed 4 years ago
To get a concrete example of the issue, see the following test set:
@testset "Weighted stable set" begin
matrix = [
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
]
model = CS.Optimizer()
x = [MOI.add_constrained_variable(model, MOI.ZeroOne()) for _ in 1:4]
for i in 1:4, j in 1:4
if matrix[i,j] == 1 && i < j
(z, _) = MOI.add_constrained_variable(model, MOI.GreaterThan(0.0))
MOI.add_constraint(model, z, MOI.Integer())
MOI.add_constraint(model, z, MOI.LessThan(1.0))
f = MOI.ScalarAffineFunction(
[
MOI.ScalarAffineTerm(1.0, x[i][1]),
MOI.ScalarAffineTerm(1.0, x[j][1]),
MOI.ScalarAffineTerm(1.0, z),
], 0.0
)
MOI.add_constraint(model, f, MOI.EqualTo(1.0))
# ConstraintSolver.add_constraint!(model, x[i] + x[j] <= 1)
end
end
# sum(w[i] * x[i] for i in V) - stable_set == 0
stable_set = MOI.add_variable(model)
MOI.add_constraint(model, stable_set, MOI.Integer())
MOI.add_constraint(model, stable_set, MOI.LessThan(4.0))
MOI.add_constraint(model, stable_set, MOI.GreaterThan(0.0))
weights = [0.2, 0.1, 0.2, 0.1]
terms = [MOI.ScalarAffineTerm(weights[i], x[i][1]) for i in eachindex(x)]
push!(terms, MOI.ScalarAffineTerm(-1.0, stable_set))
MOI.add_constraint(model,
MOI.ScalarAffineFunction(terms, 0.0),
MOI.EqualTo(0.0),
)
MOI.set(model, MOI.ObjectiveFunction{MOI.SingleVariable}(), MOI.SingleVariable(stable_set))
MOI.set(model, MOI.ObjectiveSense(), MOI.MAX_SENSE)
MOI.optimize!(model)
@test MOI.get(model, MOI.VariablePrimal(), x[4][1]) == 1
@test MOI.get(model, MOI.VariablePrimal(), x[1][1]) == 1
@test MOI.get(model, MOI.ObjectiveValue()) ≈ 3
end
This will fail on master because the code tries to convert a Float64
to Int
Thanks for the example. Will have a look tomorrow!
Okay I currently only support Integer coefficients but somehow thought I support real ones. The problem with real ones currently is rounding errors:
If I have 0.4x+0.1y+0.4z+0.1a - b == 0
and x
,y
and z
are fixed to 1
and a,b
are [0,1]
then the computed maximum value for 0.1a
is 0.0999
because computers :( and this is divided by 0.1 which is <1 and therefore we round down to 0 -> a
must be 0. Not sure how to deal about that... Which is probably the reason why I like DISCRETE solvers (with discrete coefficients...) :laughing:
Oh additionally I don't fully understand your example. With that weights and only binary x the only solution is x = [0,0,0,0]
isn't it?
@matbesancon can you have a look at your weights again? As far as I can see it the only possible solution is x = [0,0,0,0]
Which is probably the reason why I like DISCRETE solvers
it's still a discrete solver, plenty of purely discrete combinatorial problems include some real numbers :)
The equation with the weight is saying:
sum(x[i] * w[i]) - stable_set = 0
<=>
sum(x[i] * w[i]) = stable_set
I'm just doing this because the objective has to be a single variable
I had to use equalities here because:
Yes but with your weights of [0.2, 0.1, 0.2, 0.1]
and your @test
where 1 and 4 should be set to 1. The stable set would be 0.4
which is not discrete or am I missing something?
- inequalities are not supported, while they would often be numerically better
- affine functions are not supported as objective
It's all going to be implemented ;)
Oh right I see what you mean, that's correct my model does not follow my intent, we should not add a stable_set
variable without continuous variables supported, which is way more work.
The easiest solution may be to supported arbitrary objective functions (or at least more), which is more doable for constraint solvers
Related to https://github.com/Wikunia/ConstraintSolver.jl/issues/56
I had a problem with floating coefficients, which were
[1.0, 2.0, 3.0]
, they get converted to Int silently, which only errors if the coefficient is non-integral