MIP Start and relaxation

[Eric]

Hi All,

I have an issue with my case. I solve an MIP problem, which takes a long time (even around 1 hour) in order to root relaxation. After that, I do some operations and try to use the same solver but with a new MIP start (warm start). My challenge is that the solver again try to solve the root relaxation since I just restart (call again but not reset) it with a new MIP start solution. This is very costy and painful as the root relaxation takes along time. Is there any way to boost this process or to use the root relaxation information when I just reuse the solver?

Thank you so much,

Eric

[Sonja Mars]

Hi Eric,

Can you post a log file showing the situation?

Additionally, can you be more specific on what operations you do after the root was solved the first time? It depends on what you do, if the basic solution you have obtained from the first solve stays valid.

Thanks and best regards,
Sonja

-----------------------------------------------------------------
Dr. Sonja Mars
Gurobi Optimization

[Eric]

Hi Sonja,

I rechecked my code and I understood that the operation is independent from the solver. So I wrote another piece of code to just test this situation in a very simple way. But it seems again the solver calculates the relaxation of the problem.

*****************************************************************************************************

Optimize a model with 9203 rows, 12201 columns and 43911 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 5e+02]Enter code here...

  Objective range [1e+00, 2e+03]

  Bounds range    [1e+00, 9e+03]

  RHS range       [1e+00, 9e+03]

Found heuristic solution: objective 2.11873e+06

Presolve removed 3329 rows and 4153 columns

Presolve time: 0.10s

Presolved: 5874 rows, 8048 columns, 30046 nonzeros

Variable types: 0 continuous, 8048 integer (7656 binary)

Root relaxation: objective 1.229504e+03, 7328 iterations, 2.74 seconds

Total elapsed time = 5.05s

    Nodes    |    Current Node    |     Objective Bounds      |     Work

 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 1229.50379    0  732 2118729.00 1229.50379   100%     -    6s

Explored 0 nodes (14230 simplex iterations) in 6.01 seconds

Thread count was 1 (of 8 available processors)

Time limit reached

Best objective 2.118729000000e+06, best bound 1.230000000000e+03, gap 99.9419%

Optimize a model with 9203 rows, 12201 columns and 43911 nonzeros

Coefficient statistics:

  Matrix range    [1e+00, 5e+02]

  Objective range [1e+00, 2e+03]

  Bounds range    [1e+00, 9e+03]

  RHS range       [1e+00, 9e+03]

Found heuristic solution: objective 2.11873e+06

Presolve removed 3329 rows and 4153 columns

Presolve time: 0.07s

Presolved: 5874 rows, 8048 columns, 30046 nonzeros

Loaded MIP start with objective 56974

Variable types: 0 continuous, 8048 integer (7656 binary)

Root relaxation: objective 1.229504e+03, 6596 iterations, 2.06 seconds

Total elapsed time = 5.04s

    Nodes    |    Current Node    |     Objective Bounds      |     Work

 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 1229.50379    0  645 56974.0000 1229.50379  97.8%     -    5s

H    0     0                    55073.000000 1229.50379  97.8%     -    5s

     0     0 1236.80760    0  987 55073.0000 1236.80760  97.8%     -    7s

H    0     0                    55071.000000 1236.80760  97.8%     -    7s

     0     0 1245.13235    0 1023 55071.0000 1245.13235  97.7%     -    9s

H    0     0                    54869.000000 1245.13235  97.7%     -    9s

     0     0 1249.84144    0 1074 54869.0000 1249.84144  97.7%     -   10s

H    0     0                    45781.000000 1249.84144  97.3%     -   11s

     0     0 1251.92071    0 1101 45781.0000 1251.92071  97.3%     -   12s

H    0     0                    44675.000000 1251.92071  97.2%     -   13s

     0     0 1252.77028    0 1151 44675.0000 1252.77028  97.2%     -   14s

H    0     0                    42574.000000 1252.77028  97.1%     -   22s

Process finished with exit code -1

*******************************************************************************************************************

Thanks,

Eric

[Ed Rothberg]

We'll always re-solve the root relaxation after you modify a MIP model.  I think Sonja was thinking about the LP case, where we'll usually keep the basis, but where there are a few model modifications (those that affect the basis) that will cause it to be discarded.

Ed

[Eric]

Hi Ed,

Thank you so much for your prompt answer. In this case, I didn't modify the problem. I just run it, and then run it again with a new MIP start. Can we call a "warm start" as a modification to the problem? Does it change the information about the validity of the root relaxation?

Anyway, It is really a pain particularly in my case where the relaxation takes 10 minutes to more than 1 hour and I have to do it twice or more only by restarting from a new solution. Is there any way to save the relaxation information and reuse it again?

What would you advise?

Many thanks,

Eric

[Ed Rothberg]

A warm start restarts the optimization, so it re-solves the relaxation.

If you want to pass in a solution without stopping the optimization, use a solution callback.

Ed

[Eric]

I don't understand the relationship between relaxation and warm start and how they can affect each other. It might be helpful if you could make a bit more clear for me.
By the way, is there any recommended practice apart from "solution callback"? because I need to stop the solver and do something else and then later again call it back. Therefore it is not possible to use solution callback, I suppose.

Thanks,

Eric

[Ed Rothberg]

I don't understand the relationship between relaxation and warm start and how they can affect each other.

The only thing the MIP start does is (hopefully) provide an initial feasible solution.  Having a feasible solution can help a few things in MIP (pruning, etc.), but it doesn't fundamentally change the steps of the algorithm.  In particular, the MIP start has no effect on the root relaxation solve.  It is solved from scratch whenever you start the MIP solve over.

Ed

[Eric]

Thank you so much Ed. As you said, it has no effect on the root relaxation, I wishI would see this feature in the new release of the Gurobi solver.

By the way, I checked an example in Java for using callback but I couldn't use the callback for my case. Could you tell me how I can use the setSolution callback for this purpose, i.e. only start a solver with a feasible solution?

Eric