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

回答済み

Krypt

2024年09月22日 23:02 編集済み

• 
• 
• 

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

関連

• VRP
• Branch-and-Price

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:20

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Mario Ruthmair

  • Gurobi Staff

  2024年10月24日 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

投稿コメントは受け付けていません。