I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf)

The paper describes the constraint like this: $$\sum_{i \in S} \sum_{j \in S, j<i} y^t_{ij} \le \sum_{i \in S} z_{it} -z_{kt} \quad S \subseteq M \quad t \in T \quad \text{for some} \ k \in S$$ And some page further I've found this: $k=arg max_j\{z_{jt}\}$ but no idea how to interpret this.

Where $y^t_{ij}$ is $1$ when the edge is used from $i$ to $j$ at time $t$. And $z_{it}$ is $1$ when vertex $i$ is visited at time $t$.

What is the exact definition of $S$? The set of all subtours or one specific subtour? Let say $M = \{1, 2, ...,7\}$ and $M' = \{0, 1, ..., 7\}$ ($M'$ with supplier/depot).

And the solution I get contains the following subtours: $0,1,3,0$ and $2,4,5,2$ and $6,7,6$

Know how would a pseudo code look like to implement this? And what is $k$?

My current solution look like this (implemented in C# with Gurobi solver). But I'm not sure if this should be implemented as a lazy constraint in the callback or adding the constraint after model.Optimize() if a subtour exists and call model.Optimize() again.

I did an implementation but I guess it's not worth to post it before I really understand the equation.

  • $\begingroup$ Are you asking for code, review of your code, an explanation of $k$, or ...? $\endgroup$ – Raphael Jun 5 '15 at 11:23

$S$ contains every subtour except the tour with the depot. And for each subtour a constraint has to be added.

The meaning of $k=argmax_j\{z_{jt}\}$ has been answered in https://math.stackexchange.com/questions/1290142/explanation-of-textrmargmax-jz-jt-and-how-to-implement-it/1290178#1290178

I solved this with a callback as soon as a subtour is found.


Not the answer you're looking for? Browse other questions tagged or ask your own question.