I am a beginner to optimization and graphical models. What I understand is that a Linear Program constitutes a relaxation and hence is a lower bound of a given Integer Linear Program. I also understand that a Lagrangian relaxation is another way of relaxing and hence yields another lower bound. I understand that the Lagrangian lower bound is always at least as good as the Linear Program relaxation lower bound (Correction made after comments). What I don't understand is the following:
Is there any advantage of doing a dual decomposition of a Linear Program? I came across this tutorial/set of slides http://www.cs.cityu.edu.hk/~cheewtan/CS8292Class/Lec13.pdf where the dual (Lagrangean)decomposition of LP is done.
What is the advantage of doing so? I am thinking if I have an ILP, would it make sense to first do LP relaxation and then dual decomposition of LP? If yes, why? Why wouldn't doing a dual(Lagrangian) decomposition from an ILP directly be more beneficial as it gives a tighter lower bound?
Sorry, if the question is silly, but I seem to be confused.
First of all, the Lagrangian relaxation does not necessarily yield a tighter bound than the Linear relaxation. In some cases both relaxations yield equivalent bounds (e.g., if the matrix of constraints that are not relaxed is totally unimodular). What you can say is that the Lagrangean relaxation is always as least as good as the linear one.
On a practical level, Lagrangian relaxation is harder to implement.
This being said, the advantage of doing a Lagrangian relaxation is that, if done correctly (if relaxing the right set of constraints), it will yield a better bound and thus potentially speed up convergence.
Such decomposition methods are typically used for integer programs as you mentioned, but they also work for pure linear programs. I am not sure why you would want to do that though, as linear programs are easy to solve as they are. Perhaps it is interesting from a pure theoretical perspective.