Is warm start implicit in resolving an LP

Answered

Comments

5 comments

  • Jaromił Najman

    Hi Frederick,

    If you add an additional constraint, then the dual simplex algorithm can be warm-started. Thus, as long as you don't reset your model, Gurobi will take advantage of a warm start without you having to specify the vstart, cstart values.

    There is a very nice video explaining warm-start and other fundamentals from last year's CO@Work. The channel also has further informative videos on Optimization fundamentals and expert applications.

    Best regards,
    Jaromił

    1
    Comment actions Permalink
  • Greg

    Thank you for the valuable information, however let me clarify the following regarding the warm starts in LPs. Assuming an iterative process, where an LP is initially solved with a specific size and then it  changes size progressively. Notice that I am not resetting the model among the iterations.

    1) In every iteration only one variable (column) is added to the LP.

    2)  In every iteration only the right hand side of the constraints are changing.

    3) Both 1 and 2 happen.

    Do I have to specify the vstart values among the iterations in each case (1-3) or does the solver by default employs the optimal solution obtained in the previous iteration is some of the above cases?

    Finally, could you propose the proper method (Primal Simplex or Dual Simplex) for each case (1-3) so as the warm starts would be meaningful?

     

    Sincerely  thank you for your consideration and time,

    Gregory

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Greg,

    In all 3 cases Gurobi will take advantage of a warm start. However it depends on the situation whether Phase 1 or Phase 2 of the Simplex algorithm can be warm started.

    1. Depending on the bounds, Simplex can be warm started in Phase 1 or 2. If bounds are \(\geq 0\) or the variable is free, we can start in Phase 2.
    2. Here, we can always warm start in Phase 2.
    3. Here, it is most likely that we warm start in Phase 1.

    Note that warm starting in Phase 2 may be slightly better. Still, in general, warm starting improves performance of Simplex algorithms.

    Finally, could you propose the proper method (Primal Simplex or Dual Simplex) for each case (1-3) so as the warm starts would be meaningful?

    Since we can convert a dual basis into a primal basis and vice versa, it does not matter which algorithm you choose (except for the conversion overhead). The specific cases are all listed in the video mentioned in my previous post.

    Best regards,
    Jaromił

    1
    Comment actions Permalink
  • Greg

    Thank you Jaromił for the constructive reply. Are you aware if I have to specify the vstart values between each iteration manually or does the solver employ by default the optimal solution obtained in the previous iteration?

    Warm Regards,

    Gregory

     

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Greg,

    As long as you don't reset your model or change the coefficients of constraints making a warm start not possible, you don't have to provide vstart values and Gurobi will re-use the basis from the previous run.

    Best regards,
    Jaromił

    1
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk