Skip to main content

Assigning charging stations that reduces the system's travel time

Answered
Sihang Li
  • Gurobi-versary
  • First Comment
  • First Question

I 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?

Related to

0

Comments

3 comments

Date Votes
  • Simranjit Kaur
    • Gurobi Staff
    Edited

    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
  • Sihang Li
    • Gurobi-versary
    • First Comment
    • First Question

    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
  • Simranjit Kaur
    • Gurobi Staff
    Edited

    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,
    Simran

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post