Issue with warm-start after changing rows

Answered

Paula Fermin Cueto

• January 31, 2021 09:09
• Edited

Sometimes I need to change the variable coefficient of a constraint and then reoptimise from the previous solution. Whenever this change makes the problem primal infeasible, the dual simplex doesn't seem to start from the previous solution, but from the very beginning.

This small example in C++ illustrates the problem.

GRBEnv env = GRBEnv();
GRBModel model = GRBModel(env);

GRBVar x00 = model.addVar(0.0, 1.0, 0.0, GRB_CONTINUOUS, "x00");
GRBVar x01 = model.addVar(0.0, 1.0, 1.0, GRB_CONTINUOUS, "x01");
GRBVar x10 = model.addVar(0.0, 1.0, 0.0, GRB_CONTINUOUS, "x10");
GRBVar x11 = model.addVar(0.0, 1.0, 1.0, GRB_CONTINUOUS, "x11");

GRBConstr c0 = model.addConstr(x00 + x01 == 1, "c0");
GRBConstr c1 = model.addConstr(x10 + x11 == 1, "c1");
GRBConstr c2 = model.addConstr(x00 + x10 <= 1, "c2");

// First solve
model.optimize();

// Modify constraint (adding 2*x01 makes current solution infeas)
model.chgCoeff(c2, x01, 2);

// Second solve 
model.optimize();

I also tried setting CBasis and VBasis manually before the new solve and although it doesn't discard this basis it still doesn't start from there.

Interesting fact: if I simply add the modified constraint as a new constraint (therefore leaving the current, now redundant constraint in the model), then it does start from the previous basis when I reoptimise!

If this is the only possible workaround, I need to find a way to remove the old constraints somehow or I will have a big issue with problem size in my algorithm.

I someone can shed some light on this, it would be most appreciated.

 

0

• 

  Jaromił Najman

  Gurobi Staff

  • February 01, 2021 14:51
  • Edited

  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
• 

  Paula Fermin Cueto

  • February 01, 2021 17:44
  • Edited

  

  

  

  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

Please sign in to leave a comment.