# Combination of lagrangian relaxation and column generation

I am solving an integrated scheduling problem and have dealt with coupling constraints using Lagrangian relaxation to decompose the problem into two separate problems. However, it is still difficult to solve the two decomposed problems directly using the solver. Based on the structure and nature of the problems, the column generation algorithm can be used to solve them separatly, but I have not found in the relevant literature that the column generation algorithm can be used to solve Lagrangian subproblem for example, I would like to ask if this combination of Lagrangian relaxation and column generation algorithm can be used?

In theory, nothing forbids it.

I don't remember seeing any such example in the scientific literature. But here is an example of an algorithm using nested column generation, i.e. the pricing subproblem is solved by column generation as well:

Vanderbeck F (2001) A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem. Management Science 47:864–879. https://doi.org/10.1287/mnsc.47.6.864.9809

Just be careful that usually, column generation based algorithms are not the fastest ones, while many Lagrangian subproblems need to be solved.

There should also be a couple of possible optimizations such as keeping a common column pool for all subproblems.

• Dear @fontanf, Would you please, w.r.t the fact that the Lagrangian relaxation cannot guarantee to find a feasible solution, at least finding a feasible solution highly depends on the LR heuristic, is it reasonable to use that as the solving process on the pricing problem? Aug 7 at 6:25
• @A.Omidi Lagrangian relaxation, as well as column generation procedures, solve relaxations of the problem. They can both be embedded inside a branch-and-bound algorithm to get exact algorithms. For an exact branch-and-bound based on column generation (branch-and-price), the pricing problem must be solved exactly at some point. For a column generation based heuristic, having an exact pricing is not required. One needs to find a good compromise between resolution time and solution quality Aug 7 at 8:06
• Dear @fontanf please, take a look at your mentioned email on Github. Thanks Aug 7 at 12:32