Partially modify LHS of a constraint set?
Answered
I 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 non-zero 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