Originally posted by: lbr33

I am implementing a column generation approach to my problem.

The Master Problem (MP) is initialized with some initial columns. Then, the MP is solved; the pricing subproblem is solved. Some columns with negative reduced costs are found and added to the MP. The MP is solved once again with these new columns, but the value of the objective function of MP does not change in this iteration.  Can it happen? Or does it mean that I am doing something wrong?  In the end, the method converge.

 

Yes, it can happen, if the current solution to the master problem is degenerate. The negative reduced cost ensures that the simplex algorithm will attempt to bring the new variable into the basis, but if the current solution is degenerate the new variable may enter the basis with value 0. If that happens, the dual variables in the master will change to make the reduced cost of the new variable 0, so you should be able to go back to the column generation subproblem with the new dual values and get a different column to add to the master.