Can't seem to figure out the IP formulation for this.

Question Suppose there are $n$ people connected in a circular fashion as demonstrated by the diagram.

Individuals need to send packages to each other but can clearly only pass the packages in a clockwise or anticlockwise direction. Each person has at most one package to send to another person. So let $P_i$ denote the number of passes between person $i$ and person $i+1 \pmod{n}$. We want to minimize $\max\limits_{0 \leq i \leq n-1} P_i$. So basically, we want to minimize the number of passes between pair(s) that have the most number of passes between them. We can also think of this problem like a network where certain connections (edges) are exhausted so in order to reduce stress between those nodes, we can redistribute the flow in the opposite direction.

My Attempt

We notice that if we have $k$ packages to distribute, there are a maximum of $2k$ paths that each package can take to get to its destination since each package can either go clockwise or anticlockwise. Intuitively, these paths can overlap and the greatest number of overlaps will be equivalent to $(\max\limits_{0 \leq i \leq n-1} P_i)$. So ideally we want to minimize overlaps but how to actually formulate this is my problem.


Here is the formulation I came up with.

$R_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{if edge $(i,i+1 \pmod{n})$ is on route $j$}\\ 0 & \mbox{otherwise } \end{array} \right.$

$X_{j} = \left\{ \begin{array}{ll} 1 & \mbox{if route j is chosen}\\ 0 & \mbox{otherwise } \end{array} \right.$

We assume that route $j$ distributes some package clockwise and route $j+1$ distributes the same package anticlockwise.

IP formulation:

$ \begin{array}{ & &} Min: & \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{2k-1} R_{ij} X_j\\ s.t. & X_j + X_{j+1} = 1 \\ & X_{ij} = 0 \ or \ X_{ij} = 1 \end{array} $

Essentially what this is saying is that, we minimize the number of passes across each edge, for each of the possible $2k$ routes. The first constraint makes it so that only a clockwise or anticlockwise route must be taken to distribute the $j$-th package. It makes sense to me but i'm not sure.

  • $\begingroup$ feel it may be open to misinterpretation due to slightly less info than needed. ie can only be solved with some assumptions wrt current info. how many pkgs are transferred? do individuals start out with same # of pkgs? etc $\endgroup$
    – vzn
    Aug 10, 2014 at 14:55
  • $\begingroup$ Yes, I will edit that in. All we know is that an individual has at most one package per individual. The total number of packages that need to be distributed we can call $k$. So if there are 5 people in the network and each person has a package for another person, there are a total of 20 packages max. $\endgroup$ Aug 10, 2014 at 15:00
  • $\begingroup$ Just edited in what I think the formulation should be if you wanna take a look. $\endgroup$ Aug 10, 2014 at 15:11
  • $\begingroup$ I don't think that this formulation is correct. For example, the data, i.e., how many packages does person $i$ needs to send to person $j$ is not part of the formulation (you should define new constants for this task..). $\endgroup$ Aug 10, 2014 at 16:01
  • $\begingroup$ But it is, its encoded in the route adjacency matrix. So for instance, route $R_{ij}$ and $R_{ij+1}$ are clockwise and anticlockwise routes for person $i$ to send package $j$. The route also stores the edges that the package can take, so we actually know where all packages will end up going. $\endgroup$ Aug 10, 2014 at 16:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.