Why Integer Programming Is Important In Real Life

混整數規劃(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 等等日後會再寫一篇 !!

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

by Plus & Minus 2017.09