[SCIP] VRP Example and Column Regeneration

[Matheus Ota]

Dear Scipiers,

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 (https://link.springer.com/article/10.1007/s10107-005-0644-x)
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(
http://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep/)
package for cutting.

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.

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:
C_e' = -arc_con(i, j) - 0.5 * part_con(i) - 0.5 * part_con(j)

Shouldnt the formula be:
C_e' = C_e - arc_con(i, j) - 0.5 * part_con(i) - 0.5 * part_con(j)
That is, shouldnt we include the length of the edge?

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?

Sorry for the long text, I tried to explain the best that I can while being
as concise as possible.

Thanks,
Matheus
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20180527/1e70823c/attachment.html>