<div dir="ltr"><div><div><div><div><div><div><div><div><div>Dear Scipiers,<br><br></div>I'm trying to implement a Branch-Cut-and-Price for the Capacitaded Vehicle Routing Problem, more specifically, I'm trying to code the algorithm described here (<a href="https://link.springer.com/article/10.1007/s10107-005-0644-x">https://link.springer.com/article/10.1007/s10107-005-0644-x</a>) using the SCIP framework. Basically, the idea here is to use q-routes for pricing (same as routes, but allows vertex repetition), and the CVRPSEP(<a href="http://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep/">http://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep/</a>) package for cutting.<br><br></div>Now, the problem is that, after inserting a column (which represents a qroute), The same column arise in the next iteration with negative reduced cost, and I insert it again, again, and again... From my understanding, after inserting a column, it should have reduced cost >= 0, therefore, it should never be inserted again.<br><br></div>Trying to solve this problem I looked back at the VRP example included with SCIP (thanks for that!), and I think I'm doing like I'm supposed to, specifically, I'm transforming the constraints in the init method and inserting the generated pricing variables into the transformed contraints. One thing that I could note was that the reduced cost of each edge e = (i, j) in the example is using the following formula:<br></div>C_e' = -arc_con(i, j) - 0.5 * part_con(i) - 0.5 * part_con(j)<br><br></div>Shouldnt the formula be:<br>C_e' = C_e - arc_con(i, j) - 0.5 * part_con(i) - 0.5 * part_con(j)<br></div><div>That is, shouldnt we include the length of the edge?<br></div><div><br></div>Also, looking at the model in the example, I can see that you have two types of variables: one for the edges(Y) and one for the tours(X). The "part_con" constraint looks like it "translates" the X variables into the Y variables. The model described in the paper is very similar, but instead of keeping this "translation" contraint, it replaces every Y variable with its equivalent expression with the X variables. This makes it more complicated to manage, because when generating a column (new X variable), I would need to insert the variable in a lot of contraints. So instead, I would like to keep the "translation" constraint, and just add the X variable to this "translation" contraint, just like it is done in the example. Do you guys know if this is OK, even if I add cuts (which uses only the Y variables) in the Constraint Handler?<br><br></div>Sorry for the long text, I tried to explain the best that I can while being as concise as possible.<br><br></div>Thanks,<br></div>Matheus<br><div><div><div><div><br></div></div></div></div></div>