1
$\begingroup$

I am working on a single source multiple destinations problem formulation using MILP. The network I have designed is as shown in the figure below Graph Network. The objective function is to minimize the total travelling distance from source to all destination nodes which is defined as follows:

$\min \sum_{(i, j)\in N} T_{ij} x_{ij}$

The constraints I have defined are as follows:

$\sum_{i,j\in Edges} x_{ij} = \sum_{j,l\in Edges} x_{jl}$ for all intermediate nodes. It ensures path starts at origin and that each subsequent edge in the path is a continuation from the previous edge.

$\sum_{i,j\in Edges} x_{ij} = 1 $ For farthest destination node from all destinations

$\sum_{i,j\in Edges} x_{ij} >= 1 $ For intermediate destination nodes

$\sum_{i,j\in Edges} x_{ij} = 1$ for i is source node

The output shows discontinuous edges while computing the shortest path for all destinations. For example, O is the source node and A, C, and E. 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.

$\endgroup$
6
  • $\begingroup$ What is $u_j$? It doesn't seem to be used anywhere. $\endgroup$
    – saulspatz
    Apr 10, 2021 at 11:51
  • $\begingroup$ @saulspatz $u_j$ represents the destination nodes. I set a constraint that each destination node must be visited at least once. The intermediate destinations can be visited multiple times. $\endgroup$
    – bsha
    Apr 10, 2021 at 11:57
  • $\begingroup$ How does that enter into the MILP problem? You minimize a function of the $x_{ij}$ subject to constraints on the $x_{ij}$. I understand that part. Then you define some variables $u_j$ that are never mentioned again. How can they possibly affect the solution? Are they defined in terms of the $x_ij$? $\endgroup$
    – saulspatz
    Apr 10, 2021 at 12:03
  • $\begingroup$ In the code, I have defined it using $x_{ij}$. I am writing two different constraints for the destinations. The code I am writing in docplex python as follows: 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') $\endgroup$
    – bsha
    Apr 10, 2021 at 12:08
  • $\begingroup$ Please put the explanation in the body of the question, formatted so as to be easier to read. What is m? I don't see $u_i$ anywhere in your comment. We shouldn't have to guess what you mean. $\endgroup$
    – saulspatz
    Apr 10, 2021 at 12:12

1 Answer 1

1
$\begingroup$

You are almost there. Think of sending one unit of flow from the source to each of the $d$ destination nodes. You can express the whole system of constraints uniformly as one constraint per node: outflow minus inflow equals $d$ for the source node, $0$ for the intermediate nodes, and $-1$ for the destination nodes.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .