本篇介紹一些筆者認為重要的整數規劃-圖形，邏輯建模技巧與概念，關於整數規劃的用途，可先參考之前這篇:
http://discoverforgottenmath.blogspot.tw/2017/09/why-integer-programming-is-important-in.html
而建模技巧是把日常生活中的邏輯給正確的連結到方程式上!!
以下我們都把 $X \in \{0,1\}$ 視為 boolean 決策變數
=======================================
刻劃出點 Node $i , j$ 跟邊 Arc $(i,j)$ 關係
=======================================
定義:
$X_{i} = 1 \text{ iff } $ 我選擇了點 $i$
$X_{ij} = 1 \text{ iff } $ 我選擇了邊 $(i,j)$
$$(E1) \quad \text{if $(i,j)$ is selected then ($i$ and $j$) are selected} $$ $$ \left\{\begin{array}{c} X_{(i,j)}\leq X_i \\ X_{(i,j)}\leq X_j \\ \end{array}\right.$$ $$(E2) \quad \text{if ($i$ and $j$) are selected then $(i,j)$ is selected } $$ $$ X_{i}+X_{j} \leq 1+X_{(i,j)} $$
$(E1)$ 是現實生活中自然的邏輯:
意涵代表，我選擇了這條邊 $(i,j)$ 則我自然會 cover $i , j$ 這兩個點
$(E2)$ 則不一定會有的邏輯，需思考 $(i,j)$ 的定義
例如: 我定義 $(i,j)$ 為直接從 $i$ 走到 $j$
則走路徑 $(i \rightarrow j \rightarrow k \rightarrow w)$
則 $X_{i}=1 , X_{w} =1 $ 但是 $X_{(i,w)} = 0$ ，就不滿足 $(E2)$ 的邏輯
註: 結合 $(E1)$ and $(E2)$ 兩個邏輯事實上就是"線性化"，以下的非線性邏輯
$$ X_{(i,j)} = X_{i}X_{j} $$ ，而根據遞迴我們就有辦法線性化連乘的 boolean $$X_{S} = \prod_{s\in S}X_{s}$$
[精簡] 為了讓符號跟精簡，我們可以令 $a = (i,j)$ ，把 $(E1)$ , $(E2)$ 寫成
$$ X_{a} \leq X_i \quad X_{a}\leq X_{j} \quad X_{i}+X_{j} \leq 1+X_{a}$$
[思考] 關於 $(i,j)$ 定義需要小心提防，以下列舉
(1) $(i,j)$ 是否有方向性 ?? ，有方向性則要 $X_{(i,j)}$ ，$X_{(j,i)}$ 是不同的意義，無方向性我們正式的定義 $X_{[i,j]}$ ，其中 $[i,j]$ 為 equivalence class 裡的表現元。
(2) $(i,j)$ 是代表直接拜訪的邊?? 還是 OD-pair (起點-終點)??
如果是 $OD-pair$ 則我們必須使用探訪演算法，如 BFS , DFS , Union-Find 來確立 $(i,j)$ 是否存在，來定義 $X_{ij}$
=======================================
同理拓展至路徑 Path 與邊 Arc 的關係
=======================================
令 $p$ 為長度 $n$ 的路徑，可表示為 $(i_1 \rightarrow i_2 \rightarrow i_3 , .... \rightarrow i_n) $
定義 $X_p = 1 \text{ iff }$ 我選擇了路徑 $p$
$$ (P1) \text{如果選擇了路徑 $p$ 則 } \overbrace{(i_1,i_2)}^{a_1},\overbrace{(i_2,i_3)}^{a_2},...\overbrace{(i_{n-1},i_{n})}^{a_{n-1}}
\text{ 就被選擇了} $$
$$\left\{\begin{array}{l} X_{p} \leq X_{a_1} \\ X_{p} \leq X_{a_2} \\ X_{p} \leq X_{a_3}\\ ... \\ X_{p} \leq X_{a_{n-1}} \\ \end{array}\right.$$
$$ (P2) \text{如果選擇了 }\overbrace{(i_1,i_2)}^{a_1},\overbrace{(i_2,i_3)}^{a_2},...\overbrace{(i_{n-1},i_{n})}^{a_{n-1}} \text{則路徑 $p$ 就被選擇了} $$
$$ \sum_{k=1}^{n-1}X_{a_{k}} \leq (n-2) + X_{p} $$
[例子: 火車]
在交通運輸中，如果"火車" 會有"路徑"$p$ ，邊$a$相當於站與站之間的鐵軌，站相當於 $i,j$。
我們可以令火車為 $k \in TRA$ 分別定義 $X^{k}_{p}$ , $X^{k}_{a}$ , $X^{k}_{i}$
如果每一台火車有考慮的已知路徑集 $p \in P_k$，結合了$(E1)$ , $(E2)$ , $(P1)$ , $(P2)$ ，感謝遞移性，於是我們能夠描述出那些火車選擇了那些路徑後 $X^{k}_{p}$ 後，路徑-鐵軌-站的複雜 "0-1邏輯"關係 (那些火車有經過哪些邊，有經過哪些點 ... )
[抽象推廣]
由以上我們會發現，現實生活中，有小結構 $s$ 與大結構 $S$
則當我選擇大結構 $X_{S}$ 我就會 cover 小結構的所有元素$s$，更嚴謹來說是所有子集合 $S' \subset S$ 都會被 cover
可以寫成 $ X_{S} \leq X_{S'} $ ，就如同 $(E1)$ , $(P1)$ 一樣
反之如果某些情境下，小結構 $s$ 一部分都選了則代表大結構 $S$選了
則式子會是
$$ \sum_{s \in S}X_{s} \leq (|S|-1) + X_{S} $$
===========================================
重複經過，虛擬點的邏輯
============================================
在現實生活中，我們可能會重複經過一些點，例如:
$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$
此時我們的 $X_1 , X_{12}$ 就不夠用了。有兩種建模方式可解決:
(1) 增加維度，定義重複指標 $r$ : $X^{r}_{i}$, $X^{r}_{ij}$
例如 : $X^{2}_{12} = 1$ 代表第二次經過 $(1,2)$ 這條邊
而我們可以一個簡單的邏輯來描述重複的概念
$$ \text{第 }(r+1) \text{ 次選擇存在 } \Longrightarrow \text{第 }r \text{ 次選擇存在} $$
$$ (R1) \bigwedge_{r=1,2,...} \bigwedge_{i\in V} X^{r+1}_{i} \leq X^{r}_{i} $$
以上的例子就會變為:
$$\left\{\begin{array}{c} X^{2}_{1} \leq X^{1}_{1}\\
X^{2}_{2} \leq X^{1}_{2} \\
X^{2}_{12} \leq X^{1}_{12} \\ \end{array}\right.$$
(2) 拓展點集 $V^{*} = V \times V' \times V'' \times ... $，定義虛擬點 $i' , i'' , i''' ,.....i''''''$
其中 $[i] = \{i' , i'' , i''' ,.....i'''''' \}$ , $V^{*} = \text{disjoint union of those } [i]$
則可利用下面不等式描述概念
$$ \bigwedge_{[i]} \left( X_{i''''''} \leq... \leq X_{i'} \leq X_{i} \right) $$
實作上可以把點編號 $i = 1,2,3....|V|$ ，虛擬點 $i'$的編號滿足 $(i' - i) mod |V| = 0$
以上的例子: 就變成 $1 \rightarrow 2 \rightarrow 1' \rightarrow 2'$ ，假設 $V=\{1,2\}$
則路徑就變成 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ ，其中 $(3-1) mod 2 = 0$ ,代表 $1,3$ 是同一個點 !!
於是限制式就變成 $$\left\{\begin{array}{c} X_{3} \leq X_{1}\\ X_{4} \leq X_{2} \\ X_{34}\leq X_{12} \\ \end{array}\right.$$
[預處理下標]
關於虛擬點 $i'$，半虛擬邊$(i',j)$，虛擬邊$(i',j')$產生下標的方式，需使用DFS窮舉路徑演算法，並修改探訪停止條件，以及固定路徑的 $|p|$上界，方可產生！！
再來講解重要的"選擇集" 的數學建模 !!
================================================
if something happened , we have some different choices to do
================================================
某些情境集 $e\in E$ ，我們假設情境為互斥且恰有一個一定會發生，
$$\displaystyle{\sum_{e\in E}X_e =1 }$$
我們考慮當某件事 $e$ 發生以後 $X_e =1$ ，我們有一些選擇 $c$ 在選擇集合裡 $C_e$。
量化選擇 $y_{c} \in \mathbb{\mathbb{Z}} \text{ or } \mathbb{R}$ , 而當你量化選擇 $y_{c}$後，會有一些"已知"的權重$\omega_{c}$ 。而如果我想要表達這個加權後值是多少的時候:
即條件加權決策變數 $<\omega,y>|E$ (原創定義)
$$\left\{\begin{array}{ll} (C1) & \displaystyle{<\omega,y>|E = \sum_{e\in E}\sum_{c\in C_e}\omega_{c}y_{c}} \\ \text{s.t} & \\ (C2) & \forall (e,c) \in E \times C_e \quad y_{c} \in [0, M_{c}X_{e}]\\ (C3) &\displaystyle{\sum_{e\in E}X_e =1 } \\ \end{array}\right.$$
其中
$(C2)$ 也可以寫成 $ 0 \leq y_{c} \leq M_{c}X_{e} $
代表說如果 $e$ 沒有發生，我就讓 $y_{c} = 0 $ ，如果 $e$ 有發生，我就讓 $y_{c}$ 介於 $[0,M_{c}]$ 之間 ($M_{c}$ 為給定上界)
$(C1)$ 代表權重的值，為所有情境可能的加總
以下舉個實際例子:
----------------------------------------------------------------------
假如超商有商品集: $c \in C =\{雨傘 um，雨衣 rc ，防曬乳ss，墨鏡 sg \} $
價格分別為
$\omega_{um} = 100 $，$ \omega_{rc} = 50 $，$ \omega_{ss} = 80 $，$\omega_{sg} = 120 $
情境 $e \in E = \{下雨 rain，太陽 sun \}$
於是我們可以刻劃出以下的邏輯限制式
如果"明天" rain，則消費者可能會購買 um , rc 即 $C_{rain} = \{ um,rc \}$
如果"明天" sun，則消費者可能會購買 ss , sg 即 $C_{sun} = \{ ss,sg \}$
假設每位消費者至多只能同種商品 10 款 !! 即 $ \forall c \in C , M_{c} = 10 $
令 $y$ 為每位消費者購買的數量
則每位消費者購買的金額可以寫成
$$ \text{購買金額 : } 100 y_{um} + 50 y_{rc} + 80 y_{ss} + 120 y_{sg}$$
而且必須滿足以下方程組 ([C])
$X_{rain} + X_{sun} = 1 $
$ 0 \leq y_{um} \leq 10 \cdot X_{rain} $
$ 0 \leq y_{rc} \leq 10 \cdot X_{rain} $
$ 0 \leq y_{ss} \leq 10 \cdot X_{sun} $
$ 0 \leq y_{sg} \leq 10 \cdot X_{sun} $
其中決策變數為 6維 : 4 個整數$y$(商品購買數) + 2個 0-1邏輯 $X$
如果我們有很多消費者 $i \in I$
則
$$ \text{總體營業額: } \sum_{i\in I} \left(100 y^{i}_{um} + 50 y^{i}_{rc} + 80 y^{i}_{ss} + 120 y^{i}_{sg} \right)$$
而且要滿足 $ \bigwedge_{i \in I} [C]_i $
----------------------------------------------------------------------
註: 現實來說，每位消費者的決策變數 $y^{i}$ 是由"各自"決定，所以總體營業額應該是個賽局理論的量 !!
註: 選擇集的數學建模告訴我們，現實生活中的"量"，可以寫成眾多決策組合的疊加，而且是線性聯立不等式 !!
註: 現實生活 $E$ 可以是多層， 邏輯先後 path ，甚至是 hypergraph
=========================================================
連續時間與排列限制式
=========================================================
給定$n$ 個事件 $i \in I = \{ I_1 , I_2 , ....I_n \}$ ，事件發生時刻 $t_i$ ，我們如何用線性聯立方程組描述所有$(n!)$ 不同排列事件的時間軸 !!
例如 : $\sigma = \{2,1,4,3,5......\} $ ，則 $t_2 < t_1 < t_4 < t_3 < t_5 ....$ `
我們另外定義 $cost_{ij}$ 代表如果事件 $i$ 接下來發生事件 $j$ 發生時間間隔
可以寫成$t_{(k+1)} = t_{(k)} + cost_{(k),(k+1)} \quad \forall k = 1,2,3,..(n-1)$ 其中括號 () 代表順序！
筆者是使用 TSP
(https://en.wikipedia.org/wiki/Travelling_salesman_problem) 類似想法的數學建模，整體模型如下 :
$$ \begin{array}{ll}
(T_1)& \displaystyle{\bigwedge_{(i,j)\in I^2_{\neq}} \quad \left( t_i + cost_{ij} \leq t_j + M(1-X_{ij}) \right)} \\
(T_2)& \displaystyle{ \bigwedge_{(i,j)\in I^2_{\neq}} \quad \left( t_j \leq t_i + cost_{ij} + M(1-X_{ij}) \right) } \\
(T_3)& \displaystyle{ \bigwedge_{i \in I} \quad \sum_{j\in I_{\neq}}X_{ji} = 1-FIR_{i}} \\
(T_4)& \displaystyle{\bigwedge_{i \in I} \quad \sum_{j\in I_{\neq} }X_{ij} = 1-LAS_{i} } \\
(T_5)& \displaystyle{ \bigwedge_{i \in I} \quad \left(\sum_{j\in I_{\neq} }X_{ij} - \sum_{j\in I_{\neq}}X_{ji}= FIR_{i}-LAS_{i} \right)} \\
(T_6) & \displaystyle{ \bigwedge_{i \in I} \left( FIR_{i}+LAS_{i}\leq 1 \right) } \\
(T_7) & \text{Subtour Elimination } of X\\
\end{array} $$
其中 $M$是夠大的數
$(T_1)$ 代表 如果有選擇 $(i,j)$ ，則 $X_{ij} = 1$ ，我們會有不等式，$t_i + cost_{ij} \leq t_j$ 如果沒有選擇 $(i,j)$ ，則 $X_{ij} = 0$ , 我們關掉(註解掉)限制式 !! $(t_i + cost_{ij} \leq t_j + M)$ 恆對
$(T_2)$ 結合 $(T_1)$讓$X_{ij} = 1$ 時， 等式成立，即 $t_i + cost_{ij} = t_j$
$FIR_i = 1$ 代表事件$i$ 為第一個事件
$LAS_i = 1$ 代表事件$i$ 為最後一個事件
$(T_3)$ 當事件$i$不是第一個事件時，恰好有 1個事件在它前面 （流入量 =1）
$(T_4)$ 當事件$i$不是最後一個事件時，恰好有 1個事件在它後面（流出量 =1）
$(T_5)$ 為知名的 Flow Balance Constraint !!
當事件$i$不是第一個事件或最後一個事件時，淨流量為 0 (流出-流入)
當事件$i$是第一個事件，淨流量為 $1$ (流出-流入)
當事件$i$是最後一個事件，淨流量為$ -1$ (流出-流入)
$(T_6)$ 為排名至多只會有一種
$(T_7)$ 為消去子迴路限制式，由於這部份原理有些複雜，
有興趣的讀者可以查詢 Miller-Tucker-Zemlin (MTZ) constraint or Dantzig-Fulkerson-Johnson(DFJ) Constraint 相關概念
[小結]
本文介紹一些整數規劃常見的數學建模概念與例子，希望能幫助讀者理解日常生活中的邏輯與"線性限制式"之間的關係！！
而建模技巧是把日常生活中的邏輯給正確的連結到方程式上!!
以下我們都把 $X \in \{0,1\}$ 視為 boolean 決策變數
=======================================
刻劃出點 Node $i , j$ 跟邊 Arc $(i,j)$ 關係
=======================================
定義:
$X_{i} = 1 \text{ iff } $ 我選擇了點 $i$
$X_{ij} = 1 \text{ iff } $ 我選擇了邊 $(i,j)$
$$(E1) \quad \text{if $(i,j)$ is selected then ($i$ and $j$) are selected} $$ $$ \left\{\begin{array}{c} X_{(i,j)}\leq X_i \\ X_{(i,j)}\leq X_j \\ \end{array}\right.$$ $$(E2) \quad \text{if ($i$ and $j$) are selected then $(i,j)$ is selected } $$ $$ X_{i}+X_{j} \leq 1+X_{(i,j)} $$
$(E1)$ 是現實生活中自然的邏輯:
意涵代表，我選擇了這條邊 $(i,j)$ 則我自然會 cover $i , j$ 這兩個點
$(E2)$ 則不一定會有的邏輯，需思考 $(i,j)$ 的定義
例如: 我定義 $(i,j)$ 為直接從 $i$ 走到 $j$
則走路徑 $(i \rightarrow j \rightarrow k \rightarrow w)$
則 $X_{i}=1 , X_{w} =1 $ 但是 $X_{(i,w)} = 0$ ，就不滿足 $(E2)$ 的邏輯
註: 結合 $(E1)$ and $(E2)$ 兩個邏輯事實上就是"線性化"，以下的非線性邏輯
$$ X_{(i,j)} = X_{i}X_{j} $$ ，而根據遞迴我們就有辦法線性化連乘的 boolean $$X_{S} = \prod_{s\in S}X_{s}$$
[精簡] 為了讓符號跟精簡，我們可以令 $a = (i,j)$ ，把 $(E1)$ , $(E2)$ 寫成
$$ X_{a} \leq X_i \quad X_{a}\leq X_{j} \quad X_{i}+X_{j} \leq 1+X_{a}$$
[思考] 關於 $(i,j)$ 定義需要小心提防，以下列舉
(1) $(i,j)$ 是否有方向性 ?? ，有方向性則要 $X_{(i,j)}$ ，$X_{(j,i)}$ 是不同的意義，無方向性我們正式的定義 $X_{[i,j]}$ ，其中 $[i,j]$ 為 equivalence class 裡的表現元。
(2) $(i,j)$ 是代表直接拜訪的邊?? 還是 OD-pair (起點-終點)??
如果是 $OD-pair$ 則我們必須使用探訪演算法，如 BFS , DFS , Union-Find 來確立 $(i,j)$ 是否存在，來定義 $X_{ij}$
=======================================
同理拓展至路徑 Path 與邊 Arc 的關係
=======================================
令 $p$ 為長度 $n$ 的路徑，可表示為 $(i_1 \rightarrow i_2 \rightarrow i_3 , .... \rightarrow i_n) $
定義 $X_p = 1 \text{ iff }$ 我選擇了路徑 $p$
$$ (P1) \text{如果選擇了路徑 $p$ 則 } \overbrace{(i_1,i_2)}^{a_1},\overbrace{(i_2,i_3)}^{a_2},...\overbrace{(i_{n-1},i_{n})}^{a_{n-1}}
\text{ 就被選擇了} $$
$$\left\{\begin{array}{l} X_{p} \leq X_{a_1} \\ X_{p} \leq X_{a_2} \\ X_{p} \leq X_{a_3}\\ ... \\ X_{p} \leq X_{a_{n-1}} \\ \end{array}\right.$$
$$ (P2) \text{如果選擇了 }\overbrace{(i_1,i_2)}^{a_1},\overbrace{(i_2,i_3)}^{a_2},...\overbrace{(i_{n-1},i_{n})}^{a_{n-1}} \text{則路徑 $p$ 就被選擇了} $$
$$ \sum_{k=1}^{n-1}X_{a_{k}} \leq (n-2) + X_{p} $$
[例子: 火車]
在交通運輸中，如果"火車" 會有"路徑"$p$ ，邊$a$相當於站與站之間的鐵軌，站相當於 $i,j$。
我們可以令火車為 $k \in TRA$ 分別定義 $X^{k}_{p}$ , $X^{k}_{a}$ , $X^{k}_{i}$
如果每一台火車有考慮的已知路徑集 $p \in P_k$，結合了$(E1)$ , $(E2)$ , $(P1)$ , $(P2)$ ，感謝遞移性，於是我們能夠描述出那些火車選擇了那些路徑後 $X^{k}_{p}$ 後，路徑-鐵軌-站的複雜 "0-1邏輯"關係 (那些火車有經過哪些邊，有經過哪些點 ... )
[抽象推廣]
由以上我們會發現，現實生活中，有小結構 $s$ 與大結構 $S$
則當我選擇大結構 $X_{S}$ 我就會 cover 小結構的所有元素$s$，更嚴謹來說是所有子集合 $S' \subset S$ 都會被 cover
可以寫成 $ X_{S} \leq X_{S'} $ ，就如同 $(E1)$ , $(P1)$ 一樣
反之如果某些情境下，小結構 $s$ 一部分都選了則代表大結構 $S$選了
則式子會是
$$ \sum_{s \in S}X_{s} \leq (|S|-1) + X_{S} $$
===========================================
重複經過，虛擬點的邏輯
============================================
在現實生活中，我們可能會重複經過一些點，例如:
$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$
此時我們的 $X_1 , X_{12}$ 就不夠用了。有兩種建模方式可解決:
(1) 增加維度，定義重複指標 $r$ : $X^{r}_{i}$, $X^{r}_{ij}$
例如 : $X^{2}_{12} = 1$ 代表第二次經過 $(1,2)$ 這條邊
而我們可以一個簡單的邏輯來描述重複的概念
$$ \text{第 }(r+1) \text{ 次選擇存在 } \Longrightarrow \text{第 }r \text{ 次選擇存在} $$
$$ (R1) \bigwedge_{r=1,2,...} \bigwedge_{i\in V} X^{r+1}_{i} \leq X^{r}_{i} $$
以上的例子就會變為:
$$\left\{\begin{array}{c} X^{2}_{1} \leq X^{1}_{1}\\
X^{2}_{2} \leq X^{1}_{2} \\
X^{2}_{12} \leq X^{1}_{12} \\ \end{array}\right.$$
(2) 拓展點集 $V^{*} = V \times V' \times V'' \times ... $，定義虛擬點 $i' , i'' , i''' ,.....i''''''$
其中 $[i] = \{i' , i'' , i''' ,.....i'''''' \}$ , $V^{*} = \text{disjoint union of those } [i]$
則可利用下面不等式描述概念
$$ \bigwedge_{[i]} \left( X_{i''''''} \leq... \leq X_{i'} \leq X_{i} \right) $$
實作上可以把點編號 $i = 1,2,3....|V|$ ，虛擬點 $i'$的編號滿足 $(i' - i) mod |V| = 0$
以上的例子: 就變成 $1 \rightarrow 2 \rightarrow 1' \rightarrow 2'$ ，假設 $V=\{1,2\}$
則路徑就變成 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ ，其中 $(3-1) mod 2 = 0$ ,代表 $1,3$ 是同一個點 !!
於是限制式就變成 $$\left\{\begin{array}{c} X_{3} \leq X_{1}\\ X_{4} \leq X_{2} \\ X_{34}\leq X_{12} \\ \end{array}\right.$$
[預處理下標]
關於虛擬點 $i'$，半虛擬邊$(i',j)$，虛擬邊$(i',j')$產生下標的方式，需使用DFS窮舉路徑演算法，並修改探訪停止條件，以及固定路徑的 $|p|$上界，方可產生！！
再來講解重要的"選擇集" 的數學建模 !!
================================================
if something happened , we have some different choices to do
================================================
某些情境集 $e\in E$ ，我們假設情境為互斥且恰有一個一定會發生，
$$\displaystyle{\sum_{e\in E}X_e =1 }$$
我們考慮當某件事 $e$ 發生以後 $X_e =1$ ，我們有一些選擇 $c$ 在選擇集合裡 $C_e$。
量化選擇 $y_{c} \in \mathbb{\mathbb{Z}} \text{ or } \mathbb{R}$ , 而當你量化選擇 $y_{c}$後，會有一些"已知"的權重$\omega_{c}$ 。而如果我想要表達這個加權後值是多少的時候:
即條件加權決策變數 $<\omega,y>|E$ (原創定義)
$$\left\{\begin{array}{ll} (C1) & \displaystyle{<\omega,y>|E = \sum_{e\in E}\sum_{c\in C_e}\omega_{c}y_{c}} \\ \text{s.t} & \\ (C2) & \forall (e,c) \in E \times C_e \quad y_{c} \in [0, M_{c}X_{e}]\\ (C3) &\displaystyle{\sum_{e\in E}X_e =1 } \\ \end{array}\right.$$
其中
$(C2)$ 也可以寫成 $ 0 \leq y_{c} \leq M_{c}X_{e} $
代表說如果 $e$ 沒有發生，我就讓 $y_{c} = 0 $ ，如果 $e$ 有發生，我就讓 $y_{c}$ 介於 $[0,M_{c}]$ 之間 ($M_{c}$ 為給定上界)
$(C1)$ 代表權重的值，為所有情境可能的加總
以下舉個實際例子:
----------------------------------------------------------------------
假如超商有商品集: $c \in C =\{雨傘 um，雨衣 rc ，防曬乳ss，墨鏡 sg \} $
價格分別為
$\omega_{um} = 100 $，$ \omega_{rc} = 50 $，$ \omega_{ss} = 80 $，$\omega_{sg} = 120 $
情境 $e \in E = \{下雨 rain，太陽 sun \}$
於是我們可以刻劃出以下的邏輯限制式
如果"明天" rain，則消費者可能會購買 um , rc 即 $C_{rain} = \{ um,rc \}$
如果"明天" sun，則消費者可能會購買 ss , sg 即 $C_{sun} = \{ ss,sg \}$
假設每位消費者至多只能同種商品 10 款 !! 即 $ \forall c \in C , M_{c} = 10 $
令 $y$ 為每位消費者購買的數量
則每位消費者購買的金額可以寫成
$$ \text{購買金額 : } 100 y_{um} + 50 y_{rc} + 80 y_{ss} + 120 y_{sg}$$
而且必須滿足以下方程組 ([C])
$X_{rain} + X_{sun} = 1 $
$ 0 \leq y_{um} \leq 10 \cdot X_{rain} $
$ 0 \leq y_{rc} \leq 10 \cdot X_{rain} $
$ 0 \leq y_{ss} \leq 10 \cdot X_{sun} $
$ 0 \leq y_{sg} \leq 10 \cdot X_{sun} $
其中決策變數為 6維 : 4 個整數$y$(商品購買數) + 2個 0-1邏輯 $X$
如果我們有很多消費者 $i \in I$
則
$$ \text{總體營業額: } \sum_{i\in I} \left(100 y^{i}_{um} + 50 y^{i}_{rc} + 80 y^{i}_{ss} + 120 y^{i}_{sg} \right)$$
而且要滿足 $ \bigwedge_{i \in I} [C]_i $
----------------------------------------------------------------------
註: 現實來說，每位消費者的決策變數 $y^{i}$ 是由"各自"決定，所以總體營業額應該是個賽局理論的量 !!
註: 選擇集的數學建模告訴我們，現實生活中的"量"，可以寫成眾多決策組合的疊加，而且是線性聯立不等式 !!
註: 現實生活 $E$ 可以是多層， 邏輯先後 path ，甚至是 hypergraph
=========================================================
連續時間與排列限制式
=========================================================
給定$n$ 個事件 $i \in I = \{ I_1 , I_2 , ....I_n \}$ ，事件發生時刻 $t_i$ ，我們如何用線性聯立方程組描述所有$(n!)$ 不同排列事件的時間軸 !!
例如 : $\sigma = \{2,1,4,3,5......\} $ ，則 $t_2 < t_1 < t_4 < t_3 < t_5 ....$ `
我們另外定義 $cost_{ij}$ 代表如果事件 $i$ 接下來發生事件 $j$ 發生時間間隔
可以寫成$t_{(k+1)} = t_{(k)} + cost_{(k),(k+1)} \quad \forall k = 1,2,3,..(n-1)$ 其中括號 () 代表順序！
筆者是使用 TSP
(https://en.wikipedia.org/wiki/Travelling_salesman_problem) 類似想法的數學建模，整體模型如下 :
$$ \begin{array}{ll}
(T_1)& \displaystyle{\bigwedge_{(i,j)\in I^2_{\neq}} \quad \left( t_i + cost_{ij} \leq t_j + M(1-X_{ij}) \right)} \\
(T_2)& \displaystyle{ \bigwedge_{(i,j)\in I^2_{\neq}} \quad \left( t_j \leq t_i + cost_{ij} + M(1-X_{ij}) \right) } \\
(T_3)& \displaystyle{ \bigwedge_{i \in I} \quad \sum_{j\in I_{\neq}}X_{ji} = 1-FIR_{i}} \\
(T_4)& \displaystyle{\bigwedge_{i \in I} \quad \sum_{j\in I_{\neq} }X_{ij} = 1-LAS_{i} } \\
(T_5)& \displaystyle{ \bigwedge_{i \in I} \quad \left(\sum_{j\in I_{\neq} }X_{ij} - \sum_{j\in I_{\neq}}X_{ji}= FIR_{i}-LAS_{i} \right)} \\
(T_6) & \displaystyle{ \bigwedge_{i \in I} \left( FIR_{i}+LAS_{i}\leq 1 \right) } \\
(T_7) & \text{Subtour Elimination } of X\\
\end{array} $$
其中 $M$是夠大的數
$(T_1)$ 代表 如果有選擇 $(i,j)$ ，則 $X_{ij} = 1$ ，我們會有不等式，$t_i + cost_{ij} \leq t_j$ 如果沒有選擇 $(i,j)$ ，則 $X_{ij} = 0$ , 我們關掉(註解掉)限制式 !! $(t_i + cost_{ij} \leq t_j + M)$ 恆對
$(T_2)$ 結合 $(T_1)$讓$X_{ij} = 1$ 時， 等式成立，即 $t_i + cost_{ij} = t_j$
$FIR_i = 1$ 代表事件$i$ 為第一個事件
$LAS_i = 1$ 代表事件$i$ 為最後一個事件
$(T_3)$ 當事件$i$不是第一個事件時，恰好有 1個事件在它前面 （流入量 =1）
$(T_4)$ 當事件$i$不是最後一個事件時，恰好有 1個事件在它後面（流出量 =1）
$(T_5)$ 為知名的 Flow Balance Constraint !!
當事件$i$不是第一個事件或最後一個事件時，淨流量為 0 (流出-流入)
當事件$i$是第一個事件，淨流量為 $1$ (流出-流入)
當事件$i$是最後一個事件，淨流量為$ -1$ (流出-流入)
$(T_6)$ 為排名至多只會有一種
$(T_7)$ 為消去子迴路限制式，由於這部份原理有些複雜，
有興趣的讀者可以查詢 Miller-Tucker-Zemlin (MTZ) constraint or Dantzig-Fulkerson-Johnson(DFJ) Constraint 相關概念
[小結]
本文介紹一些整數規劃常見的數學建模概念與例子，希望能幫助讀者理解日常生活中的邏輯與"線性限制式"之間的關係！！
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2018.01
留言
張貼留言