I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems.
I can understand basic ones like the knapsack problem:
$min \quad \sum_{i \in I} v_i x_i$
$s.t.$
$\qquad \sum_{i \in I} w_i x_i \leq K$
$\qquad x_i \in \{0, 1\} \qquad (i \in I)$
however when it comes to something like this formulation for the steiner minimal tree problem:
$min \quad \sum_{[i,j]\in E} d_{ij}$
$s.t.$
$\qquad d_{ij} \leq \| a^i-x^j\| - M(1-y_{ij}), \quad [i,j] \in E_1,$
$\qquad d_{ij} \leq \| x^i-x^j\| - M(1-y_{ij}), \quad [i,j] \in E_2,$
$\qquad d_{ij} \leq 0, \hspace{105pt} [i,j] \in E_3,$
$\qquad \sum_{j\in S} y_{ij} = 1, \hspace{82pt} i \in P,$
$\qquad \sum_{i < j,i \in S} y_{ij} = 1, \hspace{68pt} j \in S - \{p+1\},$
$\qquad y_{ij} \in \{0,1\}, \hspace{87pt} [i,j] \in E,$
$\qquad d_{ij} \in \mathbb{R}, \hspace{104pt} [i,j] \in E,$
$\qquad x^i \in \mathbb{R}, \hspace{105pt} i \in S.$
I have trouble working out what each of the constraints represent.
I am not asking for someone to explicitly explain that particular problem (although that would be a good help) I am more asking for advice on good ways to increase my understanding ILP formulations for combinatorial optimisation problems - especially for graph theory related problems.
Are there any good resources that people could recommend that explain the basics well with some good worked examples?
I'm sure I will get it eventually, it feels like the sort of thing that takes a while to understand and then it just "clicks" all of a sudden; I just need some help getting it to "click"!
Any help would be greatly appreciated.