Vertices visited more than once

[tomatoes-prog]

I am working with a CVRPTW with 68 nodes on the Graph, when I try to solve the problem with the package I found that with a time_limit of 300 the Pulp Solver is finding multiple routes where the Nodes are visited more than once. I took a look at the code and I found that the module master_solve_pulp.py in line 281 (Sorry, I dont know how to quote the lines) are the constraints of the master problem: `

Save set covering constraints

self.set_covering_constrs[node] = pulp.LpConstraintVar(
                  "visit_node_%s" % node, pulp.LpConstraintGE, right_hand_term )

`

Where I think the problem is that the constraint is build with greater than Sign, I found that changing it to EQ pulp.LpConstraintEQ solves the problem but i know that the reason is because of the dual variables in the pricing problem. I dont know if there is a way to solve the column generation with GE constraint and solve the final problem with EQ constraint

[torressa]

Hey again @tomatoes-prog I think I did this for convergence, as we are minimising it will always end up with equality. I didn't think about early termination though

Your suggestion makes sense, since the constraints are already saved when calling _solve(relax=False, time_limit=whatever) (to get an integer solution at the end) defined in (to get code snippet: click on the line number -> copy permalink) https://github.com/Kuifje02/vrpy/blob/fb9adea8d8f89f07e7074c4de3c56d7f05007243/vrpy/master_solve_pulp.py#L169 we can change the sense parameter of the constraints. e.g.

def _solve(self, relax: bool, time_limit: Optional[int]):
    if not relax:
        for node in self.G.nodes():
            self.set_covering_constrs[node].sense = pulp.LpConstraintEQ
    # do other stuff        

[tomatoes-prog]

I would like to know if the change of the sign does modify the dual variables and thus the reduced cost function in the pricing problem.

[torressa]

I don't think so, nope. This is what we had in the past: https://github.com/Kuifje02/vrpy/commit/4c93897070b1c4a0cf14685f5382a1576a1aa0d8#diff-21c83ae683a648d3d9993ee9165eac081655344f5a584ef3424418f3c3942809

Also, what I wrote before was actually what we had before the "formulation by columns" rewrite (https://github.com/Kuifje02/vrpy/commit/c80507e581fd6c7e4aa77fadc700142436d97483#diff-21c83ae683a648d3d9993ee9165eac081655344f5a584ef3424418f3c3942809R258

[Kuifje02]

I agree with everything @torressa said : 0/ having a >= sign speeds up convergence during the column generation process 1/ the change of sign does have an impact on the dual variables : setting the sign to = yields dual variables that can be positive or negative, while >= yields only positive variables. This is partially why it is better to keep the >= sign 2/ However, when solving the last MIP (after the column generation procedure), it should indeed be a = sign, as it was before

[tomatoes-prog]

Perfect! Changing it it to = with pulp.LpConstraintEQ decreased the convergence performance.

I will try this myself, I dont know how to publish and share if it works but I will pay attention for future releases if this is fixed. Thank you.

[torressa]

@Kuifje02 My bad, I'll fix 2 that now @tomatoes-prog I'll commit to the dev branch so you can check it out for now. If you want to contribute you can simply fork it and send a pull request.

[Kuifje02]

@tomatoes-prog maybe on some specific data set, using a = sign speeds up convergence, but in general, it is better to use the >= sign while generating columns, so that the dual variables remain positive.

[tomatoes-prog]

@torressa Hello again, I just took a look to the dev branch and tried the previus problem but I still couldn't solve the problem.

I think the problem now is the _solve function still is not working correctly at the last iteration even with the for loop to change the sense of the constraint because it just modify the LpConstraint object but doesn't modify the Master Problem. I would like to suggets the next piece of code after the not relax conditional

            for const in self.prob.constraints:
                self.prob.constraints[const].sense = pulp.LpConstraintEQ

This will modify the sense of the problem but I dont know if this have other consequences

[Kuifje02]

@tomatoes-prog as mentioned above, doing what you propose will slow down the convergence, as it will allow dual variables to be negative, making the search space of the subproblem larger.

Can you post a data set (if possible small), so that we can 1/ reproduce the error 2/ fix it 3/ add a unit test ?

[tomatoes-prog]

Sorry maybe I am not very clear, and my English is not good. What I am proposing is to modify the constraint after the column generation procedure, like @Kuifje02 proposed some replies ago, so you don't slow the convergence. What I noted was that the commit attempted to solve the problem with this method but It doesnt work because it doesn't modify the self.prob so in the last iteration when you solve the master problem the problem continues with >= sense.

Unfortunately I just reverted the version because the master branch seems to work stable and I cannot show the results. You can try It yourself printing the constraints when change the self.relax object to false:

So, again I propose to change this

def _solve(self, relax: bool, time_limit: Optional[int]):
    if not relax:
        print(self.prob.constraints)
        for node in self.G.nodes():
            self.set_covering_constrs[node].sense = pulp.LpConstraintEQ
    # do other stuff        

for this:

def _solve(self, relax: bool, time_limit: Optional[int]):
    if not relax:
        print(self.prob.constraints)
        #SOLVING THE MIP PROBLEM
        for const in self.prob.constraints:
                #Modify the self.prob object instead of the self.set_covering_constrs object
                self.prob.constraints[const].sense = pulp.LpConstraintEQ
    # do other stuff        

You can try this with the any problem you have, even with the docs example, let me know if this doesnt work for you and I will upload a little graph to test

[Kuifje02]

@tomatoes-prog you are right, for some reason, self.set_covering_constrs[node].sense = pulp.LpConstraintEQ does not change the sign. I will do the modification with what you propose, thanks !

[Kuifje02]

Closing for now, will make a new release tomorow. Thanks @tomatoes-prog !