Issue with warmstart after changing rows
AnsweredSometimes 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.

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 warmstart. However, adding new constraints, keeps the dual basis feasible, hence, you see the warmstart.
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 warmstart 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 
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 warmstart 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 nonbasic. 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.
Comments
2 comments