Skip to main content

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

Answered

Comments

5 comments

  • Michel Soares
    Thought Leader

    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
    First Question
    First Comment

    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'
    0
  • Michel Soares
    Thought Leader

    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 Gurobi Staff

    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
    First Question
    First Comment

    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.