Decision Optimization

 View Only
Expand all | Collapse all

How to solve discontinuity in single source multiple destinations problem?

  • 1.  How to solve discontinuity in single source multiple destinations problem?

    Posted Thu April 15, 2021 04:11 AM

    I am trying to extend the program on the following link https://github.com/shellei503/Linear-Programming-Examples/blob/master/9.3%20(The%20Shortest%20Path%20Problem)/prob_1/9.3-1.ipynb for single-source and multiple destinations.

    Some modifications to the existing network include that each edge in the network is bidirectional. I have added the following constraints to the existing code to achieve the objective:

    m.add_constraint(m.sum(x[(i,j)] for i,j in last_arc if j == final_END_NODE)== 1, ctname='last_arc') for dd in remDst: m.add_constraint(m.sum(x[(i,j)] for i,j in subEdges if j==dd)>= 1, ctname='last_arc') m.add_constraint(m.sum(x[(i,j)] for i,j in subEdges if i==src)== 1, ctname='start_arc_F') m.add_constraint(m.sum(x[(i,j)] for i,j in subEdges if j==src)== 0, ctname='start_arc_B')

    where final_END_NODE is computed based on the distance from the source node to the farthest destination, remDst includes the remaining destinations, and subEdges includes the edges in the network which are bidirectionally visitable.

    The output shows discontinuous edges while computing a single shortest path from the source to all destinations. For example, O is the source node and A, C, and E are the destination nodes. The output shows the edges:

    O-C

    C-E

    A-B

    B-A

    The solution misses the edge from E-B. What should be the constraint to address this problem. Any help in this regard is appreciated.






    #DecisionOptimization
    #Support
    #SupportMigration


  • 2.  RE: How to solve discontinuity in single source multiple destinations problem?

    Posted Thu April 15, 2021 02:53 PM

    Without looking into the details, as an initial step, you might want to try to force the edge E-B into the solution explicitly by setting the value of the corresponding variable to 1. If your model becomes infeasible, you can refine conflicts to find out which constraint(s) is conflicting with the edge E-B. If it is feasible, maybe there are multiple valid solutions based on the current set of constraints. You need to check further to see if the solution without edge E-B is actually valid. If not, you need modify your model accordingly.

    If you need further discussion, please open a case if you are entitled. Otherwise, please discuss your question in Data Science Community https://community.ibm.com/community/user/datascience/communities/community-home/digestviewer?communitykey=ab7de0fd-6f43-47a9-8261-33578a231bb7&tab=digestviewer






    #DecisionOptimization
    #Support
    #SupportMigration