Replace CBC with HIGHS

[drchainsaw]

Replace CBC with HIGHS

[odow]

Do you have a reproducible example? Is there a log of the solve that doesn't respect the time limit?

[DrChainsaw]

It turned out to not be trivial to create a reproducer. I guess this means that a possible workaround for me is to just add some extra constraints/objectives in the testcase.

Here is the closest I have gotten to an MWE which mimics the testcase, but it does not behave exactly the same since the optimal solution seems to be found in way fewer steps and increasing the size of the problem beyond n=1000000 or so just makes the program hang before solving starts. Posting it anyways in case it should be enough.

julia> versioninfo()
Julia Version 1.9.0-rc2
Commit 72aec423c2 (2023-04-01 10:41 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 12 × Intel(R) Core(TM) i7-5820K CPU @ 3.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, haswell)
  Threads: 1 on 12 virtual cores
Environment:
  JULIA_DEPOT_PATH = E:/Programs/julia/.julia
  JULIA_PKG_DEVDIR = E:/Programs/julia/.julia/dev
  JULIA_EDITOR = code
  JULIA_NUM_THREADS = 1

function testtimeout(n, t=n/1000000, rng=Xoshiro(1))
       model = JuMP.Model(JuMP.optimizer_with_attributes(HiGHS.Optimizer, "time_limit"=>float(t)))

       v0 = @variable(model, [1:n], Int)
       v1 = @variable(model, [1:3n], Int)
       v2 = @variable(model, [1:7n], Int)
       v3 = @variable(model, [1:7n], Int)

       @constraint(model, 0 .<= v0 .<= 10)
       @constraint(model, 0 .<= v1 .<= 10)
       @constraint(model, 0 .<= v2 .<= 10)
       @constraint(model, 0 .<= v3 .<= 10)

       @constraint(model, v0 .== v1[1:n])
       @constraint(model, v0 .== v1[n+1:2n])
       @constraint(model, v0 .== v1[2n+1:3n])

       @constraint(model, v1 .== v2[1:3n])
       @constraint(model, v0 .== v2[3n+1:4n])
       @constraint(model, v1 .== v2[4n+1:7n])

       @constraint(model, v3 .== v2)

       @constraint(model, sum(v0[1:cld(n,3)]) <= sum(v2[1:2n]))
       @constraint(model, sum(v1[1:n]) >= sum(v0[cld(n, 4):end]))
       @constraint(model, sum(v2[1:n]) <= sum(v3[2n:end]))
       @constraint(model, sum(v0[1:cld(n,4)]) >= sum(v3[1:n]))

       # Enabling these makes the solver exit due to time limit reliably 
       #@constraint(model, sum(v0) <= 0.8length(v0))
       #@constraint(model, sum(v1) <= 0.8length(v1))
       #@constraint(model, sum(v2) <= 0.8length(v2))
       #@constraint(model, sum(v3) <= 0.8length(v3))

       @objective(model, Min, sum(v3 .* randn(rng, length(v3))) + sum(v2 .* randn(rng, length(v2))) + sum(v1 .* randn(rng, length(v1))))

       @show JuMP.get_attribute(model, "time_limit")
       JuMP.optimize!(model)
       end

julia> testtimeout(100000)
JuMP.get_attribute(model, "time_limit") = 0.1
Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
4 rows, 87384 cols, 262151 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      -415744.702504
  Dual bound        -415744.702504
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    -415744.702504 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            3.68 (total)
                    3.35 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Here is output from the failing testcase but turned up to 100000 neurons in the first layer (I have double checked that the time limit is set to 0.001). What it does have in common is that the optimal solution seems to be found during presolve, so a naive guess of the root cause is that time limit is only checked after presolve.

Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
16 rows, 200002 cols, 2400004 nonzeros
1 rows, 21 cols, 21 nonzeros
1 rows, 10 cols, 10 nonzeros
1 rows, 5 cols, 5 nonzeros
1 rows, 3 cols, 3 nonzeros
0 rows, 1 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      99900.9991
  Dual bound        99900.9991
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    99900.9991 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            20.07 (total)
                    19.17 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Ripping out all the constraints and objective expressions would take quite a bit of effort. If it is useful I can dump the model to some file format and post it here.

[odow]

What it does have in common is that the optimal solution seems to be found during presolve, so a naive guess of the root cause is that time limit is only checked after presolve.

That's pretty plausible. Especially if it is making progress. Most solvers treat limits as a strong hint, rather than something that they hit exactly.