When using column generation, can I delete a node with negative reduced cost from my subproblem?

Question

I am solving a minimization problem with a column generation procedure. The master problem is of the form $$ \min \sum_{i\in \Omega}c_i \lambda_i $$ subject to $$ \sum_{i\in \Omega \mid v \in i } \lambda_i = 1 \quad \forall v \in V $$ Columns $\lambda_i$ represent paths with nodes belonging to set $V$.

Let $\pi_v$ denote the dual variable associated with each constraint. In my subproblem, I am looking for columns that have smallest marginal cost : $$ \hat{c}_i = c_i - \sum_{v\in V, v \in i} \pi_v $$

My question is, if $\pi_v <0$, can I safely delete node $v$ from the subproblem (as passing through $v$ will increase the global cost) ? Or do I have to keep it, in case passing through $v$ is the only way to access other nodes that together have a potential negative reduced cost ?

More generally, is there a strategy to delete useless nodes or edges from the subproblem to speed up computation ?

In this article by Francois Soumis et al (a VRP variant solved with column generation), edges and nodes are eliminated heuristically from the sunproblem: [p.15, section 4.3]

They refer the reader to another paper ([14]) for the details of these "heuristics," but the paper is nowhere to be found. I am interested in such techniques as my problem is also a VRP variant (my subproblem also consists in finding some sort of shortest path).

Answer 1

If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a vertex, removing the vertex gives another path which is both feasible for the sub-problem and which corresponds to a master problem column with smaller reduced cost.

If the graph is not complete, in general you cannot delete vertices because you might even disconnect the graph. Analogously, if you have resource constraints, removing a vertex might (in the extreme case) disallow the only resource-feasible paths. Whether you can do vertex removal under special circumstances is, I think, problem-dependent.

From my experience, heuristic vertex or arc removal can give good results. Especially if your sub-problem has high complexity, say pseudo-polynomial or worse. Just make sure that you solve the sub-problem exactly (i.e., with no heuristics) at the end of the exploration of each node, to make sure that there are no more negative-reduced-cost columns.