I'm trying to implement column generation for an inventory-routing type model in AMPL, using CPLEX 11 as the solver. I'm finding that my pricing problem is generating columns that have been generated in previous iterations, or that were part of the initial set of columns in the restricted master problem. Is this a definite indication that I've made a mistake in formulating my problems, in my AMPL code, or is this theoretically possible? I've tried to look for examples of this in the literature, but can't find anything.
asked
AnORStudent |

If your master problem is a linear program, then it's almost surely an error in your code. The objective function in the column generation problem is typically the reduced cost of a new column in the master problem. If the reduced cost has the correct sign, the new column Be sure that your subproblem objective is the full reduced cost, which frequently includes a constant term -- or else, rather than testing the sign of the subproblem objective, test whether it is greater than (or less than, whichever is relevant) the appropriate constant.
answered
Paul Rubin ♦♦ |

As Paul says, in the linear case, you use the objective returned from the subproblem as a termination criteria. But I suspect you already know this, since you must have read up on column generation before using it. I think we need more information on what you actually do, otherwise it's hard to help. What type of restricted master and sub problem do you have ?
answered
Bo Jensen ♦ |

Update: thanks for confirming what I thought was the case - with a linear master problem I can't possibly be adding the same column multiple times. I'll look at my formulation and code carefully and if I still can't find an answer I'll post more details about the model.

It was in fact a stupid mistake in my code. I made a mistake when passing the values of the dual variables from the master problem to the pricing problem.