Getting sub-optimal solution after time limit for large LP problems

Answered

Dante Van Poucke

January 23, 2024 14:17

I have a large LP problem that takes several hours to find the optimal solution. The solution is needed in a time sensitive environment, so I would like to be able to stop the optimization at point in time and retrieve a feasible sub-optimal solution from Gurobi. Currently I am using the TimeLimit parameter but when Gurobi terminates due to the time limit no solution is found (model.SolCount== 0). Is there any way get some sub-optimal solution?

PS: The only constraints of my model are a set of mutually exclusive norm constraints, so finding a feasible solution should be trivial.

Logs:

number of variables = 10390740, number of constraints = 266730
Set parameter Threads to value 6
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19045.2))

CPU model: 13th Gen Intel(R) Core(TM) i7-1365U, instruction set [SSE2|AVX|AVX2]
Thread count: 10 physical cores, 12 logical processors, using up to 12 threads

Academic license 2432445 - for non-commercial use only - registered to da___@ugent.be
Optimize a model with 273870 rows, 10390741 columns and 50528006 nonzeros
Model fingerprint: 0xe079cdae
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 0 rows and 0 columns (presolve time = 5s) ...
Presolve removed 0 rows and 0 columns (presolve time = 14s) ...
Presolve removed 0 rows and 0 columns (presolve time = 15s) ...
Presolve removed 7140 rows and 7140 columns (presolve time = 33s) ...
Presolve removed 7140 rows and 7140 columns (presolve time = 38s) ...
Presolve removed 7140 rows and 7140 columns (presolve time = 40s) ...
Presolve removed 7140 rows and 7140 columns (presolve time = 50s) ...
Presolve removed 7140 rows and 7140 columns (presolve time = 56s) ...
Presolve removed 7140 rows and 7140 columns
Presolve time: 62.42s
Presolved: 266730 rows, 10383601 columns, 50513726 nonzeros

Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...

Related to

Comments

5 comments

Michel Soares

January 23, 2024 14:56
Hi Dante,

You should be able to access the best solution found when the optimization ends, the same way you would retrieve the solution when it finds the optimal solution. It is not clear if this is the case, but if presolve is taking a long time and you have very limited time, you may consider reducing the value of the Presolve parameter.
0

Dante Van Poucke

January 23, 2024 15:18

Hi Michel,

Thanks for you response.
In most case the presolve is not the problem, see e.g. this smaller problem below. I set the time limit to 30 seconds. After the timeout I check if there is a solution using

print(f"Solutions found? {model.SolCount}") -> log shows "Solutions found? 0"

so I would expect no solution was found. To be sure I tried to retrieve the solution like I would normally do with

model.getVarByName(f"[varname]").x

but this throws:

AttributeError: Unable to retrieve attribute 'x'

So I am not able to retrieve any sub-optimal solution.

Full log is shown below:

Set parameter Username
Set parameter WLSAccessID
Set parameter WLSSecret
Set parameter LicenseID
number of variables = 1391544, number of constraints = 72336
Set parameter Threads to value 6
Set parameter TimeLimit to value 30
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19045.2))

CPU model: 13th Gen Intel(R) Core(TM) i7-1365U, instruction set [SSE2|AVX|AVX2]
Thread count: 10 physical cores, 12 logical processors, using up to 12 threads

Optimize a model with 75240 rows, 1391545 columns and 6595704 nonzeros
Model fingerprint: 0x89f40056
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 2904 rows and 2904 columns
Presolve time: 4.98s
Presolved: 72336 rows, 1388641 columns, 6589896 nonzeros

Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...

Elapsed ordering time = 5s
Ordering time: 10.12s

Barrier statistics:
 Dense cols : 1
 AA' NZ     : 4.434e+06
 Factor NZ  : 7.560e+06 (roughly 700 MB of memory)
 Factor Ops : 8.337e+09 (less than 1 second per iteration)
 Threads    : 8

                  Objective                Residual
Iter       Primal          Dual         Primal    Dual     Compl     Time
   0   8.64118532e+01  0.00000000e+00  1.76e+03 0.00e+00  1.79e-02    23s
   1   8.94762291e+01 -2.71494429e+03  1.17e+01 3.48e-03  1.19e-03    24s
   2   8.93820253e+01 -1.69906375e+01  2.00e-15 1.80e-05  3.89e-05    25s
   3   8.55828510e+01  3.48615786e+01  2.00e-15 9.78e-06  1.85e-05    27s
   4   7.67951497e+01  5.12615496e+01  3.62e-14 4.25e-06  9.32e-06    28s
   5   7.30615169e+01  5.62575457e+01  2.29e-14 2.49e-06  6.12e-06    29s
   6   6.93874338e+01  5.94058357e+01  1.18e-14 4.32e-07  3.62e-06    30s
   7   6.73249316e+01  6.06981889e+01  6.00e-15 2.08e-07  2.39e-06    30s

Barrier performed 7 iterations in 30.32 seconds (29.88 work units)
Barrier solve interrupted - model solved by another algorithm




Stopped in 94976 iterations and 30.53 seconds (36.23 work units)
Time limit reached
Solutions found? 0
Traceback (most recent call last):
....
AttributeError: Unable to retrieve attribute 'x'

Michel Soares

January 23, 2024 17:30
Ok, let me explain a few things that can help and the challenges in having a result for this model in 30 seconds.

1. If the presolve takes the full 30 seconds, you will not have a solution within your time limit. For this last log it does not seem to be the case, but it may happen for other models. If that is a problem, you would have to change the Presolve parameter.

2. You may want to try different values for the parameter Method, so Gurobi will focus all computing power in a single algorithm, which may help you finding a solution in time.

3. There are a lot of other parameters you can experiment with to try to have a solution faster, but for this model size and time limit, it may be impossible. Try using 1 minute or more and see if you are able to retrieve a solution.
0
Riley Clement
Gurobi Staff

January 23, 2024 23:58
Hi Dante,

Michel has provided some good advice.

Ultimately though, this:

Getting sub-optimal solution after time limit for large LP problems

is not possible.

Following on from Michel's recommendation, first try setting Method=2. Barrier will typically work better on problems of this size. If you do not need a basic solution then setting SolutionTarget=1 or (alternatively Crossover=0) could potentially save a lot of time if the simplex algorithms are struggling on your LP.

- Riley
0
Dante Van Poucke

January 29, 2024 14:29
Thanks for your help, Michel and Riley!
Setting the parameters did help to reduce computation time. Unfortunately, the speedup was not high enough. I will have to resort to heuristicst to solve this problem.
0

Please sign in to leave a comment.

Comments

Didn't find what you were looking for?