I have some points with determined coordinates $(a_i,b_i)$. A vehicle can move between these points based on rectangular distance. In more detail, we consider that the path between points is an orthogonal path.

In a mathematical model of my problem, I need to determine the coordinates of specific points that can exist in the path between each pair of points, according to the orthogonal path between them. For example, if the vehicle traverses between two specific points $(a_1,b_1)$ and $(a_2,b_2)$, the coordinates of the desired point $(x,y)$ can be $x=a_1$ and $b_1<y<b_2$ or $a_1<x<a_2$ and $y=b_2$.

How should I write such constraint in my MIP (mixed integer programming) model, which can explain the above mentioned feature?

  • $\begingroup$ Do you really need the explicit points of the path, or do you just need to use the rectilinear distance $|a_1-a_2|+|b_1-b_2|$? $\endgroup$ – RobPratt Sep 23 '20 at 1:31
  • $\begingroup$ One of the asumptions of my problem is that the vehicle can't move in euclidean space and it is restricted to move in orthogonal path betweem some predetermined points. I want to determine the optimal coordinate in the path that vehicle traverses based on the other assumptions in my problem. For example, I want to determine the optimal point for stopping in the path of vehicle... $\endgroup$ – Bhr Sep 23 '20 at 10:00
  • $\begingroup$ @Bahar, are you trying to define some dummy points based on your needs (determine the coordinates of specific points that can exist in the path between each pair of points) and then calculate the distance between theses dummy points and original points? $\endgroup$ – A.Omidi Sep 23 '20 at 13:14
  • $\begingroup$ Notice that your strict inequalities disallow $(x,y)=(a_1,b_2)$. Also, you are omitting the other orthogonal path that goes through $(a_2,b_1)$. I just wanted to make sure that's what you want to do. $\endgroup$ – RobPratt Sep 23 '20 at 14:14
  • $\begingroup$ @A.Omidi No, they aren't dummy nodes. the coordinate of these points is decision variables in my model. $\endgroup$ – Bhr Sep 23 '20 at 14:26

To enforce this disjunction, introduce a small constant $\epsilon>0$, binary variable $z$, and linear constraints \begin{align} a_1 +\epsilon(1- z)\le x &\le a_1 z+(a_2-\epsilon)(1-z)\\ b_2(1-z)+(b_1+\epsilon)z \le y &\le b_2 -\epsilon z \end{align}

To instead allow $(x,y)$ to appear along the orthogonal paths through $(a_1,b_2)$ or $(a_2,b_1)$ (four line segments), introduce binary variables $z_i$ for $i\in\{1,2,3,4\}$ and linear constraints $$ a_1 z_1 +(a_1+\epsilon) z_2 + (a_1+\epsilon) z_3 + a_2 z_2 \le x \le a_1 z_1+(a_2-\epsilon) z_2 +(a_2-\epsilon) z_3 + a_2 z_2 \\ (b_1+\epsilon)z_1 + b_2 z_2 + b_1 z_3 + (b_1+\epsilon)z_4 \le y \le (b_2-\epsilon) z_1 + b_2 z_2 + b_1 z_3 + (b_2-\epsilon) z_4 \\ z_1 + z_2 + z_3 + z_4 = 1 $$ The earlier formulation corresponds to $(z_1,z_2,z_3,z_4)=(z,1-z,0,0)$.

  • $\begingroup$ Thanks a lot for your help. $\endgroup$ – Bhr Sep 23 '20 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.