Adding a variable slows down the search

[hakank]

(Perhaps I should be surprised by this, but I wanted to report it.)

The following model solves the problem of finding the smallest difference between ABCDE - FGHIJ, where A..J are distinct integers 0..9. The optimal answer is 247 = 50123 - 49876.

When using the variable diff, the best solution time I've found is 20.4s.Without diff - i.e. using only the constraint @constraint(model, v[1] - v[2] >= 1) (commented below) - it's much faster: about 0.6s.

Is this expected, i.e. that the solver works better with as few variables as possible? This kind of makes sense since more variables mean a larger model, but I'm a little surprise by the difference between the two solving times.

That said, the reason it's slow might be that I've not found the best heuristics + solver (but I've tried many combinations).

using ConstraintSolver, JuMP
using Cbc, GLPK
const CS = ConstraintSolver

function least_diff()

    cbc_optimizer = optimizer_with_attributes(Cbc.Optimizer, "logLevel" => 0)
    glpk_optimizer = optimizer_with_attributes(GLPK.Optimizer)

    model = Model(optimizer_with_attributes(CS.Optimizer, 
                                                            "logging"=>[],
                                                            # Testing different heuristics...
                                                            # "traverse_strategy"=>:BFS,
                                                            "traverse_strategy"=>:DFS,
                                                            # "traverse_strategy"=>:DBFS,

                                                            # "branch_split"=>:Smallest,
                                                            # "branch_split"=>:Biggest,
                                                            "branch_split"=>:InHalf, 

                                                            "time_limit"=>120,

                                                            # "lp_optimizer" => cbc_optimizer, # 45.8s
                                                            # "lp_optimizer" => glpk_optimizer, # 21.5s
                                        ))

    @variable(model, 0 <= x[1:10] <= 9, Int)
    @variable(model, 10000 <= v[1:2] <= 99999, Int) # ABCDE and FGHIJ
    @variable(model, 0 <= diff <= 999, Int) # adding this is much slower than using v[1:2] only

    a,b,c,d,e,f,g,h,i,j = x
    @constraint(model, x in CS.AllDifferentSet())
    @constraint(model, v[1] == 10000*a + 1000*b + 100*c + 10*d + e) # ABCDE
    @constraint(model, v[2] == 10000*f + 1000*g + 100*h + 10*i + j) # FGHIJ

    # Using diff is slower
    @constraint(model, diff == v[1] - v[2])  # much slower
    @constraint(model, diff >= 1)

    # this is much faster
    # @constraint(model, v[1] - v[2] >= 1) 

    @objective(model, Min, diff) # slower

    # Faster
    # @objective(model, Min, v[1]-v[2])

    # Solve the problem
    println("solve")
    optimize!(model)

    status = JuMP.termination_status(model)
    println("status:$status")
    if status == MOI.OPTIMAL
        x = convert.(Integer,JuMP.value.(x))
        abcde = convert.(Integer,JuMP.value.(v[1]))
        fghij = convert.(Integer,JuMP.value.(v[2]))
        println("x:$x")
        println("$diff = $abcde - $fghij")
        num_sols = MOI.get(model, MOI.ResultCount())
        println("\nnum_sols:$num_sols\n")
    end
end

least_diff()

[Wikunia]

Thanks for opening up this issue. It's very valuable for me to have different people trying out different problems to improve this solver.

I'll test this out tmr and get back to you with some more insight.

For now I can just guess that the extra constraint that you have might be called relatively late inside the pruning step which will prune everything again. The order in which the constraints are called might make a difference but yeah such a huge one is definitely unexpected.

Will do some debugging and plotting of the search graph tmr.

[Wikunia]

Okay some new ideas 😄

When you write v[1] - v[2] without defining diff with it the bound computation is less strong such that the best bound is often negative. Which obviously can't work as you have defined that v[1] should be bigger. I should definitely fix that. Nonetheless, in this example it seems to stear the search in a better direction to find an incumbent.

I'll further investigate this in the next days.

[Wikunia]

In most cases it is reasonable to use an lp solver as my bound computation is really bad but I've seen that you have tried that as well so I'll check what happens in that case.