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?

  • 2
    $\begingroup$ The structure of the pricing problem can add the variables into the restricted master problem with negative reduced cost. $\endgroup$ – A.Omidi May 11 at 18:55

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.

| improve this answer | |
  • $\begingroup$ When computing the cost, for a certain column/path should I then do it for each person/vehicle (fx each column could be associated with an attribute list, where the cost for for the column is represented for each person). I already implemented column generation with a single subproblem - and now I'm trying to extend it, but I think it is somewhat more difficult. $\endgroup$ – User123456789 May 11 at 20:25
  • $\begingroup$ I thought that the allocation of person/vehicle to the new shortest path is part of the subsequent RMP. Now, I am completely out of sync with what you are asking. If possible, elaborate on your question. $\endgroup$ – Divyam Aggarwal May 11 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.