Assigning charging stations that reduces the system's travel time
AnsweredI was working on a project, and the problem is: out of all nodes from a traffic network, choose N nodes that would minimize the travel time of the system.
I modeled the problem with gurobi for a small network as such:
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
0 min_dist[1] + 0 min_dist[3] + 0 min_dist[4] + 0 min_dist[2]
+ xfc_min_dist[1] + xfc_min_dist[3] + xfc_min_dist[4] + xfc_min_dist[2]
+ 0 xfc_dists[1,3] + 0 xfc_dists[1,4] + 0 xfc_dists[1,2]
+ 0 xfc_dists[3,1] + 0 xfc_dists[3,4] + 0 xfc_dists[3,2]
+ 0 xfc_dists[4,1] + 0 xfc_dists[4,3] + 0 xfc_dists[4,2]
+ 0 xfc_dists[2,1] + 0 xfc_dists[2,3] + 0 xfc_dists[2,4]
Subject To
num_xfc_constraint: is_xfc[1] + is_xfc[3] + is_xfc[4] + is_xfc[2] = 1
self_dist_constraint_1_1: xfc_dists[1,1] = 0
self_dist_constraint_3_3: xfc_dists[3,3] = 0
self_dist_constraint_4_4: xfc_dists[4,4] = 0
self_dist_constraint_2_2: xfc_dists[2,2] = 0
xfc_dist_constraint_1_3: is_xfc[3] = 1 -> xfc_dists[1,3] = 1e-08
non_xfc_dist_constraint_1_3: is_xfc[3] = 0 -> xfc_dists[1,3] = 1e+100
xfc_dist_constraint_1_4: is_xfc[4] = 1 -> xfc_dists[1,4] = 10.00000001
non_xfc_dist_constraint_1_4: is_xfc[4] = 0 -> xfc_dists[1,4] = 1e+100
xfc_dist_constraint_1_2: is_xfc[2] = 1 -> xfc_dists[1,2] = 10.00000002
non_xfc_dist_constraint_1_2: is_xfc[2] = 0 -> xfc_dists[1,2] = 1e+100
xfc_dist_constraint_3_1: is_xfc[1] = 1 -> xfc_dists[3,1] = 10
non_xfc_dist_constraint_3_1: is_xfc[1] = 0 -> xfc_dists[3,1] = 1e+100
xfc_dist_constraint_3_4: is_xfc[4] = 1 -> xfc_dists[3,4] = 10
non_xfc_dist_constraint_3_4: is_xfc[4] = 0 -> xfc_dists[3,4] = 1e+100
xfc_dist_constraint_3_2: is_xfc[2] = 1 -> xfc_dists[3,2] = 10.00000001
non_xfc_dist_constraint_3_2: is_xfc[2] = 0 -> xfc_dists[3,2] = 1e+100
xfc_dist_constraint_4_1: is_xfc[1] = 1 -> xfc_dists[4,1] = 10.00000001
non_xfc_dist_constraint_4_1: is_xfc[1] = 0 -> xfc_dists[4,1] = 1e+100
xfc_dist_constraint_4_3: is_xfc[3] = 1 -> xfc_dists[4,3] = 10.00000002
non_xfc_dist_constraint_4_3: is_xfc[3] = 0 -> xfc_dists[4,3] = 1e+100
xfc_dist_constraint_4_2: is_xfc[2] = 1 -> xfc_dists[4,2] = 1e-08
non_xfc_dist_constraint_4_2: is_xfc[2] = 0 -> xfc_dists[4,2] = 1e+100
xfc_dist_constraint_2_1: is_xfc[1] = 1 -> xfc_dists[2,1] = 10
non_xfc_dist_constraint_2_1: is_xfc[1] = 0 -> xfc_dists[2,1] = 1e+100
xfc_dist_constraint_2_3: is_xfc[3] = 1 -> xfc_dists[2,3] = 10.00000001
non_xfc_dist_constraint_2_3: is_xfc[3] = 0 -> xfc_dists[2,3] = 1e+100
xfc_dist_constraint_2_4: is_xfc[4] = 1 -> xfc_dists[2,4] = 20.00000001
non_xfc_dist_constraint_2_4: is_xfc[4] = 0 -> xfc_dists[2,4] = 1e+100
xfc_min_dist_constraint_Node(1): is_xfc[1] = 1 -> xfc_min_dist[1] = 0
non_xfc_min_dist_constraint_Node(1): is_xfc[1] = 0 -> - min_dist[1]
+ xfc_min_dist[1] = 0
xfc_min_dist_constraint_Node(3): is_xfc[3] = 1 -> xfc_min_dist[3] = 0
non_xfc_min_dist_constraint_Node(3): is_xfc[3] = 0 -> - min_dist[3]
+ xfc_min_dist[3] = 0
xfc_min_dist_constraint_Node(4): is_xfc[4] = 1 -> xfc_min_dist[4] = 0
non_xfc_min_dist_constraint_Node(4): is_xfc[4] = 0 -> - min_dist[4]
+ xfc_min_dist[4] = 0
xfc_min_dist_constraint_Node(2): is_xfc[2] = 1 -> xfc_min_dist[2] = 0
non_xfc_min_dist_constraint_Node(2): is_xfc[2] = 0 -> - min_dist[2]
+ xfc_min_dist[2] = 0
Bounds
Binaries
is_xfc[1] is_xfc[3] is_xfc[4] is_xfc[2]
General Constraints
min_dist_constraint_Node(1): min_dist[1] = MIN ( xfc_dists[1,1] ,
xfc_dists[1,3] , xfc_dists[1,4] , xfc_dists[1,2] )
min_dist_constraint_Node(3): min_dist[3] = MIN ( xfc_dists[3,1] ,
xfc_dists[3,3] , xfc_dists[3,4] , xfc_dists[3,2] )
min_dist_constraint_Node(4): min_dist[4] = MIN ( xfc_dists[4,1] ,
xfc_dists[4,3] , xfc_dists[4,4] , xfc_dists[4,2] )
min_dist_constraint_Node(2): min_dist[2] = MIN ( xfc_dists[2,1] ,
xfc_dists[2,3] , xfc_dists[2,4] , xfc_dists[2,2] )
End
and gurobi reported that the model is infeasible. I ran the computeIIs() function and get an .ilp file that looks like this:
\ Model _copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
0 xfc_dists[4,2] + 0 xfc_dists[2,3]
Subject To
num_xfc_constraint: is_xfc[1] + is_xfc[3] + is_xfc[4] + is_xfc[2] = 1
xfc_dist_constraint_4_2: is_xfc[2] = 1 -> xfc_dists[4,2] = 1e-08
non_xfc_dist_constraint_4_2: is_xfc[2] = 0 -> xfc_dists[4,2] = 1e+100
xfc_dist_constraint_2_3: is_xfc[3] = 1 -> xfc_dists[2,3] = 10.00000001
non_xfc_dist_constraint_2_3: is_xfc[3] = 0 -> xfc_dists[2,3] = 1e+100
Bounds
Binaries
is_xfc[1] is_xfc[3] is_xfc[4] is_xfc[2]
End
I am unsure why the conditional constraints shown above cause the system to be infeasible. Can anyone possibly help me with that?
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
The num_xfc_constraint forces at least one of the variables is_xfc[2] or is_xfc[3] to be zero. The infeasibility comes as the associated indicator constraints set the variables xfc_dists[4,2] and xfc_dists[2,3] to 1e+100. Is there a particular reason you need to set these variables to 1e+100?
0 -
Thanks so much for helping!
I am setting up the model so that the sum of all `xfc_min_distance[i]` is minimized, and the `xfc_min_distance[i]` is defined as the minimum distance from a non-xfc node to any xfc node.
The distances from all node-to-node pairs were precomputed from Dijkstra algorithm, and I would like to exclude the non-xfc-node-to-non-xfc-node distances when calculating distances to closest xfc node, and that's why I set them to GRB.INFINITY when the destination node is not an xfc node.0 -
Hi Sihang,
Instead of using GRB.INFINITY, you can set the non-xfc-node-to-non-xfc-node distances to a finite value greater than the maximum of your precomputed node-to-node distances. This should also exclude them from calculating the distance to the closest xfc node.
On another note, you perhaps would want to exclude xfc_dists[i,i] from the calculation of min_dist[i], as otherwise, your min_dist[i] values will always be zero.
Also, the following constraints can be modelled in a different way, which might be worth trying if the maximum of the precomputed node-to-node distances is small.
xfc_dist_constraint_1_4: is_xfc[4] = 1 -> xfc_dists[1,4] = 10.00000001 non_xfc_dist_constraint_1_4: is_xfc[4] = 0 -> xfc_dists[1,4] = 1e+100
can be replaced with
xfc_dist_constraint_1_4: xfc_dists[1,4] = 10 * is_xfc[4] + M * (1-is_xfc[4])
where M is just greater than the maximum of the precomputed node-to-node distances.
Best regards,
Simran0
Post is closed for comments.
Comments
4 comments