entfernungsspezifische Einschränkung

Question

Ich habe einige Punkte mit bestimmten Koordinaten $(a_i,b_i)$. Ein Fahrzeug kann sich basierend auf der rechteckigen Entfernung zwischen diesen Punkten bewegen. Im Detail betrachten wir, dass der Pfad zwischen Punkten ein orthogonaler Pfad ist.

In einem mathematischen Modell meines Problems muss ich die Koordinaten bestimmter Punkte bestimmen, die im Pfad zwischen jedem Punktpaar vorhanden sein können, entsprechend dem orthogonalen Pfad zwischen ihnen. Zum Beispiel, wenn das Fahrzeug zwischen zwei bestimmten Punkten fährt$(a_1,b_1)$ und $(a_2,b_2)$, die Koordinaten des gewünschten Punktes $(x,y)$ kann sein $x=a_1$ und $b_1<y<b_2$ oder $a_1<x<a_2$ und $y=b_2$.

Wie soll ich eine solche Einschränkung in mein MIP-Modell (Mixed Integer Programming) schreiben, das die oben genannte Funktion erklären kann?

Answer 1

Um diese Disjunktion zu erzwingen, führen Sie eine kleine Konstante ein $\epsilon>0$, binäre Variable $z$und lineare Einschränkungen \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}

---

Stattdessen zulassen $(x,y)$ entlang der orthogonalen Pfade durch erscheinen $(a_1,b_2)$ oder $(a_2,b_1)$ (vier Liniensegmente), führen Sie binäre Variablen ein $z_i$ zum $i\in\{1,2,3,4\}$ und lineare Einschränkungen $$ 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 $$ Die frühere Formulierung entspricht $(z_1,z_2,z_3,z_4)=(z,1-z,0,0)$.