distance specific constraint

Question

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?

Answer 1

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)$.