ตัวแปรการตัดสินใจจำนวนเต็มเป็นดัชนี

Question

ปัญหาต่อไปนี้มีตัวแปรจำนวนเต็มสองตัวแปรเท่านั้น อย่างไรก็ตามจะปรากฏในดัชนีของพารามิเตอร์ ขอขอบคุณหากใครมีความคิดที่มีประสิทธิภาพในการแปลงเป็นรูปแบบการเขียนโปรแกรมจำนวนเต็มแบบบัญญัติ

$$ \begin{alignat*}{2} &&\max \quad & (d_y - d_x)^2 \\ &&\text{s.t.} \quad & d_y - d_x \geq \alpha \\ && & x,y \in \mathbb{Z}_+ \\ \end{alignat*} $$

Answer 1

สมมติ $x,y\in\{0,\dots,n\}$. ฉันคิดว่าฉันจะวนซ้ำสิ่งเหล่านี้$(n+1)^2$ จับคู่และรักษาคู่ที่ดีที่สุดที่ตรงตามข้อ จำกัด

แต่ถ้าคุณยืนยันในการเขียนโปรแกรมจำนวนเต็มแนะนำตัวแปรไบนารี $x_i$ และ $y_i$ สำหรับ $i\in\{0,\dots,n\}$โดยมีการตีความว่า $d_x=\sum_i d_i x_i$ และ $d_y=\sum_i d_i y_i$. ปัญหาคือการทำให้เกิดประโยชน์สูงสุด$$\left(\sum_i d_i (y_i - x_i)\right)^2$$ ขึ้นอยู่กับ \begin{align} \sum_i x_i &= 1\\ \sum_i y_i &= 1\\ \sum_i d_i (y_i - x_i) &\ge \alpha \end{align} หากคุณต้องการคุณสามารถทำให้วัตถุประสงค์เป็นเส้นตรงได้