search

BrunoRosendo / master-thesis

Source code for my master's thesis, in the topic "Quantum algorithms for optimizing urban transportation"
MIT License
6 stars 0 forks source link

Mandatory to pass in node even if pickup is 0 #29

Closed BrunoRosendo closed 7 months ago

BrunoRosendo commented 7 months ago

in cases where deliveries are not used

BrunoRosendo commented 7 months ago

When not using deliveries, I simply return max(pickup_demand, 1). However, I need to check if the behaviour is correct with deliveries, since the overall demand can be 0 or negative and we still need to pass in the node

BrunoRosendo commented 7 months ago

The problem occurred when we had demand (pickup - delivery) smaller than 0. It wasn't because of the demand itself but because, in those cases, CPLEX doesn't return 0.0 or 1.0 only. It would return values very close to it (e.g. 0.99999998). This thread explains why this can happen in the general case

https://stackoverflow.com/questions/72895787/cplex-binary-var-matrix-gives-values-outside-0-0-and-1-0

To fix it, I simply rounded the binary values before returning.

I believe this can happen in cases with negative demand because of the way inequality constraints work:

image

As we can see, there will be cases where the equation will be -X - slack = 0, which will not be fully satisfied and the binary values will therefore not be 1.0 exactly.