Issue with warm-start after changing rows

Answered

Comments

2 comments

  • Jaromił Najman

    Hi Paula,

    Changing the coefficients in constraints is not guaranteed to keep the primal or dual basis feasible. Thus, the algorithm does not use a warm-start. However, adding new constraints, keeps the dual basis feasible, hence, you see the warm-start.
    A workaround for your problem could be to keep adding new constraints up to a certain point and then remove multiple redundant constraints at once via model.remove(). However, removing constraints will invalidate the current basis and destroy the warm-start for the subsequent run. You could try to provide a valid basis by using the CBasis attributes for constraints, i.e., remove only the ones which are not in the basis and construct a valid dual basis for the algorithm.

    Best regards,
    Jaromił

    1
    Comment actions Permalink
  • Paula Fermin Cueto

    Hi Jaromił, 

    Thank you very much for this clarification.

    It is going to be tricky to control the size of the problem. I really want to avoid destroying the warm-start without keeping redundant rows in the model for subsequent iterations of my algorithm. My plan to address this (and I think is consistent with your suggestion) is:

    1. Use model.chgCoeff() to change the coefficients of the constraints that would remain basic after the change (comparing the current slack and the new term added)

    2. For all other constraints, add them to the model using model.addConstr() and keep the old, now redundant ones.

    3. Reoptimise (the previous basis should be valid)

    4. Remove old, redundant constraints that are basic with model.remove() (this shouldn't invalidate the basis, as I would be removing one redundant constraint and one basic variable - the slack)

    5. For old, redundant constraints that are non basic, remove this constraint and find one non slack variable from the basis with its value at the lower bound in the previous solution and set it to non-basic. One such variable should exist, ie the vertex should be degenerate, otherwise, this redundant constraint would not have entered the basis...

    I'm still wrapping my head around all this, so please feel free to challenge any part of my reasoning!

    Best,

    Paula

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk