Infinite Loop Issue with HiGHS Solver in Julia-JuMP During Sensitivity Analysis

Specific Domains Optimization (Mathematical)
,
1

I’m encountering a problem while running a sensitivity analysis for an optimization problem in Julia using JuMP and the HiGHS solver. Initially, the model execution time varies between 5 to 20 minutes for different input parameter combinations. However, for some combinations, the model runs indefinitely, exceeding 24 hours without reaching a solution. The process appears to be stuck at a single iteration, with the execution time frozen at 108.8 seconds (as indicated in the attached screenshot).

Screenshot_inf_loop
Screenshot_inf_loop1264×742 104 KB

I’m uncertain whether this issue is related to RAM limitations or another factor. Monitoring the Task Manager during execution shows that there is still available RAM, suggesting the problem might not be memory-related. To isolate the issue, I attempted running the model with only the problematic parameter sets, but the problem persists, ruling out the possibility of cumulative errors from serial execution.

Has anyone experienced a similar issue with the HiGHS solver or within a Julia-JuMP context? Any insights on potential causes or solutions would be greatly appreciated. Below are the steps I’ve taken so far without success:

  1. Monitoring RAM usage to check for possible memory leaks or limitations.
  2. Isolating the problematic parameter sets to identify if the issue is specific to certain data.
  3. Reviewing the solver’s documentation for known issues or limitations with certain types of optimization problems.

Any advice on further troubleshooting steps or solutions would be immensely helpful.

1 Like
2

Hi @vicente_zehnder, welcome to the forum!

To isolate the issue, I attempted running the model with only the problematic parameter sets, but the problem persists

This is actually good news because it means we might be able to figure out the problem :smile:

Could you send me the MPS file of the failing model? You can write a file with:

write_to_file(model, "fail.mps")

I’ll send you a private message with my email.

2 Likes
3

Hey @odow !

Thanks a lot for the warm welcome and for offering a hand with this! :smile: Really appreciate it. I’ve just sent over the MPS file to your email.

1 Like
4

I can’t reproduce the hang. I don’t know if this is a HiGHS bug, or just a difficult problem to solve. The hang might have been HiGHS failing to detect some degeneracy or cycling?

julia> using HiGHS

julia> h = Highs_create()
Ptr{Nothing} @0x00007fbe7b226200

julia> Highs_readModel(h, "fail.mps")
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Number of PL entries in BOUNDS section is 77760
Number of BV entries in BOUNDS section is 38880
0

julia> Highs_run(h)
Presolving model
34557 rows, 36717 cols, 140387 nonzeros
32397 rows, 34556 cols, 130656 nonzeros

Solving MIP model with:
   32397 rows
   34556 cols (8639 binary, 0 integer, 0 implied int., 25917 continuous)
   130656 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -33949085.7489  inf                  inf        0      0      0         0     0.5s
         0       0         0   0.00%   -11536488.54332 inf                  inf        0      0      4     29671     3.4s
         0       0         0   0.00%   -11535621.21849 inf                  inf    27780   3076     13     36433    10.3s
         0       0         0   0.00%   -11533277.72074 inf                  inf    33011   4684    361     41028    17.6s
         0       0         0   0.00%   -11532089.46961 inf                  inf    39272   7064    369     46548    23.9s
         0       0         0   0.00%   -11530464.96164 inf                  inf    30013  10060    373     54197    32.1s
         0       0         0   0.00%   -11529769.97896 inf                  inf    29907  12527    381     61030    40.6s
         0       0         0   0.00%   -11528704.58719 inf                  inf    30417  14491    387     66969    48.4s
         0       0         0   0.00%   -11528067.71604 inf                  inf    30883  14504    395     71974    56.3s
         0       0         0   0.00%   -11527614.11118 inf                  inf    30680  15865    401     76633    64.5s
         0       0         0   0.00%   -11527471.22196 inf                  inf    31284  16465    405     79070    69.8s
         0       0         0   0.00%   -11527395.95402 inf                  inf    31229  16980    409     81071    75.2s
         0       0         0   0.00%   -11527316.65888 inf                  inf    32100  12986    411     83006    81.1s
         0       0         0   0.00%   -11527141.27824 inf                  inf    28744  13832    421     86326    90.0s
         0       0         0   0.00%   -11526904.19827 inf                  inf    30467  14570    429     89556    97.2s
         0       0         0   0.00%   -11526692.91617 inf                  inf    27476  11189    435     92642   103.8s
         0       0         0   0.00%   -11526217.62272 inf                  inf    28778  11853    441     95643   110.2s
         0       0         0   0.00%   -11526042.22932 inf                  inf    29523   9730    448     98629   116.9s
         0       0         0   0.00%   -11525591.15637 inf                  inf    21970  12043    454    104795   125.7s
         0       0         0   0.00%   -11525462.37326 inf                  inf    21858  13684    461    110511   133.8s

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -11525198.98984 inf                  inf    20109  13303    468    115982   142.2s
         0       0         0   0.00%   -11525027.39853 inf                  inf    26182  14520    476    120505   150.4s
         0       0         0   0.00%   -11524564.44604 inf                  inf    24240  13815    483    125479   160.8s
         0       0         0   0.00%   -11524347.82893 inf                  inf    20714  14360    488    127468   166.3s
         0       0         0   0.00%   -11524265.45506 inf                  inf    23209  14853    492    129924   172.3s
         0       0         0   0.00%   -11524121.06832 inf                  inf    25798  15361    494    132013   177.7s
         0       0         0   0.00%   -11524110.68876 inf                  inf    24514  12646    501    136267   187.1s
         0       0         0   0.00%   -11524090.11569 inf                  inf    19274  13086    505    138311   192.1s
         0       0         0   0.00%   -11524070.90583 inf                  inf    21276  13488    511    140291   198.0s
         0       0         0   0.00%   -11524055.07528 inf                  inf    23417  13909    515    142270   204.4s
         0       0         0   0.00%   -11524046.45336 inf                  inf    25378  14334    519    145468   211.1s
         0       0         0   0.00%   -11524028.69166 inf                  inf    18428  12017    529    149498   220.3s
 L       0       0         0   0.00%   -11524028.69166 -11280420.84095    2.16%    18428  12017    559    149498   375.9s

0.2% inactive integer columns, restarting
Model after restart has 31239 rows, 33398 cols (8609 bin., 0 int., 0 impl., 24789 cont.), and 128168 nonzeros

         0       0         0   0.00%   -11524028.69166 -11280420.84095    2.16%     6850      0      0    269138   376.6s
         0       0         0   0.00%   -11524028.69166 -11280420.84095    2.16%     6850   3965      3    279771   384.7s
         0       0         0   0.00%   -11523938.47525 -11280420.84095    2.16%    22878   5856      3    284202   392.2s
         0       0         0   0.00%   -11523933.14471 -11280420.84095    2.16%    25779   6819      3    287539   398.4s
         0       0         0   0.00%   -11523867.12579 -11280420.84095    2.16%    28299   8532      3    293082   406.2s
         0       0         0   0.00%   -11523864.59742 -11280420.84095    2.16%    21953  10468      3    298176   415.0s

The problem just looks really hard to solve, so I tried a few other solvers.

Gurobi

(base) oscar@Oscars-MBP models_jump % gurobi_cl fail.mps 
Set parameter LogFile to value "gurobi.log"
Using license file /Users/oscar/gurobi.lic

Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (mac64[x86] - Darwin 22.6.0 22G91)
Copyright (c) 2023, Gurobi Optimization, LLC

Read MPS format model from file fail.mps
Reading time = 0.33 seconds
: 147910 rows, 147964 columns, 443732 nonzeros

CPU model: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 147910 rows, 147964 columns and 443732 nonzeros
Model fingerprint: 0x7c054958
Variable types: 109084 continuous, 38880 integer (38880 binary)
Coefficient statistics:
  Matrix range     [5e-08, 3e+04]
  Objective range  [2e-02, 4e+02]
  Bounds range     [1e+00, 5e+07]
  RHS range        [1e+00, 5e+07]
Presolve removed 117910 rows and 114756 columns
Presolve time: 1.19s
Presolved: 30000 rows, 33208 columns, 124257 nonzeros
Variable types: 24658 continuous, 8550 integer (8550 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing primal log only...

Concurrent spin time: 0.00s

Solved with dual simplex
Extra simplex iterations after uncrush: 40

Root relaxation: objective -1.153649e+07, 21304 iterations, 1.92 seconds (1.00 work units)
Total elapsed time = 5.29s (DegenMoves)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 -1.154e+07    0  865          - -1.154e+07      -     -    5s
     0     0 -1.154e+07    0 1462          - -1.154e+07      -     -    9s
     0     0 -1.154e+07    0 1459          - -1.154e+07      -     -    9s
     0     0 -1.154e+07    0 1487          - -1.154e+07      -     -   10s
     0     0 -1.154e+07    0 1487          - -1.154e+07      -     -   10s
     0     0 -1.154e+07    0 1419          - -1.154e+07      -     -   13s
     0     0 -1.154e+07    0 1416          - -1.154e+07      -     -   13s
     0     0 -1.153e+07    0 1427          - -1.153e+07      -     -   14s
     0     0 -1.153e+07    0 1425          - -1.153e+07      -     -   14s
     0     0 -1.153e+07    0 1390          - -1.153e+07      -     -   16s
     0     0 -1.153e+07    0 1395          - -1.153e+07      -     -   17s
     0     0 -1.153e+07    0 1391          - -1.153e+07      -     -   17s
     0     0 -1.153e+07    0 1393          - -1.153e+07      -     -   17s
     0     0 -1.153e+07    0 1448          - -1.153e+07      -     -   19s
     0     0 -1.153e+07    0  687          - -1.153e+07      -     -   25s
     0     2 -1.153e+07    0  679          - -1.153e+07      -     -   33s
    11    16 -1.153e+07    4 1058          - -1.153e+07      -   789   35s
   116   215 -1.153e+07   26  880          - -1.153e+07      -   411   40s
   482   611 -1.153e+07  106  764          - -1.153e+07      -   151   45s
   908  1031 -1.138e+07  199  848          - -1.153e+07      -   101   51s
  1144  1371 -1.151e+07  223  701          - -1.153e+07      -  98.4   55s
  1863  2012 infeasible  482               - -1.153e+07      -  67.3   60s
  2394  2626 -1.148e+07  594  384          - -1.153e+07      -  68.6   66s
  2961  2993 -1.153e+07   10  985          - -1.153e+07      -  59.2   70s
  3572  3655 -1.153e+07   64  805          - -1.153e+07      -  56.6   76s
H 3920  3905                    -1.13678e+07 -1.153e+07  1.46%  55.1   78s
* 3946  3874            1010    -1.14123e+07 -1.153e+07  1.07%  54.8   78s
H 4114  3987                    -1.14154e+07 -1.153e+07  1.04%  53.5   81s
H 4151  3946                    -1.14163e+07 -1.153e+07  1.03%  53.7   81s
H 4263  3946                    -1.14180e+07 -1.153e+07  1.02%  53.4   81s
H 4506  4390                    -1.14212e+07 -1.153e+07  0.99%  53.3   86s
H 4560  4265                    -1.14305e+07 -1.153e+07  0.91%  53.0   86s
H 4657  4250                    -1.14362e+07 -1.153e+07  0.86%  52.9   86s
H 4851  4500                    -1.14395e+07 -1.153e+07  0.83%  51.1   89s
H 4891  4265                    -1.14797e+07 -1.153e+07  0.47%  51.2   89s
H 4953  4250                    -1.14920e+07 -1.153e+07  0.37%  51.3   89s
  5089  4422 -1.150e+07  253  824 -1.149e+07 -1.153e+07  0.37%  50.0   92s
H 5146  4421                    -1.14920e+07 -1.153e+07  0.37%  49.7   92s
H 5320  1569                    -1.15152e+07 -1.153e+07  0.16%  49.7   97s
  5321  1551 -1.153e+07   58  687 -1.152e+07 -1.153e+07  0.16%  49.7  104s
  5323  1552 -1.152e+07   43  868 -1.152e+07 -1.152e+07  0.06%  49.7  113s
  5324  1553 -1.152e+07  103  625 -1.152e+07 -1.152e+07  0.05%  49.6  120s
  5327  1555 -1.152e+07  149  425 -1.152e+07 -1.152e+07  0.05%  49.6  129s
  5328  1556 -1.152e+07   39  479 -1.152e+07 -1.152e+07  0.05%  49.6  130s
  5329  1556 -1.152e+07  199  371 -1.152e+07 -1.152e+07  0.05%  49.6  136s
  5331  1558 -1.152e+07  112  343 -1.152e+07 -1.152e+07  0.05%  49.6  143s
  5333  1559 -1.152e+07  176  324 -1.152e+07 -1.152e+07  0.05%  49.6  149s
  5334  1560 -1.152e+07  136  342 -1.152e+07 -1.152e+07  0.05%  49.6  150s
  5336  1561 -1.152e+07   69  312 -1.152e+07 -1.152e+07  0.05%  49.5  161s
  5337  1562 -1.152e+07  174  312 -1.152e+07 -1.152e+07  0.05%  49.5  166s
  5340  1569 -1.152e+07   14  394 -1.152e+07 -1.152e+07  0.05%  59.8  171s
  5348  1574 -1.152e+07   15  400 -1.152e+07 -1.152e+07  0.05%  61.4  177s
  5352  1577 -1.152e+07   16  484 -1.152e+07 -1.152e+07  0.05%  61.9  180s
  5364  1585 -1.152e+07   17  431 -1.152e+07 -1.152e+07  0.05%  62.8  187s
  5376  1594 -1.152e+07   19  523 -1.152e+07 -1.152e+07  0.05%  63.6  191s
  5387  1609 -1.152e+07   20  525 -1.152e+07 -1.152e+07  0.05%  64.1  195s
  5401  1618 -1.152e+07   21  442 -1.152e+07 -1.152e+07  0.05%  64.5  200s
  5442  1626 -1.152e+07   27  435 -1.152e+07 -1.152e+07  0.05%  65.0  205s
  5511  1672 -1.152e+07   37  399 -1.152e+07 -1.152e+07  0.05%  65.9  211s
  5633  1763 -1.152e+07   57  401 -1.152e+07 -1.152e+07  0.05%  66.0  218s
  5836  1760 -1.152e+07   86  251 -1.152e+07 -1.152e+07  0.05%  67.3  223s
  5939  1898 -1.152e+07  102  241 -1.152e+07 -1.152e+07  0.05%  69.3  229s
  6144  2016 -1.152e+07  128  205 -1.152e+07 -1.152e+07  0.05%  69.8  234s
  6375  2111 -1.152e+07  158  187 -1.152e+07 -1.152e+07  0.05%  69.7  239s
  6612  2127 -1.152e+07  191  175 -1.152e+07 -1.152e+07  0.05%  69.1  244s
  6800  2103 -1.152e+07  221  178 -1.152e+07 -1.152e+07  0.05%  70.2  249s
  6914  2155     cutoff  248      -1.152e+07 -1.152e+07  0.05%  71.7  254s
  7093  2217 -1.152e+07   23  479 -1.152e+07 -1.152e+07  0.05%  73.5  261s
H 7201  2032                    -1.15155e+07 -1.152e+07  0.04%  74.3  261s
^C
Interrupt request received

SCIP

I needed to turn off heuristics/feaspump or it would get stuck.

(base) oscar@Oscars-MBP models_jump % scip -s scip.set -f fail.mps   
SCIP version 7.0.3 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 5.0.2] [GitHash: 74c11e60cd]
Copyright (C) 2002-2021 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

External libraries: 
  SoPlex 5.0.2         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: e24c304e]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (www.coin-or.org/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.2.1            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.4.0          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  PaPILO 1.0.2         parallel presolve for integer and linear optimization [GitHash: e567fef]
  bliss 0.73.3p        Computing Graph Automorphism Groups by T. Junttila and P. Kaski (http://www.tcs.hut.fi/Software/bliss/)
  Ipopt 3.14.1         Interior Point Optimizer developed by A. Waechter et.al. (www.coin-or.org/Ipopt)

reading user parameter file <scip.set>

read problem <fail.mps>
============

original problem has 147964 variables (38880 bin, 0 int, 0 impl, 109084 cont) and 147910 constraints

solve problem
=============

presolving:
(round 1, fast)       55129 del vars, 32414 del conss, 0 add conss, 28092 chg bounds, 0 chg sides, 1080 chg coeffs, 0 upgd conss, 0 impls, 8634 clqs
(round 2, fast)       72942 del vars, 81521 del conss, 0 add conss, 35481 chg bounds, 1080 chg sides, 3240 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 3, fast)       98298 del vars, 98246 del conss, 0 add conss, 38374 chg bounds, 1080 chg sides, 3240 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 4, fast)       102614 del vars, 98246 del conss, 0 add conss, 41965 chg bounds, 1080 chg sides, 3240 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
   (1.3s) running MILP presolver
   (1.4s) MILP presolver (5 rounds): 1082 aggregations, 0 fixings, 4333 bound changes
(round 5, medium)     103696 del vars, 98246 del conss, 0 add conss, 46314 chg bounds, 1080 chg sides, 3240 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 6, fast)       103696 del vars, 99328 del conss, 0 add conss, 46315 chg bounds, 1080 chg sides, 4330 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 7, fast)       103696 del vars, 99328 del conss, 0 add conss, 72211 chg bounds, 1080 chg sides, 4330 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 8, fast)       116644 del vars, 112276 del conss, 0 add conss, 72211 chg bounds, 1080 chg sides, 4330 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
   (1.7s) running MILP presolver
   (1.8s) MILP presolver (4 rounds): 1082 aggregations, 0 fixings, 0 bound changes
(round 9, medium)     117726 del vars, 112276 del conss, 0 add conss, 72211 chg bounds, 1080 chg sides, 4330 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 10, fast)       117726 del vars, 113357 del conss, 0 add conss, 72211 chg bounds, 1080 chg sides, 4330 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 11, exhaustive) 117726 del vars, 113358 del conss, 0 add conss, 72211 chg bounds, 1080 chg sides, 4330 chg coeffs, 3240 upgd conss, 0 impls, 0 clqs
(round 12, exhaustive) 117726 del vars, 113358 del conss, 0 add conss, 72211 chg bounds, 1080 chg sides, 4330 chg coeffs, 4317 upgd conss, 3240 impls, 0 clqs
   (2.1s) sparsify finished: 3240/142541 (2.3%) nonzeros canceled - in total 3240 canceled nonzeros, 8640 changed coefficients, 0 added nonzeros
   (2.2s) probing: 51/8640 (0.6%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes
   (2.2s) probing aborted: 50/50 successive totally useless probings
   (2.3s) symmetry computation started: requiring (bin +, int -, cont +), (fixed: bin -, int +, cont -)
   (2.4s) no symmetry present
presolving (13 rounds: 13 fast, 5 medium, 3 exhaustive):
 117726 deleted vars, 113358 deleted constraints, 0 added constraints, 72211 tightened bounds, 0 added holes, 1080 changed sides, 12970 changed coefficients
 4317 implications, 0 cliques
presolved problem has 36712 variables (8640 bin, 0 int, 0 impl, 28072 cont) and 34552 constraints
   4317 constraints of type <varbound>
  30235 constraints of type <linear>
Presolving Time: 2.04

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
 52.1s|     1 |     0 | 46718 |     - |   623M |   0 |  36k|  34k|  34k|   0 |  0 |   1 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 65.0s|     1 |     0 | 46727 |     - |   630M |   0 |  36k|  34k|  34k|   4 |  1 |   2 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 68.0s|     1 |     0 | 46990 |     - |   634M |   0 |  36k|  34k|  34k| 125 |  2 |   3 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 70.6s|     1 |     0 | 47228 |     - |   638M |   0 |  36k|  34k|  34k| 248 |  3 |   4 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 73.6s|     1 |     0 | 47285 |     - |   641M |   0 |  36k|  34k|  34k| 270 |  4 |   5 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 76.5s|     1 |     0 | 47364 |     - |   645M |   0 |  36k|  34k|  34k| 309 |  5 |   6 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 79.6s|     1 |     0 | 47393 |     - |   650M |   0 |  36k|  34k|  34k| 321 |  6 |   7 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 82.9s|     1 |     0 | 47723 |     - |   654M |   0 |  36k|  34k|  34k| 442 |  7 |   8 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 86.1s|     1 |     0 | 47904 |     - |   657M |   0 |  36k|  34k|  35k| 511 |  8 |   9 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 89.7s|     1 |     0 | 48032 |     - |   661M |   0 |  36k|  34k|  35k| 545 |  9 |  10 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 93.4s|     1 |     0 | 48055 |     - |   664M |   0 |  36k|  34k|  35k| 557 | 10 |  11 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 95.6s|     1 |     0 | 48172 |     - |   668M |   0 |  36k|  34k|  35k| 627 | 11 |  12 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 96.4s|     1 |     0 | 48172 |     - |   669M |   0 |  36k|  34k|  35k| 627 | 11 |  13 |   0 |-1.153649e+07 |      --      |    Inf | unknown
 97.8s|     1 |     0 | 48175 |     - |   673M |   0 |  36k|  34k|  35k| 629 | 12 |  13 |   0 |-1.153649e+07 |      --      |    Inf | unknown
^Cpressed CTRL-C 1 times (5 times for forcing termination)
 99.8s|     1 |     0 | 48253 |     - |   676M |   0 |  36k|  34k|  35k| 673 | 13 |  14 |   0 |-1.153649e+07 |      --      |    Inf | unknown

Comments

They all struggle to solve this problem. So

  • The LP relaxation is very close to optimal
  • The solver has a hard time finding a feasible solution
  • The first feasible solution found is very close to optimal

You can probably make much better progress if you:

  • Provide a feasible starting point
  • Consider other formulations of your problem. What is it modeling and how?
2 Likes
5

Thank you, @odow, for your valuable help.

Your advice helped me solve the problem. It appears that the root of the problem was my reliance on JuMP functions for running the models, which led to the solver getting stuck at a specific iteration. Initially, my approach was as follows:

using JuMP, HiGHS

model = Model(HiGHS.Optimizer)

## rest of the model definition

set_optimizer_attribute(model, "mip_rel_gap", 0.02) 

optimize!(model)

With this setup, the solver would halt at the iteration detailed in my original post, and it remained in that state for over 24 hours.

However, by creating the model with JuMP and then reading and executing it using the functions from the HiGHS package, the problem was resolved in less than 4 minutes (with the relative gap of 2%):

using JuMP, HiGHS

model = Model(HiGHS.Optimizer)

## rest of the model definition

write_to_file(model, "model.mps")

h = Highs_create()

Highs_readModel(h, "model.mps")

Highs_setStringOptionValue(h, "mip_rel_gap", "0.02")

Highs_run(h)

I’m not exactly sure why JuMP was causing the solver to get stuck, but it seems like using HiGHS directly is the way to go.

Once again, thank you for your support!

1 Like
6

This shouldn’t have made a difference.

One option is that the two models may have a different row order, so the difference I timings is just luck.

For an example that gets stuck, could you try:

model = Model(HiGHS.Optimizer)
## rest of the model definition
set_attribute(model, "time_limit", 10.0) 
optimize!(model)
Highs_writeModel(unsafe_backend(model), "fail.mps")

There probably is a cycling bug somewhere in HiGHS, but it’s hard to reproduce without the exact model.

2 Likes
7

Hello @odow,

I executed the code you shared but replaced set_attribute(model, 'time_limit', 10.0) with set_optimizer_attribute(model, 'time_limit', 10.0) due to an error. I will send you an email with the modified .mps file.

When i read it and run it using the HiGHS package, it stalls but it takes significantly more time before reaching that iteration.

Is there a method to prevent this by setting a time limit per iteration, with an attribute like “time_limit”?

I’d share the entire model, but it contains sensitive data and is quite large, making it challenging to review quickly. However, I’ll explore what can be done regarding this.

Thank you again for your help with this problem.

Best.

8

What version of JuMP and HiGHS are you using? Maybe the problem will be fixed if you update your packages to a newer version.

You can check the version with import Pkg; Pkg.status().

9

I got the following

julia> import Pkg; Pkg.status()
Status `C:\Users\vicen\OneDrive\Documents\codigos\optimizacion\Optimization\Project.toml`
  [87dc4568] HiGHS v1.7.5
  [682c06a0] JSON v0.21.4
10

Okay, not a HiGHS version problem so ignore my comment.

(But version of JuMP? set_attribute should have worked.)

p.s. I’m about to leave for the weekend, but I’ll test your email when I get a chance.

11

I’m not sure why, but in the project.toml file, there were only the HiGHS and JSON packages, and the model was running with the JuMP version I installed directly on my PC a few months ago. So, I ran (Optimization) pkg> add JuMP, and JuMP was downloaded again and added to the project.toml file.

The versions I now have are:

julia> import Pkg; Pkg.status()
Status `C:\Users\vicen\OneDrive\Documents\codigos\optimizacion\Optimization\Project.toml`
  [87dc4568] HiGHS v1.8.1
  [682c06a0] JSON v0.21.4
  [4076af6c] JuMP v1.20.0

When I run the model now, it takes more than 1 hour to reach a solution, but it doesn’t stall, so the problem is solved.

There are still a couple of things.

I still get an error by using set_attribute(). I tried running the following code to see if there was another version inside the function I’m using:

        model = Model(HiGHS.Optimizer)
        Pkg.status()
        set_attribute(model, "time_limit", 10.0)

But get the same error:

Status `C:\Users\vicen\OneDrive\Documents\codigos\optimizacion\Optimization\Project.toml`
  [87dc4568] HiGHS v1.8.1
  [682c06a0] JSON v0.21.4
  [4076af6c] JuMP v1.20.0
ERROR: UndefVarError: `set_attribute` not defined
Stacktrace:

Also, I’m still curious why, when I run the same model but save it in a .mps file and then read it with the HiGHS package functions, it runs so much faster. Is there a way to replicate that efficiency using JuMP directly?

12

You likely need to restart Julia for the new version to be loaded. That should work.

Also, I’m still curious why, when I run the same model but save it in a .mps file and then read it with the HiGHS package functions, it runs so much faster. Is there a way to replicate that efficiency using JuMP directly?

It is just luck. The models may have the rows in the constraint matrix in a different order. There is no way to replicate directly. It could equally have been the other way, where reading from file was slower than JuMP.

13

Hi odow!

I hope this message finds you well. I apologize for the delay in my previous response.
Recently, I’ve successfully utilized the set_attribute function; however, I’ve encountered again the stalling issue. This time, the model stalls at 112 seconds. Despite setting the time limit attribute to 200 seconds, the model fails to terminate even after surpassing the 200-second threshold. It seems the issue prevents the model from enforcing the time limit constraint.

using JuMP, HiGHS

model = Model(HiGHS.Optimizer)

## rest of the model definition

set_attribute(model, "time_limit", 200.0)

optimize!(model)

## It stalls for more than 200 seconds

I tried running it again using the highs packages, but the stalling problem doesnt repeat:

using JuMP, HiGHS

model = Model(HiGHS.Optimizer)

## rest of the model definition

Highs_writeModel(unsafe_backend(model), "model.mps")

h = Highs_create()

Highs_readModel(h, "model.mps")

Highs_run(h)

## the model reaches a solution

Is there a way save and reaload the model to JuMP so the issue can be replicated?

The versions of my Pkg are the same as before.

14

Is there a way save and reaload the model to JuMP so the issue can be replicated?

Not really. You could email me the full script?

I think this is a bug inside HiGHS, where if we create the model programatically via JuMP, we get different behavior to reading the MPS file. I’m about to make a new release of HiGHS.jl that supports HiGHS v1.7.0: Support HiGHS v1.7.0 by odow · Pull Request #205 · jump-dev/HiGHS.jl · GitHub. That might fix it, or it might not.

If it continues to be a problem, you might be best using a different solver like Gurobi.jl.

15

Hello @odow,

I’ve set up a new environment to test all the packages, and I’m observing different versions for them. Here is the output from Pkg.status():

julia> Pkg.status()
Status `C:\Users\vicen\OneDrive\Documents\codigos\optimizacion\Optimization\Project.toml`
  [336ed68f] CSV v0.10.13
  [a93c6f00] DataFrames v1.6.1
  [87dc4568] HiGHS v1.9.0
  [a98d9a8b] Interpolations v0.15.1
⌅ [4076af6c] JuMP v0.23.2
  [0f51c51e] PiecewiseLinearOpt v0.4.1
  [91a5bcdd] Plots v1.40.3
  [9ff05d80] TickTock v1.3.0
  [fdbf4ff8] XLSX v0.10.1
  [9e88b42a] Serialization
  [10745b16] Statistics v1.9.0
Info Packages marked with ⌅ have new versions available but compatibility constraints restrict them from upgrading. To see why use `status --outdated`

The current version of JuMP is v0.23.2, and it seems there might be a compatibility issue. When trying to update JuMP to v1.21.0, it fails due to compatibility constraints with PiecewiseLinearOpt:

julia> Pkg.add(PackageSpec(name="JuMP", version="1.21.0"))
   Resolving package versions...
ERROR: Unsatisfiable requirements detected for package JuMP [4076af6c]:
 JuMP [4076af6c] log:
 ├─possible versions are: 0.18.3-1.21.0 or uninstalled
 ├─restricted to versions 1.21.0 by an explicit requirement, leaving only versions: 1.21.0
 └─restricted by compatibility requirements with PiecewiseLinearOpt [0f51c51e] to versions: [0.19.0-0.21.10, 0.23.0-0.23.2] — no versions left
   └─PiecewiseLinearOpt [0f51c51e] log:
     ├─possible versions are: 0.2.1-0.4.1 or uninstalled
     └─restricted to versions * by an explicit requirement, leaving only versions: 0.2.1-0.4.1

Could this be the source of the issue? Is there an alternative package for implementing piecewise linear constraints that would be compatible with a newer version of JuMP?

16

Could this be the source of the issue?

That’s a very old version of JuMP, so it could be, or maybe not. There’s only one way to tell :laughing:

Is there an alternative package for implementing piecewise linear constraints that would be compatible with a newer version of JuMP?

Not that I’m aware of.

17

Ok, thank you for the help!

1 Like