My question is whether there is a trick to express the following constraint as linear constraints? S_j=max{ a_j, S_i+t_ij } where a_j and t_ij are constants Many thanks in advance asked 26 Oct '13, 08:17 gdikas 
Sj >= Si + tij*xij  M(1xij) and Sj >= aj where xij is a boolean equal to 1 if j should be after i answered 26 Oct '13, 09:19 Sohaib Afifi ...if
(26 Oct '13, 16:36)
fbahr ♦
S_j are forced to take the larger possible value due to the objective, so i do not think the equality is safeguarded in this case. I also posted a more descriptive comment above. Thank you
(27 Oct '13, 02:48)
gdikas

Thank you for your help, I think the following constraints (1) and (2) will work, please advice me if anything seems wrong. (1) s_jk ≤ a_j+(b_ja_j )w_jk + M(1x_ijk), (i,j)∈A,k∈K case: w_jk = 1 => s_jk ≤ s_ik + t_ij => s_jk = s_jk + t_ij case: w_jk = 0 => s_jk ≤ a_j => s_jk = a_j All in all, you need four (types of) constraints: the two inequalities that you specified in the addendum to your question plus the two introduced here. For the latter, you need to identify bounds, \(L_{\{x,y\}}, ~U_{\{x,y\}}\) of the expressions in the \(\max\) function. This is quite trivial for the first expression, \(x := a_j\): \(L_x = a_j = U_x\) ...and only a tiny bit less trivial for the second one, \(y := s_{ik} + t_{ij}  M(1x_{ijk})\) – if we pick \(M\) wisely, \(M := b_i + t_{ij}\): \(L_y = a_i  b_i, U_y = b_i + t_{ij}\).
(27 Oct '13, 09:48)
fbahr ♦
Now you can plug \(L_{\{x,y\}}, ~U_{\{x,y\}}\) into the "template" provided in @Paul Rubin's blog post – which yields: \(\textrm{(1)}~ s_{jk} \leq a_j + ([b_i + t_{ij}]  [a_j])w_{jk}\)
(27 Oct '13, 09:52)
fbahr ♦
For \(w_{jk} = 0\):
(27 Oct '13, 10:32)
fbahr ♦
...and for \(w_{jk} = 1\):
(27 Oct '13, 10:53)
fbahr ♦
To wrap things up:
(27 Oct '13, 12:12)
fbahr ♦
Here are some considerations for your last comments:
(27 Oct '13, 13:05)
gdikas
ad 1. Even in your formulation you don't need to do this since ad 2. If ad 3. <I'll give this a 2nd thought.>
(27 Oct '13, 14:30)
fbahr ♦
After much consideration [or, more precisely: failing to find a counterexample which breaks your formulation], I think that your formulation actually works asis [probably due to the fact  didn't really think this through, though  that you have
(28 Oct '13, 06:04)
fbahr ♦
showing 5 of 8
show 3 more comments

Is this for a fixed value of i?
Actually, I am trying to eliminate the waiting times in case a of a VRP problem in which the objective function favors large values of s_ik (start of service). The following two constraints do not guarantee that s_ik will receive the lowest possible value.
a_i≤ s_ik ≤ b_i (ai earliest start of service, bi latest start of service)
s_ik+t_ijM(1x_ijk )≤s_jk (i,j)∈A,k∈K (where A is the arc set, and k the set of vehicles, xijk 1 if arc ij traversed by veh. k, t_ij travel time, M>>1)
Furthermore, I cannot add s_ik (or s_ikai)to the objective function because it conflicts with one other term.