# Lagrangian Bound in Column Generation

Hi,

I'm implementing Column Generation and applying stabilization using smoothing techniques mention in Pessoa 2014. Since each loop of the master problem consists of more than hundred of pricing problems, I want to speed up the convergence rate, by re-optimizing the restricted master problem every 10 solving pricing problems. What I did is as describing below:

- Solve RMP as LP problem, obtain dual values
- Apply stabilization, obtain new multiplier
- Generate pricing problem using the obtained multiplier, solve and get new column
- Repeat step 3 10 times, add new generated column to RMP, go beck to step 1 and continue for the next pricing problems

The problem with this approach is how to calculate the Lagrangian bound. The way I calculated the Lagrangian bound is by using the following formula : LB = Z_LP + sum of generated reduced cost. But following my CG process, this LB is computed by Z_LP + the sum of 10 generated columns. But I don't think this is the correct way to calculate the Lagrangian bound, since when I'm checking the log, after certain time, Z_LP of RMP become smaller than the biggest value of LB, which is incorrect because each LB is supposed to be a valid bound of the RMP with any feasible set of columns.

Are there any suggestion how to compute this Lagrangian Bound correctly ?

Please sign in to leave a comment.

## Comments

0 comments