Partially modify LHS of a constraint set?
AnsweredI have implemented a column generation algorithm in Gurobi in Python. The most computationally expensive aspect of this algorithm is the reconstruction of the master problem when a column is added (or sometimes removed). For example, a sample constraint set for my master problem is as follows:
mdl_master.addConstrs((gp.quicksum((A[s][i]  B[s][i]) * chi[s] for s in s_set) >= E[i] for i in i_set), name='cst')
where `A`
and `E`
represent parameters of the master problem, `chi`
is a continuous decision variable, and `s`
is the index of columns.
Given that new columns can be added to the master problem or some unused columns can be eliminated, how do you suggest I reduce the computational cost of building such constraints in an iterative algorithm like column generation? Would it be possible and beneficial to partially modify the LHS of such a constraint set instead of building it from scratch? If so, how?

Hi Amirhossein,
Indeed, we strongly recommend updating your model in place without rebuilding it from scratch. You can do this similar to the following:
 Add the new column/variable to the model via mdl_master.addVar().
 Iterate through the relevant constraints (mdl_master.addConstrs() returns a tupledict of constraints indexed by i).
 In all constraints where the new variable should have a nonzero coefficient, change the coefficient via mdl_master.chgCoeff(). If you do nothing for a constraint, then the new variable automatically has a coefficient of zero.
Best regards,
Mario0 
Thanks a lot, Mario. Got it but have another question. What if I want to remove a column from the restricted master problem (removing the variable itself and from all constraints)? It seems that I can remove a variable by rmp.remove(). But what about removing it from the constraint?
0
Please sign in to leave a comment.
Comments
3 comments