'Weird' Indexing In The MILP Literature

37 Views Asked by At

Fairly new to MILP. I posted this question as an issue on the Gurobi examples repo too, but it might be more appropriate to ask it here.

NOTE: Since I "need at least 10 reputation to post images" , the images won't render, but they are available on the github issue linked above and I have linked to the urls (sorry).

I was following this great example from Gurobi.

In the model formulation, we have: [link to image of formulation]https://user-images.githubusercontent.com/19332617/108038384-70a65200-7043-11eb-9fbd-1eb9005240b6.png

I see that we have: d∈D={n+1,n+2,...,n+m}: Index and set of depots (service centers), where m is the number of depots. I am confused as to how there can be n+m depots. I am also confused as to why the set starts from n+1 instead of 1. In the example there are two depots, not 9 i.e 2+7.

I have run into something similar when studying the literature (Ramkumar et al 2012, their formulation also has confusing indices for the number of depots: link to image of Ramkumar formulation )

Edit: Indeed, the paper referenced in the notebook also notes "(1,..,n+m) where the m depots are represented by n+1,...,n+m" but does not state their reasoning for doing so. (S. Salhi, A. Imran, N. A. Wassan. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation. Computers & Operations Research 52 (2014) 315-325.)

Edit 2: However, in the Supply Network I example, we have something that makes more sense (to me).: link to Supply Network formulation image

Here there is no (n+1...n+m) indexing.

Any enlightenment on this indexing and why it used would be greatly appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

The idea is that there are $n+m$ nodes in total, with $n$ of one type (customer) and $m$ of the other type (depot). The first $n$ are customers $\{1,\dots,n\}$, and the last $m$ are depots $\{n+1,\dots,n+m\}$.