Providing integer start solution drastically increases root relaxation computation time

Answered

Comments

7 comments

  • Jaromił Najman

    HI Hendrik,

    Could you also attach the first lines of the LOG file showing the model statistics, i.e., number of rows, columns, nonzeros, and the coefficient ranges?

    It looks like the barrier algorithm converges to a better starting basis for the root simplex without a starting point provided by you. This can be seen by the fact that the primal and dual infeasibility is 0 after crossover.

    In the second optimization run, the simplex algorithm makes only little progress. This is most likely caused by numerical issues. The provided feasible point looks suspicious, because the objective value is in the order of magnitude of 1e-16 which is at the border of numerical precision. You could try setting the NumericFocus parameter to 3 in order to switch to Quad precision.

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Hendrik Weber

    Hello Jaromił,

    Thank you for your immediate answer.

    Here are the "first parts" of the output logs. Please excuse the lack of formatting:

    ________________________________

    Without providing incumbent:

    Academic license - for non-commercial use only
    Changed value of parameter Method to 2
    Prev: -1 Min: -1 Max: 5 Default: -1
    Changed value of parameter TimeLimit to 7200.0
    Prev: inf Min: 0.0 Max: inf Default: inf
    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
    Optimize a model with 461198 rows, 1025792 columns and 1654390 nonzeros
    Model fingerprint: 0x7bf81dfa
    Variable types: 879120 continuous, 146672 integer (146520 binary)
    Coefficient statistics:
    Matrix range [8e-01, 1e+03]
    Objective range [1e+00, 2e+00]
    Bounds range [1e+00, 1e+00]
    RHS range [8e-01, 2e+03]
    Warning: Completing partial solution with 142112 unfixed non-continuous variables out of 146672
    User MIP start did not produce a new incumbent solution
    Processed MIP start in 29.32 seconds
    Presolve removed 301223 rows and 948223 columns
    Presolve time: 2.32s
    Presolved: 159975 rows, 77569 columns, 400505 nonzeros
    Variable types: 21973 continuous, 55596 integer (55444 binary)
    Root barrier log...
    Ordering time: 1.28s
    Barrier statistics:
    AA' NZ : 9.263e+05
    Factor NZ : 9.350e+06 (roughly 170 MBytes of memory)
    Factor Ops : 1.441e+09 (less than 1 second per iteration)
    Threads : 5
    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 1.19956271e+05 -7.48098707e+06 1.30e+04 4.16e-02 1.01e+03 34s
    1 5.90840962e+04 -7.30871198e+06 6.33e+03 1.54e+00 4.92e+02 34s
    2 8.57411424e+03 -5.75228656e+06 8.34e+02 3.13e-13 7.67e+01 35s
    3 1.95144575e+03 -3.06077864e+06 9.78e+01 2.77e-13 1.57e+01 35s
    4 1.35946248e+03 -1.30934119e+06 2.65e+01 7.82e-14 5.31e+00 35s
    5 1.17767629e+03 -4.17406611e+05 3.13e+00 1.60e-14 1.44e+00 35s
    6 1.11429215e+03 -3.47237146e+04 7.89e-03 7.77e-15 1.18e-01 35s
    7 8.23730095e+02 -7.98982561e+03 1.78e-15 4.86e-15 2.86e-02 35s
    8 7.13524079e+02 -5.75316639e+03 8.88e-16 3.49e-15 2.10e-02 35s
    9 5.70298488e+02 -3.69088225e+03 8.88e-16 3.50e-15 1.38e-02 36s
    10 2.85950835e+02 -2.82962059e+03 1.73e-14 2.82e-15 1.01e-02 36s
    11 2.05472256e+02 -1.82040584e+03 1.47e-14 3.48e-15 6.58e-03 36s
    12 1.16846899e+02 -1.03591392e+03 3.38e-14 3.46e-15 3.74e-03 36s
    13 7.31383741e+01 -7.55502936e+02 3.02e-14 2.46e-15 2.69e-03 36s
    14 7.54585968e+01 -6.98995912e+02 4.00e-14 2.21e-15 2.52e-03 36s
    15 6.55344200e+01 -5.08882670e+02 3.73e-14 3.05e-15 1.87e-03 36s
    16 6.11817809e+01 -2.96540922e+02 4.13e-14 2.15e-15 1.16e-03 37s
    17 3.40979452e+01 -2.58952313e+02 1.54e-13 1.65e-15 9.52e-04 37s
    18 1.23292121e+01 -1.85618205e+02 1.75e-13 1.92e-15 6.43e-04 37s
    19 1.41522634e+00 -7.44283201e+00 4.35e-13 2.52e-15 2.88e-05 37s
    20 6.19825067e-04 -3.41164362e-02 3.35e-13 2.24e-15 1.13e-07 37s
    21 6.23613589e-10 -3.43178975e-08 3.16e-13 2.80e-15 1.13e-13 37s
    22 6.23613589e-13 -3.43179045e-11 5.28e-15 2.69e-15 1.13e-16 37s
    Barrier solved model in 22 iterations and 37.44 seconds

    ________________________________

    With providing incumbent:

    Academic license - for non-commercial use only
    Changed value of parameter Method to 2
    Prev: -1 Min: -1 Max: 5 Default: -1
    Changed value of parameter TimeLimit to 7200.0
    Prev: inf Min: 0.0 Max: inf Default: inf
    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
    Optimize a model with 461198 rows, 1025792 columns and 1654390 nonzeros
    Model fingerprint: 0x45c0f276
    Variable types: 879120 continuous, 146672 integer (146520 binary)
    Coefficient statistics:
    Matrix range [8e-01, 1e+03]
    Objective range [1e+00, 2e+00]
    Bounds range [1e+00, 1e+00]
    RHS range [8e-01, 2e+03]
    User MIP start produced solution with objective 177 (1.19s)
    Loaded user MIP start with objective 177
    Processed MIP start in 1.27 seconds
    Presolve removed 301223 rows and 948223 columns
    Presolve time: 3.60s
    Presolved: 159975 rows, 77569 columns, 400505 nonzeros
    Variable types: 21973 continuous, 55596 integer (55444 binary)
    Root barrier log...
    Ordering time: 1.38s
    Barrier statistics:
    AA' NZ : 9.263e+05
    Factor NZ : 9.350e+06 (roughly 170 MBytes of memory)
    Factor Ops : 1.441e+09 (less than 1 second per iteration)
    Threads : 6
    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 1.19956271e+05 -7.48098707e+06 1.30e+04 4.16e-02 1.01e+03 7s
    1 5.90840962e+04 -7.30871198e+06 6.33e+03 1.54e+00 4.92e+02 7s
    2 8.57411424e+03 -5.75228656e+06 8.34e+02 1.42e-13 7.67e+01 7s
    3 1.95144575e+03 -3.06077864e+06 9.78e+01 1.71e-13 1.57e+01 8s
    4 1.35946248e+03 -1.30934119e+06 2.65e+01 1.28e-13 5.31e+00 8s
    5 1.17767629e+03 -4.17406611e+05 3.13e+00 2.84e-14 1.44e+00 8s
    6 1.11429215e+03 -3.47237146e+04 7.89e-03 7.11e-15 1.18e-01 8s
    7 8.23730095e+02 -7.98982561e+03 9.71e-16 4.25e-15 2.86e-02 8s
    8 7.13524079e+02 -5.75316639e+03 1.03e-15 3.86e-15 2.10e-02 8s
    9 5.70298488e+02 -3.69088225e+03 1.33e-15 3.26e-15 1.38e-02 9s
    10 2.85950835e+02 -2.82962059e+03 2.66e-14 2.95e-15 1.01e-02 9s
    11 2.05472256e+02 -1.82040584e+03 2.26e-14 2.99e-15 6.58e-03 9s
    12 1.36040219e+02 -1.31022761e+03 2.40e-14 2.14e-15 4.70e-03 9s
    13 7.52613359e+01 -9.77724825e+02 1.95e-14 3.01e-15 3.42e-03 9s
    14 9.12240663e+01 -5.92703692e+02 4.80e-14 2.52e-15 2.22e-03 9s
    15 7.11321956e+01 -3.88181946e+02 4.53e-14 2.39e-15 1.49e-03 9s
    16 5.37593403e+01 -1.48658910e+02 5.82e-14 3.80e-15 6.57e-04 10s
    17 7.99438021e-01 -1.81588262e+01 2.70e-13 1.94e-15 6.16e-05 10s
    18 8.60674623e-04 -5.03211627e-02 3.42e-13 3.20e-15 1.66e-07 10s
    19 8.65886527e-10 -5.12831888e-08 3.18e-13 2.44e-15 1.69e-13 10s
    20 8.69320488e-16 -5.14905842e-14 4.68e-15 1.78e-15 1.70e-19 10s
    Barrier solved model in 20 iterations and 10.23 seconds

    _____________________________________________

    We know for a fact that the provided integer solution is not very good, we are still working on improving the heuristic solution. This was simply intended as a proof of concept. 

    I will try to switch to quad precision as you suggested.

    I did not expect the provided start solution to also have an impact on the computation time "before the branching". I thought the provided incumbent would simply be used for pruning during branch-and-bound.

    Is there somehow a way to "ignore" the provided integer solution until we start the actual branching? A workaround that I could think of is using callbacks.

    Thank you so much for your help!

    Hendrik

     

     

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Hendrik,

    Providing the solution later via a callback would be the way to go in this case. You can achieve this via the cbSetSolution() function in a MIPNODE callback.

    >I did not expect the provided start solution to also have an impact on the computation time "before the branching". I thought the provided incumbent would simply be used for pruning during branch-and-bound.

    This is a rather minor detail which in general should not have much impact except in cases with shaky numerics (as seems to be the case here).

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Hendrik Weber

    Hello Jaromił,

    thank you so much for your help.

    Yes, we have encountered cases in the computational study where we were prompted with "Warning: Markowitz tolerance tightened to...".

    The coefficient range of 4 orders of magnitude in the model seems very reasonable. We have not yet been able to identify where the numerical issues are introduced.

    We will look further into it, also considering this here: http://files.gurobi.com/Numerics.pdf 

    In case you have any other hints or directions you can point us to: It is highly appreciated!

    Thanks again for your help and patience!

    Hendrik

     

     

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Hendrik,

    Please note that the coefficient ranges are only an indicator for numerical issues. The ranges may be very small and the underlying problem could still suffer from numerical issues, e.g., if the coefficient matrix is near to singular, has almost linearly dependent rows or similar.

    You could also try upgrading to our latest version 9.1.

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Mark Stone

    Jaromił Najman  wrote "You could try setting the NumericFocus parameter to 3 in order to switch to Quad precision."

    Does NumericFocus value of 2 also use Quad precision, and if so, is it used less than for value of 3? What about value of 1?

     

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Mark,

    The NumericFocus parameter automatically controls the quad precision computation, the Markowitz Tolerance, and a few others. Since NumericFocus automatically decides whether to use quad precision, it is possible that setting the value to 2 or 1 will also enable it, where a higher value favors the enabling more. If you want to explicitly enable Quad Precision, you can set the Quad parameter.

    For more information, please have a look at our Guidelines for Numerical Issues and the Webinar on Avoiding Numerical Issues in Optimization.

    Best regards,
    Jaromił

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk