Some Integer Programming Model Technique With Network Structure

本篇介紹一些筆者認為重要的整數規劃-圖形，邏輯建模技巧與概念，關於整數規劃的用途，可先參考之前這篇: 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 相關概念


[小結]
本文介紹一些整數規劃常見的數學建模概念與例子，希望能幫助讀者理解日常生活中的邏輯與"線性限制式"之間的關係！！

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2018.01