Questions for the future

Column generation algorithm

So I realized that column generation algorithm is a useful approach in solving shortest path problem with resource constraints (SPPRC). Then the questions are;
1-1. How to generate the reduced cost paths for the sub-problem that will generate columns for the master problem.
1-2. A dynamic programming approach such as Dijkstra's SP algorithm is not feasible for SPPRC? even for generating paths in the sub-problem?
2.  When thinking of its application to maximum covering location problems (MCLP) or more specifically my problem (deviation-flow refueling location model: DFRLM),
- the master problem becomes a set covering with cardinality (p) constraint after MCLP was reformulated as a modified p-median problem and,
- the sub-problem may be solved by a Lagrangian relaxation method.  I wanted emphasize though that Lagrangian relaxation approach would be possible only if we already know all the 'candidate' paths.
- Good news is that the modified PMP could take any functional form for specifying the cost coefficients. This implies that the column generation approach can be easily applicable to the FILM with deviation case. Again if there are two types of weights in the network, then solving a SPPRC in advance as a pre-processing may be required.

- tentative algorithm
1. locate p facilities
2. Modify the network so that for each node in p, set node label: - vehicle range. This implies resource will be replenished at the nodes being evaluated.
3. SPPRC on the modified network.
//reduced cost paths....

How about solving master problem in the MCLP + column generation?

(review of the theoretic fundamental of column generation algorithm)
Reduced cost sigma(j) = c(j) - phi *A(j), where phi is the vector of optimal dual variables.
In the case of stock cutting problems, for a column x(j) >=0 to be eligible to enter the basis of a min problem, sigma(j) has to be negative. The sub-problem of finding the possible solution with the most negative reduced cost can be formulated as a special mixed integer programming problem, a knapsack problem.

However, in the case of PMP, to solve it by a Lagrangian relaxation, first it was relaxed using surrogates, which could be an arbitrarily number but here we made sure it is the same as the vector of optimal dual variables(phi).

Another set of questions branches out from here: relationship between Lagrangian relaxation and column generation (Dantzig-Wolfe decomposition). In fact, Huisman et al (2005) showed the two ways in which the two techniques can be combined efficiently. To be more specific, Lagrangian relaxation can be applied to the master problem to approximate the optimal values of the dual variables or it can be used on the original compact formulation of the problem to generate good columns.
In sum, this approach is based on the observation that when the Lagrangian relaxation is obtained by dualizing exactly those constraints that are the linking constraints in the Dantzig-Wolfe reformulation, the same sub-problem results. Consequently, the solutions generated by the Lagrangian sub-problems can also be added as new columns to the master problem.
This approach is applicable to FILM with deviation case with a stringent assumption of shortest distance path. In other word, it couldn't be applied when there are resource constraints such as vehicle range in traveling along paths. If FRLM or DFRLM are to be solved using a column generation algorithm more specifically in the framework of resource-constrained shortest path problem, additional modeling consideration may be required. Given that SPPRC associates an edge with a decision variable whereas (D)FRLM assigns a decision variable to a node, we would need to model the relationship between an edge and a node where a facility is located.

Vehicle routing problem with time window is related to my questions? At least the formulation that I saw had a constraint that ensures one vertex is preceding the other.