0
$\begingroup$

The following is based on my understanding, which may have flaws, so please correct me if I claim something wrong.

When solving VRPs with Branch-and-Price, one can enforce integrality by branching on arcs. When doing that, enforcing branching on arcs can be done either by adding constraints in the restricted master problem, or by removing infeasible columns and remove arc(s) from the graph used when solving the pricing problem.

In my Branch-and-Price implementation, I have used the former approach to enforce branching on arcs. I know that by doing that I miss a potential speedup that can be gained by reducing the number of arcs in the subproblem graph. Someone told me that I can remove arcs from the graph, even if I enforce branching by adding constraints to the restricted master problem. I find that a bit strange, since the dual variables from the added constraints then do not matter.

So my question is: can you reduce the graph by removing arcs if branching on arcs is enforced by adding constraints to the reduced master problem?

Additionally, what are the pros and cons of the two different approaches to enforce branching on arcs?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Removing arcs in the graph is effective only for one branch (arc <= 0). You can certainly impose this constraint in the master and also remove the arc from the graph. Although removing an arc can still be useful to speed up pricing, the impact is minimal because the number of arcs removed (which is no greater than the current tree depth) is much smaller than the total number of arcs. For removing arcs from the graph, using reduced cost fixing (i.e., arc elimination using reduced costs) is much more efficient.

The other branch (arc >= 1) poses a significant challenge when imposing it in the pricing; it increases the complexity of the pricing problem. Simply removing corresponding columns from the master is not sufficient, as these columns might be generated again. Therefore, I prefer branching by adding constraints in the master.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer! I the <=0 case, what about the dual variable associated with the constraint that limits the usage of the arc to zero? If the arc is removed, then it is irrelevant what the value of that dual variable is? That seems a bit strange to me. Would the other dual variables remain unaffected if this constraint were removed along with the infeasible routes (those utilizing the arc) from the RMP? $\endgroup$
    – gmn
    Commented Mar 27 at 8:12
  • 1
    $\begingroup$ In the <= 0 case, you can fix the arc variable in the pricing problem to zero. So, the dual value of the <= 0 master constraint can be just ignored, as anyway this value is multiplied by zero when computing the objective value of any feasible pricing problem solution. $\endgroup$
    – Ruslan Sadykov
    Commented Mar 27 at 13:38

Your Answer

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

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