6
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Search term: "reduced cost fixing" $\endgroup$
    – RobPratt
    Apr 26, 2020 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, 2020 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, 2020 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, 2020 at 17:16

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2020 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$ Apr 27, 2020 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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