Hi,

Can you explain what "lower bound" and "upper bound" refer to? There are more than one version of the Lagrangian decomposition algorithm, especially because it can be applied to a variety of problem structures, so understanding what your problem looks like exactly is probably important.

Your question suggests that you may need a brief tutorial on the idea of LB and UB. So, suppose you are trying to minimize an objective function (like costs in a production model). Clearly you can make some trial feasible initial solution and since it is "guess" it is providing a value for your objective that is an upper bound (you need do no worse than this value, and as the algorithm progresses your aim is to do better,,.. i,e, to find cheaper solutions). Now for the lower bound ... the idea here is to find some underestimate of the true costs that makes the problem easy to solve and determine a value that is guaranteed to be lower than the optimal solution. Think of the gap between UB and LB as a "sandwich" and you are trying to narrow that gap (make the two sides come together, by raising the LB and lowering the UB). Each new improved feasible solution lowers the UB. The trick is often to find some way to update the primal solution from "advice" provided in the lower bound (dual) variables.

A good example of the lagrangean relaxation applied to a real problem is the p-median problem. One of the early papers on this by Narula Ogbu and Samuelson is a good strong example. Let me know if this is a an example you need more help with.

Hi

I advice you to see this paper. You will find what you need.

Best regard 

http://www.rusz.rutgers.edu/mor95.pdf

Hi, a good reference on the subject is M. Guignard, Lagrangian relaxation, TOP, 2003, v 11, 151-228.

Read the attached file to get ahead with decomposition methods