인덱스로서의 정수 의사 결정 변수

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} 원하는 경우 목표를 선형화 할 수 있습니다.