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]

enter image description here

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

  • 2
    $\begingroup$ Search term: "reduced cost fixing" $\endgroup$ – RobPratt Apr 26 '20 at 15:59
  • $\begingroup$ Doesn't reduced cost fixing apply for the variables of the master problem (and not the pricing problem) ? $\endgroup$ – Kuifje Apr 26 '20 at 16:32
  • 2
    $\begingroup$ 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. $\endgroup$ – RobPratt Apr 26 '20 at 16:48
  • $\begingroup$ 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. $\endgroup$ – Kuifje Apr 26 '20 at 17:16

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.

  • $\begingroup$ 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 ? $\endgroup$ – Kuifje Apr 26 '20 at 20:52
  • $\begingroup$ You could delete vertices with zero reduced cost. But one such vertex, if included in the path, could give you a column with the same negative reduced cost, which covers +1 row. So you might be giving up on finding early an "interesting" column. $\endgroup$ – Alberto Santini Apr 27 '20 at 0: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.