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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ 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? $\endgroup$– A.OmidiAug 7 at 6:25
-
$\begingroup$ @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 $\endgroup$– fontanfAug 7 at 8:06
-
$\begingroup$ Dear @fontanf please, take a look at your mentioned email on Github. Thanks $\endgroup$– A.OmidiAug 7 at 12:32
-
$\begingroup$ @fontanf Thanks for your reply. I will read this article. $\endgroup$– XXiaAug 7 at 13:24
$\begingroup$
$\endgroup$
1
It is hard to say anything specific without knowing more about the problem, and if you are looking for practical solutions or theoretical ones. However, your description reminds me of packing/resource sharing problems. These have been studied quite a bit, often in the context of multi-commodity flow problems, but the results can be applied to a wide collection of problems. You might want to look into the 1994 and 1996 papers of Grigoriadis and Khachiyan. (https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230260202) (https://www.jstor.org/stable/3690236)
-
$\begingroup$ Thank you very much. I'm going to read this and think if it's of the same nature as my question. $\endgroup$– XXiaAug 7 at 13:26