Stalled after 'Constructing starting basis'?

[cfe316]

I'm running HiGHS 1.11.0 via JuMP on Julia 1.9.4.

My options are:

primal_feasibility_tolerance: 1e-6
dual_feasibility_tolerance: 1e-6
presolve: "choose"
solver: "ipm"
run_crossover: "off"
ipm_optimality_tolerance: 1e-8

I'm using the interior point method, looks like IPX version 1.0.
I'm able to use this to solve small example problems, but it seems to have stalled out on a larger problem. Specifically, there's been no progress for several hours after the Constructing starting basis... phase:

Running HiGHS 1.11.0 (git hash: 364c83a51e): Copyright (c) 2025 HiGHS under MIT licence terms                                                                 
LP   has 36592082 rows; 20666490 cols; 172608415 nonzeros                                                                                                     
Coefficient ranges:                                                                                                                                           
  Matrix [2e-05, 1e+03]                                                                                                                                       
  Cost   [4e-05, 5e+03]                                                                                                                                       
  Bound  [0e+00, 0e+00]                                                                                                                                       
  RHS    [5e-11, 5e+02]                                                                                                                                       
Presolving model                                                                                                                                              
16056802 rows, 9061682 cols, 72635162 nonzeros  82s                                                                                                           
Dependent equations search running on 1435540 equations with time limit of 1000.00s                                                                           
Dependent equations search removed 0 rows and 0 nonzeros in 0.33s (limit = 1000.00s)                                                                          
14372829 rows, 7552404 cols, 74880264 nonzeros  191s                                                                                                          
Presolve : Reductions: rows 14372829(-22219253); columns 7552404(-13114086); elements 74880264(-97728151)                                                     
Solving the presolved LP                                                                                                                                      
IPX model has 14372829 rows, 7727604 columns and 75055464 nonzeros                                                                                            
Input                                                                                                                                                         
    Number of variables:                                7727604                                                                                               
    Number of free variables:                           47019                                                                                                 
    Number of constraints:                              14372829                                                                                              
    Number of equality constraints:                     1610740                                                                                               
    Number of matrix entries:                           75055464                                                                                              
    Matrix range:                                       [3e-04, 1e+03]                                                                                        
    RHS range:                                          [5e-11, 3e+02]                                                                                        
    Objective range:                                    [3e-06, 3e+02]                                                                                        
    Bounds range:                                       [1e-05, 3e+02]                                                                                        
Preprocessing                                                                                                                                                 
    Dualized model:                                     no                                                                                                    
    Number of dense columns:                            0                                                                                                     
    Range of scaling factors:                           [6.25e-02, 3.20e+01]                                                                                  
    Scaled cost norm:                                   330.475                                                                                               
    Scaled bounds norm:                                 640                                                                                                   
IPX version 1.0                                                                                                                                               
Interior point solve                                                                                                                                          
 Iter     P.res    D.res            P.obj           D.obj        mu     Time                                                                                  
   0   3.49e+02 1.48e+02   1.22501706e+07 -1.33492216e+09  5.18e+04     314s
 Constructing starting basis...                                                                                                                               
 325857 fixed variables remaining                                                                                                                             
 325741 fixed variables remaining                                                                                                                             
 325625 fixed variables remaining 
 ... 
 [several hours later]
 ...
 326 fixed variables remaining
 209 fixed variables remaining
 92 fixed variables remaining
 ...
 [stalled here for several hours]

I can see the single CPU chugging along, and the machine's memory still has more than 100 GB free, so I don't think that's the issue here? This problem has been solved with nonfree solvers, so I don't think an infeasibility is the issue.
Should I keep waiting? Does this step ordinarily take a long while before the next log output? Is there a way to increase the log verbosity?

[jajhall]

Should I keep waiting? Does this step ordinarily take a long while before the next log output? Is there a way to increase the log verbosity?

Not after such a long time. It's true that adding some logging to this stage would be useful for users

Unfortunately this is a feature of IPX. It's computing a preconditioner for the remaining IPM iterations and the algorithm to do this can take forever. It's one reason why we've written a new interior point solver, HiPO that will be in the next release.

If you can find a way to share your LP with me, I'd be curious to see how HiPO performs on it, and our first order solver on a GPU

[cfe316]

Thanks Julian. I would very much appreciate any assistance. This is a GenX electricity systems modeling problem. It's using a customized branch of an older version of GenX, and the input data for the runs I been trying to reproduce have been archived as well.

Unfortunately I needed to make a slight modification to the archive data as I found I'd make a mistake with relative links, and I needed to make some slight mods to the GenX branch as well. If you'd like to try it I'd be happy to push the GenX branch to github, and send you the GenX input data. Unless there's a better way to transfer the problem to you? I could try to make JuMP output an .lp file before solving, is that the way to go?

Are there other options for solving with HiGHS? I tried the simplex method and that seemed to stall (constraint violations became very large) and wasn't making good progress even after millions of iterations. Also I've read that IPM is generally better than simplex for electricity systems modeling.
Should I try turning off the preconditioner?

[jajhall]

Thanks: GenX are friends of ours - Jesse has been very helpful - so you're more than welcome!

I should have said that I can only use a .lp or .mps file - I'd prefer MPS. JuMP are even closer friends...

Simplex won't solve this. IPM is generally better than simplex for solving any LP without a good guess of the optimal solution.

You can't turn off the preconditioner in IPX: it's essential for solving LPs. The iteration(s) before "Constructing starting basis..." are very crude, and just there so that the initial guess of a basis for the preconditioner is better.

[cfe316]

As a "full disclosure" (realized just now I needed to update my github bio): I've recently moved to private industry. I was part of Jesse's lab as a postdoc for a few years, particularly in 2021 and '22.

What's a good way to get a gigabyte-scale file to you? The .lp was 4.5GB; I'm having it output a .mps now.

Just to be sure is "preconditioner" the same thing as "presolve"?

[jajhall]

What's a good way to get a gigabyte-scale file to you? The .lp was 4.5GB; I'm having it output a .mps now.

Google drive? We Transfer? Teams?

Just to be sure is "preconditioner" the same thing as "presolve"?

No, presolve reduces the size of the problem that actually has to be solved as an LP. In your case it's very effective, since your original LP has 36592082 rows and 20666490 columns, but after just 191s of presolve the LP solver has to solve a problem with "only" 14372829 rows and 7552404 columns. Those 191s are an excellent investment.

After the LP is solved, the optimal solution of the original problem will be deduced by "postsolve"

[cfe316]

I've shared the 9.6GB GenXModel.mps file via google drive to the ed.ac.uk email in your github profile. Let me know if you have trouble accessing it.
Thanks for explaining this to me: I was always focused on the GenX code level and not on the solution methods.

Is there anything else I should try on HiGHS' end to help it solve?

[jajhall]

I've shared the 9.6GB GenXModel.mps file via google drive to the ed.ac.uk email in your github profile. Let me know if you have trouble accessing it.

It seems to be downloading OK, thanks

Thanks for explaining this to me: I was always focused on the GenX code level and not on the solution methods.

You're welcome. I can well imagine that doing the modelling is a full-time occupation! Unfortunately, modellers can do more to help solvers, which feeds back in shorter solution times. A new JuMP feature is MathOptAnalyzer.jl, which might help you improve your model.

Is there anything else I should try on HiGHS' end to help it solve?

Nothing I can think of until I've had a look at your model

[jajhall]

I ran our new IPM solver (HiPO) on your model last night, and got the surprising and disappointing result

ERROR: Both NE and AS failed analyse phase
Summary
HiPO runtime: 370.77
Status: error in analyse phase
iterations: 0
ERROR: Hipo: Error in analyse phase
Model name : schwartz-genx
Model status : Solve error
HiGHS run time : 648.01

It's the first time that I've seen this, so I'll obviously feed this to our developer to see what he can gain from it. HiPO is very new

When I go into work I'll run the model with our first order solver on a GPU

[jajhall]

When I go into work I'll run the model with our first order solver on a GPU

It's making progress, but has run for 41149s

Back to your original point, I'm fairly sure that the stalling is due to a sparse matrix factorization taking a very long time for your model. So, I've added time-dependent logging before/after this factorization so that it's clearer where it's stalling, and some data to report if it happens: see #2530

[cfe316]

I'm running the GenX case using the same version of GenX, but a different version of Julia (and likely different versions of various packages) than I had done before. I think it's unlikely, though not impossible, that Julia version differences have caused the JuMP model to be constructed slightly differently in such a way that's it's infeasible or similar. Could that have caused the failed analysis phase?

[jajhall]

I'm running the GenX case using the same version of GenX, but a different version of Julia (and likely different versions of various packages) than I had done before. I think it's unlikely, though not impossible, that Julia version differences have caused the JuMP model to be constructed slightly differently in such a way that's it's infeasible or similar. Could that have caused the failed analysis phase?

The reaction of @filikat was that either the analyse software gives an error (quite unlikely) or the 32-bit maximum index has been exceeded. I'll run it again with more diagnostic logging.

[cfe316]

Thanks Julian!

I've left the original run (which I thought had stalled) running, and it indeed has started solving, very slowly:

   1   3.27e+02 1.38e+02   9.83433708e+06 -1.43995172e+09  5.07e+04   76115s
   2   2.86e+02 9.66e+01  -1.40360102e+05 -2.15105354e+09  4.48e+04  118789s
   3   2.69e+02 7.60e+01  -1.12213391e+07 -2.43247496e+09  4.26e+04  150059s
   4   2.54e+02 6.41e+01  -1.22939222e+07 -2.69162237e+09  4.08e+04  176865s
   5   2.46e+02 4.97e+01  -1.21672671e+07 -3.65552056e+09  3.98e+04  203275s

It looks like this is going to take a long time.

[jajhall]

Ok not bad! What sort of GPU does this run on? I'd imagine it would need to be one with quite a large memory?

GeForce RTX 4070 Ti SUPER

16 GB GDDR6X

Your presolved problem has 80M nonzeros, each requiring 12 bytes to represent it. With the constraint matrix being stored row-wise and col-wise, that's 2x12x80 MB, so 2 GB. Hence memory isn't an issue

[cfe316]

Understood: When I run this it must be the JuMP problem which uses about 200GB and the part passed to the solver becomes small.

[jajhall]

Understood: When I run this it must be the JuMP problem which uses about 200GB and the part passed to the solver becomes small.

Before presolve the LP has 172M nonzeros. This and the presolved LP are in RAM, but that's only 8GB. There are also quite a lot of vectors of size equal to the number of columns (20M - 7M after presolve) and rows (36M - 15M after presolve) so 200GB in JuMP isn't unrealistic. NB @odow

We won't be solving this model often, but it's definitely on we'll look to quote in benchmarks.

[odow]

If you are not using direct_model then there are two copies in JuMP as well.

String names also eat memory: https://jump.dev/JuMP.jl/stable/tutorials/getting_started/performance_tips/#Disable-string-names

[cfe316]

Thanks @odow for expediency I'm using an older version of GenX; I think this has been fixed recently.