time_limit seemingly not respected in MIP

[DillonJ]

Hi folks,

We're running a big model iteratively and have set time_limit = 300s... however solves are regularly taking > 600s to solve. Is it possible that time_limit doesn't apply to MIP problems and if this is the case, how would one set a time limit for MIP problems?

Thanks in advance!

[jajhall]

There are tests for the run time reaching time_limit in the MIP solver, but it may not be done somewhere that it can spend this length of time for a large model.

Could you let us have the output from HiGHS to see if we can pinpoint where it is happening? This may well not be enough, and the ideal would be for you to let us have an example of the model that causes this.

[lgottwald]

The time limit does apply to the MIP solver but clearly there seems to be a procedure that does not check it often enough. It would be good to either have an example model or alternatively to add a debugger trace after 300 seconds after compiling with -DCMAKE_BUILD_TYPE=RelWithDebInfo. For gdb you can run the executable and hit CTRL+C when the timelimit is reached. Entering "bt" will give a stack trace that allows me to see where the MIP solver is stuck at that point.

[jajhall]

@DillonJ Are you building from source, or using the JuMP-hosted binaries?

[berkorbay]

I happen to have this issue as well. I think it is from JuMP binaries but I can't exactly remember. Though, whenever I solve I get the following log.

"Running HiGHS 1.2.1 [date: 2022-03-25, git hash: 2e00bc08]"

Btw, is this merge related? https://github.com/ERGO-Code/HiGHS/pull/825#issuecomment-1110014670

edit: I just tried the same model (mps) with the latest github commit. Time limit problem persists on at least MacOS Monterey.

[odow]

Here's an example from https://github.com/DrChainsaw/NaiveNASlib.jl/issues/100.

Not bad in this case, since it takes only 1 second, but I think if the problem is large it can take arbitrarily longer before existing. Seems like there's something in presolve that isn't checking the limits.

Couldn't reproduce via MPS file because the reading is counted as the run time so hard to set time appropriately.

julia> using HiGHS

julia> function main()
           n = 100_000
           highs = Highs_create()
           for i in 1:(11 * n)
               Highs_addVar(highs, 0.0, 10.0)
               Highs_changeColCost(highs, i - 1, 1.0)
               Highs_changeColIntegrality(highs, i - 1, kHighsVarTypeInteger)
           end
           for i in 0:(n-1)
               Highs_addRow(highs, 0.0, 0.0, 2, Cint[i, n + i], [1.0, -1.0])
               Highs_addRow(highs, 0.0, 0.0, 2, Cint[i, 2n + i], [1.0, -1.0])
               Highs_addRow(highs, 0.0, 0.0, 2, Cint[i, 2n + i], [1.0, -1.0])
           end
           function _add_row(highs, lhs, rhs)
               aindex = Cint.([lhs; rhs])
               avalue = [ones(length(lhs)); -ones(length(rhs))]
               Highs_addRow(highs, -Inf, 0.0, length(aindex), aindex, avalue)
           end
           _add_row(highs, 0:33333, 4n:(6n-1))
           _add_row(highs, 24999:(n-1), n:(2n-1))
           _add_row(highs, 4n:(5n-1), (6n-1):(11n-1))
           Highs_setDoubleOptionValue(highs, "time_limit", 0.01)
           Highs_run(highs)
           @show Highs_getRunTime(highs)
           time_limitP = Ref{Cdouble}()
           Highs_getDoubleOptionValue(highs, "time_limit", time_limitP)
           @show time_limitP[]
           Highs_writeModel(highs, "time_limit.mps")
           Highs_destroy(highs)
           return
       end
main (generic function with 1 method)

julia> main()
Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
2 rows, 700000 cols, 800001 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      0
  Dual bound        0
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    0 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            1.10 (total)
                    0.94 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
Highs_getRunTime(highs) = 1.1555933272466063
time_limitP[] = 0.01
Writing the model to time_limit.mps
WARNING: There are empty or excessively-long column names: using constructed names with prefix "c"
WARNING: There are empty or excessively-long row names: using constructed names with prefix "r"

There have been quite a few reports of this: https://github.com/jump-dev/HiGHS.jl/issues/125, https://github.com/jump-dev/HiGHS.jl/issues/162