# Can s_j=max{ a_j, s_i+t_ij } be formulated as a linear constraint?

 0 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 1●3 accept rate: 0% Is this for a fixed value of i? (26 Oct '13, 15:52) Paul Rubin ♦♦ 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_ij-M(1-x_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_ik-ai)to the objective function because it conflicts with one other term. (27 Oct '13, 02:42) gdikas

 5 answered 26 Oct '13, 09:15 fbahr ♦ 4.6k●7●16 accept rate: 13%
 0 Sj >= Si + tij*xij - M(1-xij) 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 11●1 accept rate: 0% ...if there's a particular relation btw. i and j which implies i < j (for instance, j=i+1) and $$S_j$$ is bounded to the smallest value that satisfies both constraints (usually induced by a $$\min$$-obj. over a function of $$S$$). (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
 0 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_j-a_j )w_jk + M(1-x_ijk),           (i,j)∈A,k∈K (2) s_jk ≤ s_ik + t_ij + (a_j)(1-w_jk)+ M(1-x_ijk),  (i,j)∈A,k∈K case: w_jk = 1 => s_jk ≤ s_ik + t_ij => s_jk = s_jk + t_ij (1) s_jk ≤ b_j + M(1-x_ijk),           ((i,j)∈A),k∈K (2) s_jk ≤ s_ik + t_ij + M(1-x_ijk),  ((i,j)∈A),k∈K case: w_jk = 0 => s_jk ≤ a_j => s_jk = a_j (1) s_jk ≤ a_j + M(1-x_ijk),                     ((i,j)∈A),k∈K (2) s_jk ≤ s_ik + t_ij + (a_j) + M(1-x_ijk),  ((i,j)∈A),k∈K answered 27 Oct '13, 04:35 gdikas 1●3 accept rate: 0% fbahr ♦ 4.6k●7●16 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(1-x_{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}$$ $$\textrm{(2)}~ s_{jk} \leq s_{ik} + t_{ij} - (b_i + t_{ij})(1-x_{ijk}) + ([a_j] - [a_i - b_i])(1 - w_{jk})$$ (27 Oct '13, 09:52) fbahr ♦ For $$w_{jk} = 0$$: $$\begin{array}{l} \textrm{(1)} & s_{jk} \leq a_j\\ \textrm{(2)} & s_{jk} \leq s_{ik} + t_{ij} - (b_i + t_{ij})(1-x_{ijk}) + ([a_j] - [a_i - b_i])\\ & \Rightarrow~ s_{jk} \leq a_{i} + t_{ij} - (b_i + t_{ij})(1-x_{ijk}) + a_j - a_i + b_i\\ & \Rightarrow~ s_{jk} \leq a_j + [b_i + t_{ij}] - (b_i + t_{ij})(1-x_{ijk})\\ \Rightarrow~ & \textrm{(1)} \leq \textrm{(2)} ~\Rightarrow~ s_{jk} = a_j = \max(a_j, s_{ik} + \ldots) \end{array}$$ (27 Oct '13, 10:32) fbahr ♦ ...and for $$w_{jk} = 1$$: $$\begin{array}{l} \textrm{(1)} & s_{jk} \leq b_i + t_{ij}\\ \textrm{(2)} & s_{jk} \leq s_{ik} + t_{ij} - (b_i + t_{ij})(1-x_{ijk})\\ & \Rightarrow~ s_{jk} \leq [b_i + t_{ij}] - (b_i + t_{ij})(1-x_{ijk})\\ \Rightarrow~ & \textrm{(2)} \leq \textrm{(1)} ~\Rightarrow~ s_{jk} = s_{ik} + t_{ij} - (b_i + t_{ij})(1-x_{ijk}) = \max(a_j, s_{ik} + \ldots) \end{array}$$ (27 Oct '13, 10:53) fbahr ♦ To wrap things up: Don't introduce +M*(1-x_ijk) to (1); this allows for s_jk > max(a_j, s_ik + ...) In (2), it's probably supposed to be -M*(1-x_ijk) (not +M*(1-x_ijk)) b_j is an UB for s_j, but not for s_ik+t_ij-M*(1-x_ijk); and likewise: 0 is not a LB. [And just for the sake of completeness... I think you got it right - but I tend to forget it: (U_x - L_y)w and (U_y - L_x)(1-w)] (27 Oct '13, 12:12) fbahr ♦ Here are some considerations for your last comments: M*(1-x_ijk)is used to "deactivate" the constraint if xijk=0, so there is no conflict with other constriants, such as a_j≤ s_jk ≤ b_j and s_ik+t_ij-M(1-x_ijk )≤s_jk (i,j)∈A,k∈K, especially if bi+tij(1-w_jk) - M, it's the "job" of w_jk (=0) to add sth. large enough to make (2) valid, and (1) is reduced to s_jk <= a_j. [Your "hack" might work for you if you actually prefer s_jk <= b_j in case of w_jk = 0.] ad 3. (27 Oct '13, 14:30) fbahr ♦ After much consideration [or, more precisely: failing to find a counter-example which breaks your formulation], I think that your formulation actually works as-is [probably due to the fact - didn't really think this through, though - that you have max(x=const, y=var), not max(x=var, y=var)`.] (28 Oct '13, 06:04) fbahr ♦ showing 5 of 8 show 3 more comments
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: