混整數規劃(Mixed Integer Programming) 是線性規劃(Linear Programming)，加了整數的決策變數。其化簡標準形式可以寫成
$$ \begin{array}{l}\text{ min } c_{\mathcal{I}}x_\mathcal{I} + c_{\mathcal{R}}x_\mathcal{R} \\
\text{s.t } Ax = b \\ x := (x_\mathcal{I} , x_\mathcal{R}) \geq 0 \\
\end{array}$$
其中 $\mathcal{I}$ 為整數決策變數集 ，$\mathcal{R}$ 為實數決策變數集，$A$ 為已知係數
此模型已經有很多演算法可以求解詳細可以查關鍵字 branch & cut algorithm
理論上可以找到最佳決策 !! 但實務上整數規劃是 NP-Hard 問題，求解效率是議題!!，所以數學建模上我們希望 $|\mathcal{I}|$ 越小越好!!
而現實問題為何可使用整數規劃來數學建模那麼重要原因有二:
========================================
1. 現實問題物品的數量為整數個 !!
2. 邏輯的 True , False 可以用 0 - 1 決策變數表示!!
========================================
本文介紹一些筆者經驗常見邏輯限制式代表的意義，幫助大家更能理解如何數學建模。而對於有興趣的讀者，可以去閱讀 "Paul Williams : Model Building in Mathematical Programming" 這本書，有詳細的介紹。
+++++++++++++++++++++++++++++++++++
$ (A) \text{ 從集合裡面挑選元素 }$
+++++++++++++++++++++++++++++++++++
Let $i \in I , |I| < \infty , x_i \in \{0,1\} , cost : I \longrightarrow \mathbb{R} $ , denote $cost_i \in \mathbb{R}$
$x_i = 1 \Longleftrightarrow \text{ you select element in } i \in I $
$(A1)$ 從集合 $I$ 裡面挑選恰好一個元素
$$ \sum_{i \in I} x_i = 1 $$
========================================
註 : 學術上我們稱 $ \displaystyle{\sum_{i\in I} x_i =1 }$ 為 Special Ordered Sets of type 1 constraint ，記做 $SOS1(I)$ ，或寫作 $x(I) = 1 $
========================================
$(A2)$ 從集合 $I$ 裡面挑選至少一個元素
$$ \sum_{i\in I} x_i \geq 1 $$
$(A3)$ 從集合 $I$ 裡面至多挑選 $U$ 個，至少挑選 $L$個 ($L,U\in \mathbb{Z}$)
$$ L \leq \sum_{i\in I} x_i \leq U $$
$(A4)$ 如果挑選 $i \in I$ 都需要負擔/獲得 $c_i \in \mathbb{R}$
則總價格可以寫成 $$ cost(I):= \sum_{i\in I}c_i x_i $$
$(A5)$ 當然可以考慮子集合 $S \subseteq I$ ，則價格可以寫成
$$ cost(S):= \sum_{i\in S}c_i x_i $$
$(A6)$ 因為 $x_i = 1$ 代表的是種類 $i$ 有挑選，但如果同種類要計量可以用"整數"決策變數 $z_i \in \mathbb{Z^{\geq 0 }}= \{0,1,2,3,4,....\}$
$$ qcost(S):= \sum_{i\in S}c_i z_i $$
當然還可以考慮集合的集合 $\mathcal{F}\subseteq 2^{I}= \{S : S\subseteq I \}$，其中 $2^{I}$ 為 PowerSet of $I$ ，還可以定義 $Cost : 2^{I} \longrightarrow \mathbb{R}$ 類比 $(A4) , (A5)$ 限制式，可以定義
$$(A7) \quad Cost(\mathcal{F}) := \sum_{S \in \mathcal{F}}cost(S) $$
$$(A8) \quad QCost(\mathcal{F}) := \sum_{S \in \mathcal{F}}qcost(S)$$
如果 $z_i \leq U$ 則我們還可以增加一個維度只用 $0-1$變數 $x_{ij}$ 來刻劃 $z_i$ , $x_i$
$$(A9) \left\{\begin{array}{c} \displaystyle{z_i := \sum^{U}_{j=0} j \cdot x_{ij} \quad \forall i \in I} \\ \displaystyle{x_i:= \sum^{U}_{j=0} x_{ij}\leq 1 \quad \forall i \in I } \\ x_{ij} \in \{0,1\} \quad \forall (i,j) \in I \times \{0,1,2,....U\} \\ \end{array}\right. $$
+++++++++++++++++++++++++++++++++++
$(B) \text{ if - then constraints} $
+++++++++++++++++++++++++++++++++++
考慮 $i \in I$ , $y_i \in \{0,1\}$ ，記作 $\bar{y}_i = 1-y_i$
$(B1)$ 四大基本，可用來串接邏輯 Proposition
if $y_1 = 1$ then $y_2 = 1 :\qquad y_1 \leq y_2 $
if $y_1 = 1$ then $y_2 = 0 :\qquad y_1 \leq 1-y_2 \Longrightarrow y_1 \leq \bar{y}_2 $
if $y_1 = 0$ then $y_2 = 1 :\qquad 1-y_1 \leq y_2 \Longrightarrow \bar{y}_1 \leq y_2 $
if $y_1 = 0$ then $y_2 = 0 :\qquad 1- y_1 \leq 1- y_2 \Longrightarrow \bar{y}_1 \leq \bar{y}_2$
============================================
例如 : $P \Longrightarrow Q $ , $P\Longrightarrow R$ , $R\Longrightarrow S$ , $Q \Longrightarrow S$ 可以寫成
$$ \left\{\begin{array}{c} y_P \leq y_Q \\ y_P \leq y_R \\ y_R \leq y_S \\ y_Q \leq y_S \\ \end{array}\right. $$
事實上這可以畫成一個邏輯有向網路圖(Directed Graph) $G(N,A)$ 邊的方向性即為 "$\leq$"，如例子: $N=\{P,Q,R,S\}$ , $A = \{ (P,Q), (P,R), (R,S) , (Q,S)\}$
=============================================
Let $a, x \in \mathbb{R}^J , b \in \mathbb{R}$ , $$ [a,x] := \sum_{j \in J} a_{j}x_j$$
===================================
註 : $[a,x]\geq b$ 可以改寫成 $-b \leq -[a,x]$
===================================
再來介紹經典的"開啟"限制式 !!
$(B2)$ if $(y = 1)$ then $[a,x] \leq b $ , else $[a,x] < \infty $ redundant !!
$$ [a,x] \leq b + M(1-y) $$
註: $M$ 是充分大常數，學術上稱為 Capital M/Big M Constraint，但不能太大(求解上不穩定)，最好的 $M := -b + \underset{x \in \mathbb{R}^J}{\text{sup }}[a,x] $
再來是限制式"開啟" !!
$(B3)$ if ( $[a,x] \leq b$ ) then $y=1$ , else : redundant !!
$$ b + \epsilon \leq [a,x] + My $$
========================================
證: 等價於 $y = 0 \Longrightarrow [a,x] > b $ ，右邊引入極小的數 $\epsilon$ , 變成 $[a,x] \geq b + \epsilon$，根據$(B2)$最後可寫成 $ b + \epsilon \leq [a,x] + My $
最好的$ M:= b + \epsilon - \underset{x \in \mathbb{R}^J}{\text{inf }}[a,x]$
========================================
註 : 如果$(B2)(B3)$條件是 $(y = 0)$ 只要把 $y$ 代換成 $\bar{y}$ 即可 !!
========================================
結合 $(B2) (B3)$ 概念可以有 $(B4) , (B5) $
$(B4)$ 開關限制式 $[a,x] \leq b \Longleftrightarrow y =1 $
$$\left\{\begin{array}{c}
[a,x] \leq b + M(1-y) \\
b + \epsilon \leq [a,x] + My \\
\end{array}\right.$$
$(B5)$ 限制式開限制式 $[a_1,x_1]\leq b_1 \Longrightarrow [a_2,x_2]\leq b_2 $
$$ \left\{\begin{array}{c} b + \epsilon \leq [a_1,x_1] + My \\ [a_2,x_2] \leq b + M(1-y) \\ \end{array}\right.$$
========================================
證: 串聯 $[a_1,x_1]\leq b_1 \Longrightarrow y = 1$ , $y = 1 \Longrightarrow [a_2,x_2]\leq b_2$
========================================
+++++++++++++++++++++++++++++++++++
$(C)$ And + Or Constraints !!
+++++++++++++++++++++++++++++++++++
$(C1)$ if $y = 1$ then $\underset{i \in I}{\bigwedge} ([a_i,x_i]\leq b_i)$ (Right-And Constraints)
$$\left\{\begin{array}{c} [a_1,x_1]\leq b_1 + M_1(1-y) \\ [a_2,x_2]\leq b_2 + M_2(1-y) \\ [a_3,x_3]\leq b_3 + M_3(1-y) \\ ... \\ [a_{|I|},x_{|I|}]\leq b_{|I|} +M_{|I|}(1-y) \\ \end{array}\right. $$
Let $ \forall i \in I \quad y_i \in \{0,1\}$
$(C2)$ if $y = 1$ then $\underset{i \in I}{\bigvee}([a_i,x_i]\leq b_i) $ (Right-Or Constraints)
$$\left\{\begin{array}{c} [a_1,x_1]\leq b_1 + M_1(1-y_1) \\ [a_2,x_2]\leq b_2 + M_2(1-y_2) \\ [a_3,x_3]\leq b_3 + M_3(1-y_3) \\ ... \\ [a_{|I|},x_{|I|}]\leq b_{|I|} +M_{|I|}(1-y_{|I|}) \\
\displaystyle{y \leq \sum_{i\in I} y_i} \\
\end{array}\right. $$
==============================================
註: 學術上稱 $(C2)$ 叫 disjunctive constraints ，可以輕易推廣成
if $y = 1$ then $\displaystyle{\underset{i \in I}{\bigvee}\left\{\underset{j\in J_i}{\bigwedge}([a_j,x_j]\leq b_j)\right\}} $
==============================================
$(C3)$ if $(\underset{i \in I}{\bigwedge}([a_i,x_i]\leq b_i)$ then $y = 1 $ (Left-And Constraints)
$$\left\{\begin{array}{c} b_1 + \epsilon_1 \leq [a_1,x_1] + M_1(1-y_1) \\ b_2 + \epsilon_2 \leq [a_2,x_2] + M_2(1-y_2) \\ b_3 + \epsilon_3 \leq [a_3,x_3] + M_3(1-y_3) \\ ... \\ b_{|I|} + \epsilon_{|I|} \leq [a_{|I|},x_{|I|}] + M_{|I|}(1-y_{|I|}) \\
\displaystyle{ (1-y) \leq \sum_{i\in I} y_i} \\
\end{array}\right. $$
========================================
證: 等價於 if $y = 0$ then $\underset{i \in I}{\bigvee}([a_i,x_i] > b_i) $
========================================
$(C4)$ if $(\underset{i \in I}{\bigvee}([a_i,x_i]\leq b_i)$ then $y = 1 $ (Left-Or Constraints)
$$\left\{\begin{array}{c} b_1 + \epsilon_1 \leq [a_1,x_1] + M_1 \cdot y \\ b_2 + \epsilon_2 \leq [a_2,x_2] + M_2 \cdot y \\ b_3 + \epsilon_3 \leq [a_3,x_3] + M_3 \cdot y \\ ... \\ b_{|I|} + \epsilon _{|I|}\leq [a_{|I|},x_{|I|}] + M_{|I|}\cdot y \\
\end{array}\right. $$
========================================
證: 等價於 if $y = 0$ then $\underset{i \in I}{\bigwedge}([a_i,x_i] > b_i) $
========================================
$(C5)$ 互斥或，只有 $ [a_i,x_i] \leq b_i $ 其中之一會發生 (Disjoint Or Constaints)
$$\left\{\begin{array}{c} [a_1,x_1]\leq b_1 + M_1(1-y_1) \\ [a_2,x_2]\leq b_2 + M_2(1-y_2) \\ [a_3,x_3]\leq b_3 + M_3(1-y_3) \\ ... \\ [a_{|I|},x_{|I|}]\leq b_{|I|} +M_{|I|}(1-y_{|I|}) \\
\displaystyle{\sum_{i\in I} y_i = 1} \\
\end{array}\right. $$
+++++++++++++++++++++++++++++++++++
$(D)$ 離散時間狀態網路圖(Time-State-Network)
+++++++++++++++++++++++++++++++++++
考慮離散時間 $t \in T := \{0,1,2,........U\}$ (單位時刻點集)
考慮離散狀態向量集$\displaystyle{i\in(i_1,i_2,i_3,....,i_n) \in I = \prod^{n}_{j=1} I_{j}} $
註: 狀態向量集可能隨著時間 $t$ 不同而不同，即 $I^{(t)}$
考慮狀態-時間函數 $\displaystyle{v : T \times I \longrightarrow } \{0,1\}$
很明顯我們一個時間點，只會有一個狀態
$$(D1) \quad \forall t \in T \quad \sum_{i\in I} v_{it} = 1 \quad \text{或寫成 } v_t(I) = 1 $$
如果我們看 $i$ 的每個分量，很明顯每個分量也只能選一種
因為$(D1)$的決策變數非常多，事實上如果 State 間是獨立的，只要定義 $$ X^{jt}_{i_j} = 1 \Longleftrightarrow \text{at time }t , j\text{-th state is } i_j $$ (只需要 $|T| \sum^{n}_{j = 1}|I_j|$ 個決策變數)
$$ (D2) \quad \forall t\in T \quad \forall j \in \{1,2,3,...n\} \quad \sum_{i_j \in I_j} X^{jt}_{i_j} = 1 $$
[小結] 在整數規劃裡，邏輯 0-1 是強大數學建模的工具，但邏輯的串聯是困難的部分使用正確的限制式需要時間練習與經驗，而書本鮮少提到，故筆者以此文分享給需要的讀者，更多限制式技巧如 TakeMin , TakeMax , Absolute , Piecewise Linear 可以參考 FICO Xpress 教學文件 ，關於圖論(Graph) 限制式，如 TSP，VRP，Shortest Path，Multi-commodity Flow 等等日後會再寫一篇 !!
$$ \begin{array}{l}\text{ min } c_{\mathcal{I}}x_\mathcal{I} + c_{\mathcal{R}}x_\mathcal{R} \\
\text{s.t } Ax = b \\ x := (x_\mathcal{I} , x_\mathcal{R}) \geq 0 \\
\end{array}$$
其中 $\mathcal{I}$ 為整數決策變數集 ，$\mathcal{R}$ 為實數決策變數集，$A$ 為已知係數
此模型已經有很多演算法可以求解詳細可以查關鍵字 branch & cut algorithm
理論上可以找到最佳決策 !! 但實務上整數規劃是 NP-Hard 問題，求解效率是議題!!，所以數學建模上我們希望 $|\mathcal{I}|$ 越小越好!!
而現實問題為何可使用整數規劃來數學建模那麼重要原因有二:
========================================
1. 現實問題物品的數量為整數個 !!
2. 邏輯的 True , False 可以用 0 - 1 決策變數表示!!
========================================
本文介紹一些筆者經驗常見邏輯限制式代表的意義，幫助大家更能理解如何數學建模。而對於有興趣的讀者，可以去閱讀 "Paul Williams : Model Building in Mathematical Programming" 這本書，有詳細的介紹。
+++++++++++++++++++++++++++++++++++
$ (A) \text{ 從集合裡面挑選元素 }$
+++++++++++++++++++++++++++++++++++
Let $i \in I , |I| < \infty , x_i \in \{0,1\} , cost : I \longrightarrow \mathbb{R} $ , denote $cost_i \in \mathbb{R}$
$x_i = 1 \Longleftrightarrow \text{ you select element in } i \in I $
$(A1)$ 從集合 $I$ 裡面挑選恰好一個元素
$$ \sum_{i \in I} x_i = 1 $$
========================================
註 : 學術上我們稱 $ \displaystyle{\sum_{i\in I} x_i =1 }$ 為 Special Ordered Sets of type 1 constraint ，記做 $SOS1(I)$ ，或寫作 $x(I) = 1 $
========================================
$(A2)$ 從集合 $I$ 裡面挑選至少一個元素
$$ \sum_{i\in I} x_i \geq 1 $$
$(A3)$ 從集合 $I$ 裡面至多挑選 $U$ 個，至少挑選 $L$個 ($L,U\in \mathbb{Z}$)
$$ L \leq \sum_{i\in I} x_i \leq U $$
$(A4)$ 如果挑選 $i \in I$ 都需要負擔/獲得 $c_i \in \mathbb{R}$
則總價格可以寫成 $$ cost(I):= \sum_{i\in I}c_i x_i $$
$(A5)$ 當然可以考慮子集合 $S \subseteq I$ ，則價格可以寫成
$$ cost(S):= \sum_{i\in S}c_i x_i $$
$(A6)$ 因為 $x_i = 1$ 代表的是種類 $i$ 有挑選，但如果同種類要計量可以用"整數"決策變數 $z_i \in \mathbb{Z^{\geq 0 }}= \{0,1,2,3,4,....\}$
$$ qcost(S):= \sum_{i\in S}c_i z_i $$
當然還可以考慮集合的集合 $\mathcal{F}\subseteq 2^{I}= \{S : S\subseteq I \}$，其中 $2^{I}$ 為 PowerSet of $I$ ，還可以定義 $Cost : 2^{I} \longrightarrow \mathbb{R}$ 類比 $(A4) , (A5)$ 限制式，可以定義
$$(A7) \quad Cost(\mathcal{F}) := \sum_{S \in \mathcal{F}}cost(S) $$
$$(A8) \quad QCost(\mathcal{F}) := \sum_{S \in \mathcal{F}}qcost(S)$$
如果 $z_i \leq U$ 則我們還可以增加一個維度只用 $0-1$變數 $x_{ij}$ 來刻劃 $z_i$ , $x_i$
$$(A9) \left\{\begin{array}{c} \displaystyle{z_i := \sum^{U}_{j=0} j \cdot x_{ij} \quad \forall i \in I} \\ \displaystyle{x_i:= \sum^{U}_{j=0} x_{ij}\leq 1 \quad \forall i \in I } \\ x_{ij} \in \{0,1\} \quad \forall (i,j) \in I \times \{0,1,2,....U\} \\ \end{array}\right. $$
+++++++++++++++++++++++++++++++++++
$(B) \text{ if - then constraints} $
+++++++++++++++++++++++++++++++++++
考慮 $i \in I$ , $y_i \in \{0,1\}$ ，記作 $\bar{y}_i = 1-y_i$
$(B1)$ 四大基本，可用來串接邏輯 Proposition
if $y_1 = 1$ then $y_2 = 1 :\qquad y_1 \leq y_2 $
if $y_1 = 1$ then $y_2 = 0 :\qquad y_1 \leq 1-y_2 \Longrightarrow y_1 \leq \bar{y}_2 $
if $y_1 = 0$ then $y_2 = 1 :\qquad 1-y_1 \leq y_2 \Longrightarrow \bar{y}_1 \leq y_2 $
if $y_1 = 0$ then $y_2 = 0 :\qquad 1- y_1 \leq 1- y_2 \Longrightarrow \bar{y}_1 \leq \bar{y}_2$
============================================
例如 : $P \Longrightarrow Q $ , $P\Longrightarrow R$ , $R\Longrightarrow S$ , $Q \Longrightarrow S$ 可以寫成
$$ \left\{\begin{array}{c} y_P \leq y_Q \\ y_P \leq y_R \\ y_R \leq y_S \\ y_Q \leq y_S \\ \end{array}\right. $$
事實上這可以畫成一個邏輯有向網路圖(Directed Graph) $G(N,A)$ 邊的方向性即為 "$\leq$"，如例子: $N=\{P,Q,R,S\}$ , $A = \{ (P,Q), (P,R), (R,S) , (Q,S)\}$
=============================================
Let $a, x \in \mathbb{R}^J , b \in \mathbb{R}$ , $$ [a,x] := \sum_{j \in J} a_{j}x_j$$
===================================
註 : $[a,x]\geq b$ 可以改寫成 $-b \leq -[a,x]$
===================================
再來介紹經典的"開啟"限制式 !!
$(B2)$ if $(y = 1)$ then $[a,x] \leq b $ , else $[a,x] < \infty $ redundant !!
$$ [a,x] \leq b + M(1-y) $$
註: $M$ 是充分大常數，學術上稱為 Capital M/Big M Constraint，但不能太大(求解上不穩定)，最好的 $M := -b + \underset{x \in \mathbb{R}^J}{\text{sup }}[a,x] $
再來是限制式"開啟" !!
$(B3)$ if ( $[a,x] \leq b$ ) then $y=1$ , else : redundant !!
$$ b + \epsilon \leq [a,x] + My $$
========================================
證: 等價於 $y = 0 \Longrightarrow [a,x] > b $ ，右邊引入極小的數 $\epsilon$ , 變成 $[a,x] \geq b + \epsilon$，根據$(B2)$最後可寫成 $ b + \epsilon \leq [a,x] + My $
最好的$ M:= b + \epsilon - \underset{x \in \mathbb{R}^J}{\text{inf }}[a,x]$
========================================
註 : 如果$(B2)(B3)$條件是 $(y = 0)$ 只要把 $y$ 代換成 $\bar{y}$ 即可 !!
========================================
結合 $(B2) (B3)$ 概念可以有 $(B4) , (B5) $
$(B4)$ 開關限制式 $[a,x] \leq b \Longleftrightarrow y =1 $
$$\left\{\begin{array}{c}
[a,x] \leq b + M(1-y) \\
b + \epsilon \leq [a,x] + My \\
\end{array}\right.$$
$(B5)$ 限制式開限制式 $[a_1,x_1]\leq b_1 \Longrightarrow [a_2,x_2]\leq b_2 $
$$ \left\{\begin{array}{c} b + \epsilon \leq [a_1,x_1] + My \\ [a_2,x_2] \leq b + M(1-y) \\ \end{array}\right.$$
========================================
證: 串聯 $[a_1,x_1]\leq b_1 \Longrightarrow y = 1$ , $y = 1 \Longrightarrow [a_2,x_2]\leq b_2$
========================================
+++++++++++++++++++++++++++++++++++
$(C)$ And + Or Constraints !!
+++++++++++++++++++++++++++++++++++
$(C1)$ if $y = 1$ then $\underset{i \in I}{\bigwedge} ([a_i,x_i]\leq b_i)$ (Right-And Constraints)
$$\left\{\begin{array}{c} [a_1,x_1]\leq b_1 + M_1(1-y) \\ [a_2,x_2]\leq b_2 + M_2(1-y) \\ [a_3,x_3]\leq b_3 + M_3(1-y) \\ ... \\ [a_{|I|},x_{|I|}]\leq b_{|I|} +M_{|I|}(1-y) \\ \end{array}\right. $$
Let $ \forall i \in I \quad y_i \in \{0,1\}$
$(C2)$ if $y = 1$ then $\underset{i \in I}{\bigvee}([a_i,x_i]\leq b_i) $ (Right-Or Constraints)
$$\left\{\begin{array}{c} [a_1,x_1]\leq b_1 + M_1(1-y_1) \\ [a_2,x_2]\leq b_2 + M_2(1-y_2) \\ [a_3,x_3]\leq b_3 + M_3(1-y_3) \\ ... \\ [a_{|I|},x_{|I|}]\leq b_{|I|} +M_{|I|}(1-y_{|I|}) \\
\displaystyle{y \leq \sum_{i\in I} y_i} \\
\end{array}\right. $$
==============================================
註: 學術上稱 $(C2)$ 叫 disjunctive constraints ，可以輕易推廣成
if $y = 1$ then $\displaystyle{\underset{i \in I}{\bigvee}\left\{\underset{j\in J_i}{\bigwedge}([a_j,x_j]\leq b_j)\right\}} $
==============================================
$(C3)$ if $(\underset{i \in I}{\bigwedge}([a_i,x_i]\leq b_i)$ then $y = 1 $ (Left-And Constraints)
$$\left\{\begin{array}{c} b_1 + \epsilon_1 \leq [a_1,x_1] + M_1(1-y_1) \\ b_2 + \epsilon_2 \leq [a_2,x_2] + M_2(1-y_2) \\ b_3 + \epsilon_3 \leq [a_3,x_3] + M_3(1-y_3) \\ ... \\ b_{|I|} + \epsilon_{|I|} \leq [a_{|I|},x_{|I|}] + M_{|I|}(1-y_{|I|}) \\
\displaystyle{ (1-y) \leq \sum_{i\in I} y_i} \\
\end{array}\right. $$
========================================
證: 等價於 if $y = 0$ then $\underset{i \in I}{\bigvee}([a_i,x_i] > b_i) $
========================================
$(C4)$ if $(\underset{i \in I}{\bigvee}([a_i,x_i]\leq b_i)$ then $y = 1 $ (Left-Or Constraints)
$$\left\{\begin{array}{c} b_1 + \epsilon_1 \leq [a_1,x_1] + M_1 \cdot y \\ b_2 + \epsilon_2 \leq [a_2,x_2] + M_2 \cdot y \\ b_3 + \epsilon_3 \leq [a_3,x_3] + M_3 \cdot y \\ ... \\ b_{|I|} + \epsilon _{|I|}\leq [a_{|I|},x_{|I|}] + M_{|I|}\cdot y \\
\end{array}\right. $$
========================================
證: 等價於 if $y = 0$ then $\underset{i \in I}{\bigwedge}([a_i,x_i] > b_i) $
========================================
$(C5)$ 互斥或，只有 $ [a_i,x_i] \leq b_i $ 其中之一會發生 (Disjoint Or Constaints)
$$\left\{\begin{array}{c} [a_1,x_1]\leq b_1 + M_1(1-y_1) \\ [a_2,x_2]\leq b_2 + M_2(1-y_2) \\ [a_3,x_3]\leq b_3 + M_3(1-y_3) \\ ... \\ [a_{|I|},x_{|I|}]\leq b_{|I|} +M_{|I|}(1-y_{|I|}) \\
\displaystyle{\sum_{i\in I} y_i = 1} \\
\end{array}\right. $$
+++++++++++++++++++++++++++++++++++
$(D)$ 離散時間狀態網路圖(Time-State-Network)
+++++++++++++++++++++++++++++++++++
考慮離散時間 $t \in T := \{0,1,2,........U\}$ (單位時刻點集)
考慮離散狀態向量集$\displaystyle{i\in(i_1,i_2,i_3,....,i_n) \in I = \prod^{n}_{j=1} I_{j}} $
註: 狀態向量集可能隨著時間 $t$ 不同而不同，即 $I^{(t)}$
考慮狀態-時間函數 $\displaystyle{v : T \times I \longrightarrow } \{0,1\}$
很明顯我們一個時間點，只會有一個狀態
$$(D1) \quad \forall t \in T \quad \sum_{i\in I} v_{it} = 1 \quad \text{或寫成 } v_t(I) = 1 $$
如果我們看 $i$ 的每個分量，很明顯每個分量也只能選一種
因為$(D1)$的決策變數非常多，事實上如果 State 間是獨立的，只要定義 $$ X^{jt}_{i_j} = 1 \Longleftrightarrow \text{at time }t , j\text{-th state is } i_j $$ (只需要 $|T| \sum^{n}_{j = 1}|I_j|$ 個決策變數)
$$ (D2) \quad \forall t\in T \quad \forall j \in \{1,2,3,...n\} \quad \sum_{i_j \in I_j} X^{jt}_{i_j} = 1 $$
[小結] 在整數規劃裡，邏輯 0-1 是強大數學建模的工具，但邏輯的串聯是困難的部分使用正確的限制式需要時間練習與經驗，而書本鮮少提到，故筆者以此文分享給需要的讀者，更多限制式技巧如 TakeMin , TakeMax , Absolute , Piecewise Linear 可以參考 FICO Xpress 教學文件 ，關於圖論(Graph) 限制式，如 TSP，VRP，Shortest Path，Multi-commodity Flow 等等日後會再寫一篇 !!
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2017.09
留言
張貼留言