Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I can't get my head around how to implement different subproblems in a column generation procedure with only one master problem.
Say the computer found a resource constraint shortest path for each unique subproblem at some iteration in the column generation procedure. Then what? Should all shortest paths be added to the set of paths? And when the path(s) is/are added to the restricted master problem, how does the computer know exactly which person/vehicle to allocate the path?
Adding multiple columns (in your case, paths) with negative reduced costs instead of a single column with most negative reduced cost is called multiple pricing and is useful in problems that require large-number of CG-iterations to achieve an exact/near-optimal LP-bound.
Moreover, you need to solve as many subproblems as you could possibly extract from the Dantzig-Wolfe decomposition of the LP-relaxation of the master problem.
Also, it is not necessary that if a subproblem did not result in a new column (with negative reduced cost) in some CG-iteration then it won't be useful again in any subsequent CG-iteration. Check the answer.
When the new paths are added to the RMP, the computer will allocate these paths to the person/vehicle according to the new primal-solution which you will get after solving the updated RMP.
