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?
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
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
Post is closed for comments.
Comments
4 comments