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's gravatar image

gdikas
13
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

link

answered 26 Oct '13, 09:15

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

Sj >= Si + tij*xij - M(1-xij) and Sj >= aj where xij is a boolean equal to 1 if j should be after i

link

answered 26 Oct '13, 09:19

Sohaib%20Afifi's gravatar image

Sohaib Afifi
111
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

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

link

answered 27 Oct '13, 04:35

gdikas's gravatar image

gdikas
13
accept rate: 0%

edited 27 Oct '13, 11:16

fbahr's gravatar image

fbahr ♦
4.6k716

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:

  1. Don't introduce +M*(1-x_ijk) to (1); this allows for s_jk > max(a_j, s_ik + ...)

  2. In (2), it's probably supposed to be -M*(1-x_ijk) (not +M*(1-x_ijk))

  3. 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.

  4. [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:

  1. 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<b_j.

  2. +M(1-x_ijk)in case of xijk=0 allows s_j to recieve any positive value. While - M(1-x_ijk) would set s_j ~= -M that is again out of the range a_j≤ s_jk ≤ b_j

  3. Although b_j is not an upper bound for s_ik+tij but s_jk must be <=b_j, so i think is an equivelant limit for this case. Also, i donot understant why 0 cannot be a LB?

(27 Oct '13, 13:05) gdikas

ad 1. Even in your formulation you don't need to do this since x_ijk = 0 already "deactivates" (2) by adding +M to the RHS of the inequality, and (1) is basically reduced to s_jk <= b_j [by means of w_jk = 1].

ad 2. If x_ijk = 0, and therefore s_jk <= s_ik + t_ij + <sth.>(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. <I'll give this a 2nd thought.>

(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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×65
×21
×16

Asked: 26 Oct '13, 08:17

Seen: 1,361 times

Last updated: 28 Oct '13, 06:04

OR-Exchange! Your site for questions, answers, and announcements about operations research.