Speeding up Gurobi LP solver

Ongoing

Comments

8 comments

  • Jaromił Najman

    Hi Tobias,

    Given the short solution time. You should definitely try running Gurobi's Parameter Tuning Tool to find good parameters and improve performance.

    If your application does not require your optimal solution to be basic, e.g., if you are only interested in the objective value and don't re-optimize, you can turn off the Crossover algorithm.

    Best regards,
    Jaromił

    1
    Comment actions Permalink
  • Tobias Höschen

    Hi Jaromił,

    actually I already did some "research" before posting here and used the tuning tool, so this are already the tuned parameters. Is it normal that the tool only tests like 10 possible parameter assignments?

    Before tuning I had a runtime above 60 seconds, but even 40 seems to be too much since I need to compute thousands of this kind of LPS (only right hand sight change completely).

    So is the only way to speed up more computing power?

     

    Best,

    Tobias

    1
    Comment actions Permalink
  • Jaromił Najman

    Hi Tobias,

    Is it normal that the tool only tests like 10 possible parameter assignments?

    How long did the tuner run? You can set the TuneTimeLimit to, e.g., 86400, to let the tuner run for one day. It should definitely test more than 10 parameters then.

    So is the only way to speed up more computing power?

    More computing power, in particular a stronger CPU, would help. You could also search the literature for a possibly more efficient formulation of the problem.

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Tobias Höschen

    Hi Jaromil,

    Tanks for the effort and help!

    How long did the tuner run? You can set the TuneTimeLimit to, e.g., 86400, to let the tuner run for one day. It should definitely test more than 10 parameters then.

    I seht the parameter to 2 hours but it still only tested 10 parameter sets.. what did I do wrong? I attached the output at the bottom of this comment.

    More computing power, in particular a stronger CPU, would help. You could also search the literature for a possibly more efficient formulation of the problem.

    Unfortunately getting more computing power is of course not that easy. I already thought about reformulating the problems but can't find any better formulation. Originally its a MinCostFlow problem which I reformulated as a LP problem. I wish I could use the Network Simplex (which should definitely be faster) but this does not seem to be part of Gurobi.

    Best,

    Tobias

    gurobi> m.Params.TuneTimeLimit = 7200.00
    Changed value of parameter TuneTimeLimit to 7200.0
    Prev: -1.0 Min: -1.0 Max: inf Default: -1.0
    gurobi> m.tune()

    Solving model using baseline parameter set with TimeLimit=720s

    Testing candidate parameter set 1...

    Default parameters

    Solving model ...
    Optimize a model with 250000 rows, 1248000 columns and 2246000 nonzeros
    Model fingerprint: 0x45c356f2
    Coefficient statistics:
    Matrix range [1e+00, 1e+00]
    Objective range [1e+00, 1e+00]
    Bounds range [0e+00, 0e+00]
    RHS range [2e-06, 5e-01]


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


    Presolve removed 0 rows and 250000 columns
    Presolve time: 3.47s
    Presolved: 250000 rows, 998000 columns, 1996000 nonzeros


    Ordering time: 1.81s


    Barrier statistics:
    AA' NZ : 4.990e+05
    Factor NZ : 8.492e+06 (roughly 600 MBytes of memory)
    Factor Ops : 1.334e+09 (less than 1 second per iteration)
    Threads : 1

    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 8.11222789e+05 0.00000000e+00 3.61e-01 0.00e+00 1.03e+00 7s
    1 4.25192060e+05 2.32155196e+03 3.43e-01 0.00e+00 3.86e-01 8s
    2 3.17042791e+05 5.16239958e+03 2.55e-01 0.00e+00 2.87e-01 8s
    3 2.46795329e+05 7.71894020e+03 1.98e-01 0.00e+00 2.22e-01 9s
    4 2.13619279e+05 1.06218121e+04 1.70e-01 0.00e+00 1.91e-01 11s
    5 1.77845078e+05 1.37272114e+04 1.40e-01 0.00e+00 1.58e-01 12s
    6 1.58888589e+05 1.64853487e+04 1.24e-01 0.00e+00 1.39e-01 14s
    7 1.42060447e+05 1.96880484e+04 1.10e-01 0.00e+00 1.23e-01 16s
    8 1.28889097e+05 2.34057369e+04 9.78e-02 0.00e+00 1.09e-01 17s
    9 1.18836446e+05 2.62103232e+04 8.85e-02 0.00e+00 9.89e-02 18s
    10 1.11763533e+05 2.85013295e+04 8.18e-02 0.00e+00 9.13e-02 19s
    11 1.06218745e+05 3.13260634e+04 7.64e-02 0.00e+00 8.51e-02 20s
    12 1.00863907e+05 3.33343005e+04 7.10e-02 0.00e+00 7.90e-02 21s
    13 9.72788945e+04 3.57002715e+04 6.72e-02 0.00e+00 7.48e-02 22s
    14 9.46871472e+04 3.76309748e+04 6.44e-02 0.00e+00 7.17e-02 23s
    15 9.22706600e+04 3.92117125e+04 6.17e-02 0.00e+00 6.87e-02 23s
    16 8.95594596e+04 4.09635931e+04 5.86e-02 0.00e+00 6.52e-02 24s
    17 8.73508036e+04 4.25899233e+04 5.60e-02 0.00e+00 6.22e-02 25s
    18 8.54777441e+04 4.41242087e+04 5.37e-02 0.00e+00 5.96e-02 26s
    19 8.42066530e+04 4.56642628e+04 5.20e-02 0.00e+00 5.78e-02 26s
    20 8.28086215e+04 4.73624629e+04 5.02e-02 0.00e+00 5.57e-02 27s
    21 8.13847972e+04 4.90303151e+04 4.82e-02 0.00e+00 5.35e-02 28s
    22 8.02986654e+04 5.04997179e+04 4.66e-02 0.00e+00 5.18e-02 29s
    23 7.96267356e+04 5.15965009e+04 4.56e-02 0.00e+00 5.07e-02 30s
    24 7.84482130e+04 5.31267187e+04 4.37e-02 0.00e+00 4.86e-02 30s
    25 7.77130289e+04 5.42896485e+04 4.25e-02 0.00e+00 4.72e-02 31s
    26 7.68412535e+04 5.56930631e+04 4.10e-02 0.00e+00 4.55e-02 32s
    27 7.65712729e+04 5.70159876e+04 4.05e-02 0.00e+00 4.50e-02 33s
    28 7.62571487e+04 5.85439713e+04 3.99e-02 0.00e+00 4.43e-02 33s
    29 9.98000000e+08 0.00000000e+00 3.61e-01 0.00e+00 1.00e+06 35s
    30 1.98355733e+09 3.16114622e+03 3.07e-01 7.96e-13 1.72e+03 35s
    31 2.86371319e+06 3.46752720e+03 1.36e-04 2.27e-13 2.35e+00 36s
    32 5.43965170e+05 1.28895880e+05 4.39e-06 5.30e-13 3.39e-01 36s
    33 4.12211016e+05 2.26526399e+05 1.26e-06 6.19e-13 1.52e-01 37s
    34 3.65685299e+05 2.59316213e+05 5.80e-07 7.42e-13 8.69e-02 38s
    35 3.46563086e+05 2.76436859e+05 3.22e-07 8.24e-13 5.73e-02 38s
    36 3.38434810e+05 2.85601603e+05 2.20e-07 9.71e-13 4.31e-02 39s
    37 3.34409838e+05 2.90948761e+05 1.87e-07 1.14e-12 3.55e-02 39s
    38 3.32920487e+05 2.92758679e+05 1.69e-07 1.27e-12 3.28e-02 40s
    39 3.28607434e+05 2.95151173e+05 1.34e-07 1.40e-12 2.73e-02 40s
    40 3.25695783e+05 2.98414622e+05 1.02e-07 1.42e-12 2.23e-02 41s
    41 3.23206834e+05 3.00544197e+05 8.21e-08 1.57e-12 1.85e-02 42s
    42 3.20984060e+05 3.02872938e+05 6.33e-08 1.51e-12 1.48e-02 43s
    43 3.20012768e+05 3.04091271e+05 5.18e-08 1.63e-12 1.30e-02 44s
    44 3.18828221e+05 3.06592762e+05 3.87e-08 1.41e-12 1.00e-02 44s
    45 3.17498954e+05 3.07734723e+05 2.83e-08 1.56e-12 7.99e-03 45s
    46 3.16878055e+05 3.08798780e+05 2.32e-08 1.60e-12 6.61e-03 46s
    47 3.16242854e+05 3.09874783e+05 1.78e-08 1.42e-12 5.21e-03 47s
    48 3.15733955e+05 3.10554745e+05 1.33e-08 1.44e-12 4.24e-03 47s
    49 3.15420616e+05 3.11178954e+05 1.04e-08 1.47e-12 3.47e-03 48s
    50 3.15215736e+05 3.11920291e+05 9.10e-09 1.68e-12 2.70e-03 49s
    51 3.15013535e+05 3.12386262e+05 1.47e-08 1.96e-12 2.15e-03 50s
    52 3.14845842e+05 3.12863555e+05 1.09e-08 2.13e-12 1.63e-03 50s
    53 3.14584943e+05 3.13357740e+05 6.28e-09 2.18e-12 1.00e-03 51s
    54 3.14536416e+05 3.13633779e+05 2.60e-08 2.04e-12 7.40e-04 52s
    55 3.14463247e+05 3.13874266e+05 1.62e-08 2.01e-12 4.83e-04 53s
    56 3.14406205e+05 3.14033715e+05 6.89e-09 2.05e-12 3.04e-04 53s
    57 3.14383776e+05 3.14271126e+05 3.78e-07 2.88e-12 9.35e-05 54s
    58 3.14362393e+05 3.14348789e+05 1.27e-06 2.45e-12 1.10e-05 55s
    59 3.14358635e+05 3.14358082e+05 3.85e-07 2.05e-12 4.60e-07 56s
    60 3.14358140e+05 3.14358123e+05 9.83e-09 1.82e-12 1.42e-08 56s
    61 3.14358125e+05 3.14358125e+05 1.15e-10 1.81e-12 2.79e-13 57s

    Barrier solved model in 61 iterations and 56.66 seconds
    Optimal objective 3.14358125e+05

    Crossover log...

    44926 DPushes remaining with DInf 0.0000000e+00 58s
    0 DPushes remaining with DInf 0.0000000e+00 59s

    248999 PPushes remaining with PInf 0.0000000e+00 60s
    246440 PPushes remaining with PInf 0.0000000e+00 60s
    74861 PPushes remaining with PInf 0.0000000e+00 65s
    0 PPushes remaining with PInf 0.0000000e+00 69s

    Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 69s

    Iteration Objective Primal Inf. Dual Inf. Time
    293928 3.1435812e+05 0.000000e+00 0.000000e+00 70s

    Solved with barrier
    Solved in 293928 iterations and 69.74 seconds
    Optimal objective 3.143581249e+05

    -------------------------------------------------------------------------------
    Begin tuning (baseline runtime 69.85s)...
    -------------------------------------------------------------------------------

    Testing candidate parameter set 2...

    Method 2

    Solving model ... runtime 40.86s

    Improvement found:
    baseline: runtime 69.85s
    improved: runtime 40.86s
    Total elapsed tuning time 111s (7089s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 3...

    Method 1

    Solving model ... runtime 51.08s+

    Progress so far:
    baseline: runtime 69.85s
    best: runtime 40.86s
    Total elapsed tuning time 162s (7038s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 4...

    Method 0

    Solving model ... runtime 51.17s+

    Progress so far:
    baseline: runtime 69.85s
    best: runtime 40.86s
    Total elapsed tuning time 213s (6987s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 5...

    Method 2
    PreDepRow 0

    Solving model ... runtime 40.89s

    Progress so far:
    baseline: runtime 69.85s
    best: runtime 40.86s
    Total elapsed tuning time 254s (6946s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 6...

    Method 2
    AggFill 10

    Solving model ... runtime 41.49s

    Progress so far:
    baseline: runtime 69.85s
    best: runtime 40.86s
    Total elapsed tuning time 296s (6904s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 7...

    Method 0
    Presolve 1

    Solving model ... runtime 51.08s+

    Progress so far:
    baseline: runtime 69.85s
    best: runtime 40.86s
    Total elapsed tuning time 347s (6853s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 8...

    NormAdjust 1

    Solving model ...

    Tuning Interrupted

    -------------------------------------------------------------------------------

    Tested 7 parameter sets in 398.06s

    Baseline parameter set: runtime 69.85s

    Default parameters

    # Name 0 Avg Std Dev
    0 Model_cop 69.85s 69.85s 0.00

    Improved parameter set 1 (runtime 40.86s):

    Method 2

    # Name 0 Avg Std Dev
    0 Model_cop 40.86s 40.86s 0.00
    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Tobias,

    The line

    Tuning Interrupted

    indicates that the tuner has been manually interrupted either by the user or by the system. Is it possible that the process is getting killed by the system, e.g., due to time constraints or memory limits on the cluster/machine?

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Tobias Höschen

    Hi Jaromil,

    I definetly didn't interrupt the process but also am not aware of any time constraints for my system (macOS). I just tried the tuning on a smaller instance and it also interrupts after a short amount of time (memory and or time shouldn't be the reason here I guess).

    Best Tobias

    Solving model using baseline parameter set with TimeLimit=720s

    Testing candidate parameter set 1...

    Default parameters

    Solving model ...
    Optimize a model with 65536 rows, 326656 columns and 587776 nonzeros
    Model fingerprint: 0xc96b4514
    Coefficient statistics:
    Matrix range [1e+00, 1e+00]
    Objective range [1e+00, 1e+00]
    Bounds range [0e+00, 0e+00]
    RHS range [1e+01, 4e+03]

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

    Presolve removed 0 rows and 65536 columns
    Presolve time: 0.72s
    Presolved: 65536 rows, 261120 columns, 522240 nonzeros

    Ordering time: 0.38s

    Barrier statistics:
    AA' NZ : 1.306e+05
    Factor NZ : 1.986e+06 (roughly 150 MBytes of memory)
    Factor Ops : 1.861e+08 (less than 1 second per iteration)
    Threads : 1

    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 7.49465855e+08 0.00000000e+00 9.79e+02 0.00e+00 3.65e+03 2s
    1 2.05908410e+08 2.32482480e+04 5.35e+02 0.00e+00 7.02e+02 2s
    2 6.05163674e+07 6.47378451e+04 1.47e+02 0.00e+00 2.05e+02 2s

    Barrier performed 2 iterations in 2.38 seconds
    Barrier solve interrupted - model solved by another algorithm

    Solved with dual simplex
    Solved in 4837 iterations and 2.40 seconds
    Optimal objective 3.163225264e+05

    -------------------------------------------------------------------------------
    Begin tuning (baseline runtime 2.43s)...
    -------------------------------------------------------------------------------

    Testing candidate parameter set 2...

    Method 2

    Solving model ... runtime 3.06s+

    Total elapsed tuning time 6s (7194s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 3...

    Method 1

    Solving model ... runtime 1.62s

    Improvement found:
    baseline: runtime 2.43s
    improved: runtime 1.62s
    Total elapsed tuning time 7s (7193s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 4...

    Method 0

    Solving model ... runtime 1.33s

    Improvement found:
    baseline: runtime 2.43s
    improved: runtime 1.33s
    Total elapsed tuning time 8s (7192s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 5...

    Method 0
    SimplexPricing 3

    Solving model ... runtime 1.48s

    Progress so far:
    baseline: runtime 2.43s
    best: runtime 1.33s
    Total elapsed tuning time 10s (7190s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 6...

    Method 0
    PreDepRow 0

    Solving model ... runtime 1.33s

    Progress so far:
    baseline: runtime 2.43s
    best: runtime 1.33s
    Total elapsed tuning time 11s (7189s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 7...

    Method 0
    AggFill 10

    Solving model ... runtime 1.36s

    Progress so far:
    baseline: runtime 2.43s
    best: runtime 1.33s
    Total elapsed tuning time 13s (7187s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 8...

    Method 0
    Presolve 1

    Solving model ... runtime 1.47s

    Progress so far:
    baseline: runtime 2.43s
    best: runtime 1.33s
    Total elapsed tuning time 14s (7186s remaining)

    -------------------------------------------------------------------------------

    Testing candidate parameter set 9...

    NormAdjust 1

    Solving model ...

    Tuning Interrupted

    -------------------------------------------------------------------------------

    Tested 8 parameter sets in 15.90s

    Baseline parameter set: runtime 2.43s

    Default parameters

    # Name 0 Avg Std Dev
    0 Model_cop 2.43s 2.43s 0.00

    Improved parameter set 1 (runtime 1.33s):

    Method 0

    # Name 0 Avg Std Dev
    0 Model_cop 1.33s 1.33s 0.00
    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Tobias,

    The smaller problem still requires a quite considerable amount of memory

    roughly 150 MBytes of memory

    for the Barrier algorithm. Could you double check whether memory is indeed not a problem?

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Tobias Höschen

    Hi Jaromil,

    as far as I understand there shouldn't be any memory issues (see picture).

    Or am I missing something?

    Best,

    Tobias

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk