1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The most computationally expensive aspect of this algorithm is the reconstruction of the master problem when a column is added (or sometimes removed)

By "reconstruction", do you mean that you build your restricted master problem (RMP) from scratch every time a variable is added (or removed)? One should not do that, as it takes to much time, as you have pointed out. Instead you can add the variable to the model and then set the variable coefficients afterwards. Like in this (very simple example):

#Initiate RMP
rmp=Model()
artificialVariable = rmp.addVar(vtype=GRB.CONTINUOUS, obj =1000000)
constraint = rmp.addConstr(artificialVariable >= 1)

#...

#Find a new column
cost, coefficient = solveSubproblem()
newVariable = rmp.addVar(vtype=GRB.CONTINUOUS, obj = cost)
rmp.chgCoeff(constraint, newVariable, coefficient)
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! What about removing columns? It seems that I can remove a variable by rmp.remove(variable). But what about removing it from the constraint? $\endgroup$
    – mdslt
    Nov 19 at 16:39
  • 1
    $\begingroup$ You could do rmp.remove(variable), that would remove the variable from the entire model, and hence also removev it from any constraints it was a part of. You can also set all the coefficients for the variable to 0. The latter method is the one I use when I want to remove variables due to branching in Branch-and-Price, because it is likely that I want to "add" the variable again when solving another Branch-and-Bound node. $\endgroup$
    – gmn
    Nov 20 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.