ข้อ จำกัด เฉพาะระยะทาง

Question

ฉันมีบางจุดที่มีพิกัดที่กำหนด $(a_i,b_i)$. ยานพาหนะสามารถเคลื่อนที่ไปมาระหว่างจุดเหล่านี้ตามระยะทางสี่เหลี่ยม ในรายละเอียดเพิ่มเติมเราพิจารณาว่าเส้นทางระหว่างจุดเป็นเส้นทางมุมฉาก

ในแบบจำลองทางคณิตศาสตร์ของปัญหาของฉันฉันต้องกำหนดพิกัดของจุดเฉพาะที่สามารถมีอยู่ในเส้นทางระหว่างจุดแต่ละคู่ตามเส้นทางมุมฉากระหว่างจุดเหล่านั้น ตัวอย่างเช่นหากยานพาหนะเคลื่อนที่ไปมาระหว่างจุดที่เฉพาะเจาะจงสองจุด$(a_1,b_1)$ และ $(a_2,b_2)$, พิกัดของจุดที่ต้องการ $(x,y)$ เป็นไปได้ $x=a_1$ และ $b_1<y<b_2$ หรือ $a_1<x<a_2$ และ $y=b_2$.

ฉันจะเขียนข้อ จำกัด ดังกล่าวในแบบจำลอง MIP (การเขียนโปรแกรมจำนวนเต็มแบบผสม) ได้อย่างไรซึ่งสามารถอธิบายคุณลักษณะที่กล่าวถึงข้างต้นได้

Answer 1

ในการบังคับใช้การแยกนี้ให้นำค่าคงที่เล็กน้อย $\epsilon>0$ตัวแปรไบนารี $z$และข้อ จำกัด เชิงเส้น \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}

---

เพื่ออนุญาตแทน $(x,y)$ จะปรากฏตามเส้นทางมุมฉากผ่าน $(a_1,b_2)$ หรือ $(a_2,b_1)$ (ส่วนสี่บรรทัด) แนะนำตัวแปรไบนารี $z_i$ สำหรับ $i\in\{1,2,3,4\}$ และข้อ จำกัด เชิงเส้น $$ 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 $$ การกำหนดก่อนหน้านี้สอดคล้องกับ $(z_1,z_2,z_3,z_4)=(z,1-z,0,0)$.