ZEEV ZEITIN Delft University of Technology, Netherlands Integer Allocation Problems of Min-Max Type with Quasiconvex Separable Functions ZEEV ZEITIN Delft University of Technology, Netherlands Operations Research. Vol. 29, no. 1, pp. 207-211. 1981 Presented by Tzu-Cheng Hsieh, OPLab, IM, NTU 2007/1/23

Outline Introduction Optimality Conditions For MinxMaxj Problem Solution Algorithm Applications 2019/1/15 NTU, IM, OPLab

Outline Introduction Optimality Conditions For MinxMaxj Problem Solution Algorithm Applications 2019/1/15 NTU, IM, OPLab

Introduction The paper treats the problem of integer resource allocations using the min-max criterion. The objective function is assumed to be strictly quasiconvex（in the integer sense）and separable. The optimality conditions are used to obtain a solution algorithm which may be simplified in the case. 1.這篇Paper主要是利用minmax的方式去解決整數資源分配的問題。 2.而在這篇Paper所定義的目標函式是被假設為建構在整數上的strictly quasiconvex並且此目標函式是可以被分解的。 3.並且這篇Paper所提出的minmax的optimality conditions可以用來推導出一套algorithm來求出這個integer resource allocation問題的最佳解。 2019/1/15 NTU, IM, OPLab

Outline Introduction Optimality Conditions For MinxMaxj Problem Solution Algorithm Applications 2019/1/15 NTU, IM, OPLab

Optimality Conditions For MinxMaxj Problem Define Theorem Proof 1.針對Optimality conditions for minmax problem，先介紹二個名詞，再針對作者所提出的定理，加以證明。 2019/1/15 NTU, IM, OPLab

Definition A bottleneck integer problems Strictly Quasiconvex 1.所有X sub v的總合為M，先調整v找到max f sub v of x sub v，再調整這些X sub v來使這個max f sub v of x sub v 最小。也就是讓最大的f sub v of x sub v最小化。 2.對於所有整數x,a,b若滿足a<x<b使f(x)<max{f of a,f of b}則此function被稱作strictly quasiconvex。 3.另外，這篇Paper定義一個新的名詞，fi of x等於原先調整v所找到的max f sub v of x sub v。 2019/1/15 NTU, IM, OPLab

Theorem Theorem 1.作者所提出來的定理是：若x super star是bottleneck integer problem的一組最佳解，其中x sub r super star被定義為使f sub r of x sub r super star為max f sub v of x sub v super star，此時，以下這二條式子成立。 2. 這二條式子是說，將x sub r star其中一單位轉移至別的地方或將別的地方轉移一單位到x sub r super star，都會比最佳解情況下的f sub r of x sub r super star還來得大。 3.而這二個式子之後會用來導出solution algorithm。 4.這個定理也是反之亦然，若存在一組bottleneck integer problem的可行解x star且f sub j滿足strictly quasiconvex，則若滿足(4) 和(5) 的條件則x super star為bottleneck integer problem的解。 2019/1/15 NTU, IM, OPLab

Proof（1/4） Necessity 1.接下來作者提出了證明，首先先證明必要條件，這裡作者是利用反證法來證明。 2.假定x sub r super star>0且(4)是不成立的，也就是說下面這條式子成立。此時考慮一個新的解x super 1，結構如下。 3.也就是將x sub r super star扣掉一單位加到另一個x sub l上，成為另一個新的解。 4.此時，很明顯的，x super 1是可行的解，但fi of x super 1卻小於fi of x super star，違反了max f sub v of x sub v，也就是違反了問題的要求。 5.同樣的證明也可套用在(5)當x sub r super star小於M時。 2019/1/15 NTU, IM, OPLab

Proof（2/4） Sufficiency（1/3） 1.接下來證明充分條件，這裡作者也是利用反證法來證明。 2.假設x super zero形式如下，也就是maximum f sub v of x sub v super zero小於f sub r of x sub r super star。 3.此時將x super zero與x super star比較來分成三類，一類是x sub j super star大於x sub j super zero，並將這些j歸類為I1，一類是小於，並將這些i歸類為I2，一類是相等，並將這些v歸類為I3。 2019/1/15 NTU, IM, OPLab

Proof（3/4） Sufficiency（2/3） 1.因此可以分成三個Case來探討，首先是當r處在I1的集合中，也就是x sub r super star小於x sub r super zero，加上(6)式，可以得到f sub r of x sub r super star大於f sub r of x sub r super star add omega sub r。 2.當omega sub r等於1時，可以直接得到上面這條式子，而當omega sub r大於1時，由strictly quasiconvex可以得到下面這條式子。 3. 此時，當i屬於I2集合時，由(5)式可以推導出(7)式，由(6)式可以推導出(8)式。 4.從(7)與(8)可以很容易的推導出下面這條式子，此時，當h sub i大於1時，很清楚的違反了strictly quasiconvex，而當h sub i等於1時，也可以很清楚的看出(7)與(8)是矛盾的。 2019/1/15 NTU, IM, OPLab

Proof（4/4） Sufficiency（3/3） 1.當r處在I2的集合中時，此處的證明與(i)是相似的，也是會產生矛盾的結果。 2.當r處在I3的集合中時，可以得到f of sub r of x sub r super star等於f sub r of x suv r super zero，但由(6)式得知f sub r of x sub r super zero大於f sub r of x sub r super zero，顯而易見的也矛盾了。 2019/1/15 NTU, IM, OPLab

Outline Introduction Optimality Conditions For MinxMaxj Problem Solution Algorithm Applications 1.由以上的定理可以推導出一套algorithm來解答在strictly quasiconvex的bottleneck integer problem。 2019/1/15 NTU, IM, OPLab

Solution Algorithm Solution Algorithm 1.先選擇一組可行解x。 2.找出r 使f sub r of x sub r等於maxmum f sub i of x sub i。 3.若x sub r等於0則跳至step 5b，反之則跳至step 3。 4.檢查x是否成立(4)式，若成立，則跳至step 4a，反之，則f sub r of x sub r仍不是最minimum的，因為，此時將x sub i add 1指定給x sub i，將x sub r minus 1指定給 x sub r，並跳至step 2a。 5.若x sub r等於M，則求到最佳解，反之，則跳至step 4b。 6.檢查x是否成立(5)式，若成立，則求到最佳解，反之，則f sub r of x sub r仍不是最minimum的，因為，此時將x sub i minus 1指定給x sub i，將x sub r add 1指定給 x sub r，並跳至step 2a。 7.經由不斷重覆這些step，maximum f sub r of x sub r會越來越小，而求得最佳的解。 8.若f function是increasing的，則step 4a-4b則可省略，因為給的參數越大則值越大，因此須step 2b-3來縮小x sub r 的值使f sub r of x sub r更小。 9.相同的，若f function是decreasing的，則step 2b-3則可省略，因為給的參數越小則值越大，因此須step 4a-4b來增大x sub r 的值使f sub r of x sub r更小。 2019/1/15 NTU, IM, OPLab

Outline Introduction Optimality Conditions For MinxMaxj Problem Solution Algorithm Applications 2019/1/15 NTU, IM, OPLab

Application Attack and Defense Model Optimal Search 1. 作者提出了二種應用，一個是攻防模型，一個是最佳化搜尋。 2019/1/15 NTU, IM, OPLab

Attack and Defense Model（1/5） There are two players pursuing antagonistic interests, attack and defense. The attacker has available M units and the defender N units. The collision of attack and defense occurs at n targets. Let xi(yi) represent the size of the subforces attacking(defending) the i-th target. 1.情境是有二個players進行Attack和defense。 2.Attacker和Defenser各持有M個單位和N個單位的資源。 3.雙方的攻防目標(衝突點)為n個。 4.而x sub i和y sub i各代表attacker和defenser在第i個目標上的攻擊力和防禦力。 2019/1/15 NTU, IM, OPLab

Attack and Defense Model（2/5） The quantity of subforce Xi penetrating through the defense is , where qi is the efficiency of the use of the defensive means at the i-th target. 1.則attacker在第i個攻防目標上能穿透防禦機制的攻擊力大小為x sub i minus q sub i multiply y sub i，若為負值則為0，此處q sub i代表防禦機制在第i個攻防目標上的防禦效力。 2019/1/15 NTU, IM, OPLab

Attack and Defense Model（3/5） The total damage inflicted on the complex of n targets is , where di are the weighting coefficients, measuring the relative importance of vulnerability of the n targets. 1.因此，在n個攻防目標上所造成的總損失為將各別攻防目標的攻擊力加總起來，其中d sub i為用來衡量在每個攻防目標上面之弱點重要性的權重係數。 2019/1/15 NTU, IM, OPLab

Attack and Defense Model（4/5） Thus, there are two versions of the same problem： (i) From the attacker’s point of view: 1.此時，對於攻防問題在攻擊端和防禦端有不同的觀點。 2.從攻擊端來看，Attacker希望能最大化攻擊力。 3.而Defenser希望能將這個最大化的攻擊力最小化。 2019/1/15 NTU, IM, OPLab

Attack and Defense Model（5/5） (ii) From the defender’s point of view: 1.從防禦端來看，Attacker希望能最小化防禦力。 2.而Defenser希望能將這個最小化的防禦力最大化。 3.很清楚的，由於這二個式子是固定y，變動x，因此(9a)式和(9b)式可以被化減成這個式子。 4.此時就可以利用前面的solution algorithm來獲得最佳解了。 2019/1/15 NTU, IM, OPLab

Optimal Search（1/2） Let the search of some object be carried out at n areas. The efficiency of search at the j-th area is fj(xj), which spending the resource xj, if the object located at j-th area and 0 otherwise. The mathematical expectation of the search efficiency is evidently , where pj is the probability of the object whereabouts being in the j-th area. 1.另一個應用是Optimal Search。 2.情境是要在n個地區search some object。 3. x sub i是在第i個地區投入的資源，而f sub j of x sub j是當search目標在第j地區時的search效力。 4.因此，其search效力的期望值是這個式子，其中p sub j是search目標在第j地區的機率。 2019/1/15 NTU, IM, OPLab

Optimal Search（2/2） If are unknown, then an optimal strategy for a whereabouts search is determined by finding , where M is a positive integer, representing the budget restriction for the search. 1.若p sub j是未知的，則最理想的search strategy是找出這個式子的最佳解，就是希望能最大化最小的期望值，其中M代表此search的預算限制。 2019/1/15 NTU, IM, OPLab

Thanks for your listening! The End. Thanks for your listening! 2019/1/15 NTU, IM, OPLab