Wikunia / ConstraintSolver.jl

ConstraintSolver in Julia: Blog posts ->
https://opensourc.es/blog/constraint-solver-1
MIT License
136 stars 14 forks source link

Bug probably in bound computation #99

Closed Wikunia closed 4 years ago

Wikunia commented 4 years ago

The maximum stable set of the following should be 2.7.

matrix = [
        0  1  0  1  0  0  1  0  0  1
        1  0  1  0  1  0  0  0  0  0
        0  1  0  1  0  0  0  0  1  0
        1  0  1  0  1  1  0  0  0  0
        0  1  0  1  0  1  1  1  0  0
        0  0  0  1  1  0  1  0  0  0
        1  0  0  0  1  1  0  1  0  0
        0  0  0  0  1  0  1  0  1  0
        0  0  1  0  0  0  0  1  0  1
        1  0  0  0  0  0  0  0  1  0
    ]
    n = 10
    m = Model(CS.Optimizer)
    @variable(m, x[1:n], Bin)
    for i = 1:n, j = i+1:n
        if matrix[i, j] == 1
            @constraint(m, x[i] + x[j] <= 1)
        end
    end
    w = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]
    @objective(m, Max, dot(w, x))
    optimize!(m)
    @assert MOI.get(m, MOI.ObjectiveValue()) ≈ 2.7

It produces this output:

 #Open      #Closed         Incumbent             Best Bound        Time [s]  
================================================================================
     1           1                -                    3.70             1.50    
     3           3               0.90                  3.70             1.93    
     26          28              1.80                  1.70             1.99    

The incumbent should never be better than the best bound.