Getting suboptimal solution after time limit for large LP problems
AnsweredI 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 suboptimal 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 suboptimal 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) i71365U, instruction set [SSE2AVXAVX2]
Thread count: 10 physical cores, 12 logical processors, using up to 12 threads
Academic license 2432445  for noncommercial 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...

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 
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 usingprint(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 suboptimal 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) i71365U, instruction set [SSE2AVXAVX2]
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.79e02 23s
1 8.94762291e+01 2.71494429e+03 1.17e+01 3.48e03 1.19e03 24s
2 8.93820253e+01 1.69906375e+01 2.00e15 1.80e05 3.89e05 25s
3 8.55828510e+01 3.48615786e+01 2.00e15 9.78e06 1.85e05 27s
4 7.67951497e+01 5.12615496e+01 3.62e14 4.25e06 9.32e06 28s
5 7.30615169e+01 5.62575457e+01 2.29e14 2.49e06 6.12e06 29s
6 6.93874338e+01 5.94058357e+01 1.18e14 4.32e07 3.62e06 30s
7 6.73249316e+01 6.06981889e+01 6.00e15 2.08e07 2.39e06 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'0 
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 
Hi Dante,
Michel has provided some good advice.
Ultimately though, this:
Getting suboptimal 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 
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
5 comments