Enforcing arc (a,b)=1 in branch and price algorithm for routing problem

Answered

Krypt

September 22, 2024 23:02 Edited

• 
• 
• 

I am trying to solve a vehicle routing problem using a branch and price algorithm. At the restricted master problem  (RMP), we consider two branches: we enforce an arc (a,b)=0 and  (a,b)=1 (I am following the method described in here page 41). (a,b)=0 can be enforced pretty easily, but I am facing difficulty in enforcing (a,b)=1. This is because my solution in the RMP sometimes looks like this:

[x,y,z,a,b] = 0.5

[z,a,b,x,y] = 0.5

That is, I don't get a single path involving (a,b)=1, I get multiple paths involving (a,b) as fractional summing to 1, which is not what I intended. I tried formulating the RMP differently using penalty method (if (a,b) is used more than once, we penalize) and using the routes involving (a,b) as integer variables that sum to 1. But on both occasions the RMP does not stay a LP, which is essential because I need the dual variables from the RMP to calculate the reduced cost in the subproblem and enter newly generated routes into the master problem.

Note: The reference that I mentioned applies branching on the subproblem. If I am not wrong, it is possible to apply branching on either the master or subproblem. Even if I branch on the subproblem, the problem I am facing will remain. There may be more than one eligible route (like those I mentioned above) that will be added to the master problem, and we might still end up with fractional results like before.
  [1]: https://orbi.uliege.be/bitstream/2268/227844/1/thesis_Michelini_print.pdf

Related to

• VRP
• Branch-and-Price

0

• 

  Mario Ruthmair

  • Gurobi Staff

  October 24, 2024 14:59

  Hi Krypt,

  Sometimes, people add binary arc variables x(a,b) that are actually not needed in a route formulation. But you can do some stuff with them, e.g., branching, additional cuts, etc.
  Of course, you need to relate them with your route variables (here I call them \lambda):

  x(a,b) == sum_{r: (a,b) \in r} \lambda_r, \forall arcs (a,b)

  Then, you can branch on the x(a,b) variables.

  Alternatively, there are other branching schemes for VRPs, for example, Ryan-Foster branching.

  Best regards,
  Mario

  0

Please sign in to leave a comment.