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

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 () 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).

• Search term: "reduced cost fixing" Apr 26 '20 at 15:59
• Doesn't reduced cost fixing apply for the variables of the master problem (and not the pricing problem) ? Apr 26 '20 at 16:32
• Yes, I was just pointing you in the general area of using reduced costs to fix variables without loss of optimality. In your particular problem, I don't think there is any justification for deleting node $v$ based solely on $\pi_v<0$. You might get more specific help if you provide more details about your subproblem. Apr 26 '20 at 16:48
• Ok, thanks. My subproblem is shortest path with resource constraints. I added a reference in my question where such heuristics are mentioned but not detailed. Apr 26 '20 at 17:16

• Thank you ! "you can delete vertices which don't decrease the reduced cost" : this is equivalent to deleting nodes $v$ for which $\pi_v <0$, right ? Also, if the master problem is of the form $Ax\ge1$, then all dual variables are non negative if i am correct, so in this case I cannot delete any nodes ? Apr 26 '20 at 20:52