Preprocess node/edge data or reformat so Gurobi can optimize more efficiently
If your graph is sparse, the optimization model should be sparse, too. Specifically, you should only create a variable x[i,j] if the edge (i,j) exists in the graph. For an example of how to do this, see the netflow.py sample in the examples/python subdirectory of Gurobi.
I am working on a Dial a Ride Problem (DARP). I have a lage amount of nodes and edges (338 nodes and 826 edges). I've imported the node/edge data from OSMnx and am trying to solve the model with Gurobi Optimizer in Python.
To be able to use the OSMnx data with Gurobi, I created a matrix = len(nodes) x len(nodes) matrix and therein printed the length of the edge if two nodes were connected, and a large number otherwise. In the optimization, a x[i,j] = len(nodes) x len(nodes) binary decision variable is used to decide if an edge is traversed or not.
The problem I am encountering is a large computing time for just one request (+1 hour). I think this is because the model also has to consider all the other indices from this large matrix, even though they can be ignored completely since they represent that two nodes are unconnected.
My question therefore is if someone can help me find some preprocessing techniques or something else that might reduce my computational time. For example, tell the model that it can ignore indices from this matrix if the value is too high or maybe a more efficient node/edge storage file that Gurobi can use more efficiently.
Thanks in advance.