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 ?
-
正式なコメント
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.
投稿コメントは受け付けていません。
コメント
1件のコメント