LP with 26251550 rows, 1332396 columns and 177780888 nonzeros has very slow crossover

Answered

Richard Li

February 02, 2024 05:14

• 
• 
• 

I have a very large LP, with many decision variables and constraints. I am using the default crossover setting The initial barrier solution completes in a reasonable amount of time. The first two pushes finish in long, but reasonable time, but the final "cleanup" stage diverges.

I'd like to know how to make the crossover work, as I do want a basic feasible solution.

 

Is my model just too large? Is it numerical issues?

 

I've attached the log to this post. I'm still trying to figure out how to export the model but I will try to upload that tomorrow.

 

I think one highlight is this line at the end:

Iteration    Objective       Primal Inf.    Dual Inf.      Time
 11568207   -1.9721270e+01   0.000000e+00   4.427393e-01  15542s
Warning: 1 variables dropped from basis
 11569107   -2.2013593e+01   2.507379e+11   4.980957e+23  15574s

Whateve is happening after the variable gets dropped from the basis, it suddenly starts becoming wildly infeasible

Related to

• Crossover

0

• 

  Richard Li

  February 02, 2024 05:15

  • 
  • 
  • 

  Log: https://www.dropbox.com/scl/fi/js29rw7qekbgedfu5skb1/02-01-2024_01-44-27_gurobilog_expfeb1_relaxation_4block_1e-3tol.txt?rlkey=wl259nlevc83lwtj4uyoxxhi0&dl=0

  0
• 

  Mario Ruthmair

  • Gurobi Staff

  February 06, 2024 13:26

  Hi Richard,

  It is not unusual that simplex runs into issues on very large models. Barrier can solve it, but crossover (which is basically simplex) struggles to move the solution to a corner of the polytope.

  If you really need a basic solution, you can try a few parameter settings and see whether crossover improves:

  • BarHomogeneous=1
  • Crossover=1,2,3,4
  • CrossoverBasis=1
  • Quad=1
  • Presolve=0,1,2
  • Aggregate=0,1,2

  Best regards,
  Mario

  0

Please sign in to leave a comment.