作者tokyo291 (工口工口)
看板Math
標題[其他] 整數規劃問題
時間Wed Sep 30 17:29:03 2020
index A B C
1 9.6 0.2 7.7
2 7.4 0.3 5.0
3 7.8 0.25 8.5
4 6.1 0.11 8.2
資料如上，依照有4組樣本，分別有A、B、C三種數值
若依照index 1 2 3 4的順序可以分別畫出A、B、C三種數值各自的折線圖
現在希望任意排序index順序，找出一個最佳組合
可以讓A、B、C三條折線圖的線趨於水平線
目前我的想法是用整數規劃的方式求解
先整理出A、B、C中每兩點的斜率
A、
終點
1 2 3 4
1 X -2.2 -1.8 -3.5
始 2 2.2 X 0.4 -1.3
點 3 1.8 -0.4 X -1.7
4 3.5 1.3 1.7 X
B、
終點
1 2 3 4
1 X 0.1 0.05 -0.09
始 2 -0.1 X -0.05 -0.19
點 3 -0.05 0.05 X -0.14
4 0.09 1.9 0.14 X
C、
終點
1 2 3 4
1 X -2.7 0.8 0.5
始 2 2.7 X 3.5 3.2
點 3 -0.8 -3.5 X -0.3
4 -0.5 -3.2 0.3 X
X表示無斜率(自己跟自己的情況)
可以整理為整數規劃的形式
(將斜率平方，避免正負相加影響結果)
minimize：
A_21 * XA_21 + A_31 * XA_31 + A_41 * XA_41 +
A_12 * XA_12 + A_32 * XA_32 + A_42 * XA_42 +
A_13 * XA_13 + A_23 * XA_23 + A_43 * XA_43 +
A_14 * XA_14 + A_24 * XA_24 + A_34 * XA_34 +
B_21 * XB_21 + B_31 * XB_31 + B_41 * XB_41 +
B_12 * XB_12 + B_32 * XB_32 + B_42 * XB_42 +
B_13 * XB_13 + B_23 * XB_23 + B_43 * XB_43 +
B_14 * XB_14 + B_24 * XB_24 + B_34 * XB_34 +
C_21 * XC_21 + C_31 * XC_31 + C_41 * XC_41 +
C_12 * XC_12 + C_32 * XC_32 + C_42 * XC_42 +
C_13 * XC_13 + C_23 * XC_23 + C_43 * XC_43 +
C_14 * XC_14 + C_24 * XC_24 + C_34 * XC_34
A_21表示上表A始點為2終點為1的斜率，B_13、C_23...等等同樣表示斜率
XA_21為1或0，表示有無選取此項
然後再寫限制式的時候就卡住了...
請問這種有排序關係的限制是該如何表達呢?
還是這種問題其實不該用整數規劃去處理...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.214.67 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1601458145.A.36E.html
1F：→ hwanger : 按照原po的敍述 ABC的index似乎不是各排各的 所以 09/30 23:29
2F：→ hwanger : 想要minimize的式子 應該是 09/30 23:29
3F：→ hwanger : sum of (A_ij+B_ij+C_ij)X_ij over all i != j 09/30 23:29
4F：→ hwanger : 而此時domain應該是 09/30 23:29
5F：→ hwanger : { X: i,j,k,h are distinct and X_ij=X_jk=X_kh=1, 09/30 23:29
6F：→ hwanger : X_st=0 for all (s,t)!=(i,j),(j,k),(k,l) } 09/30 23:29
7F：→ hwanger : domain的形狀太奇怪 可能不應該用線性規劃 而是用 09/30 23:38
8F：→ hwanger : 離散的技巧 不過我目前也沒想到比較漂亮的手法 09/30 23:38
9F：→ hwanger : 至少這一題只有4!=24個點 當考慮n! n夠小時 跑程式 09/30 23:38
10F：→ hwanger : 暴力破解是ok的 09/30 23:38
11F：→ hwanger : 想了一下 其實這是Travelling salesman problem的變 10/01 14:43
12F：→ hwanger : 形 考慮5座城市 C0,C1,C2,C3,C4 其中C0和其他四座的 10/01 14:46
13F：→ hwanger : 距離的0 而Ci和Cj的距離是(A_ij+B_ij+C_ij) (這裡要 10/01 14:47
14F：→ hwanger : 注意的是因為取平方的關係 A_ij=A_ji B_ij=B_ji 10/01 14:49
15F：→ hwanger : C_ij=C_ji 所以上述定義是well-defined的) 現在希望 10/01 14:51
16F：→ hwanger : 從C0出發 每個城市都走過一遍並回到C0 問最短的走法 10/01 14:52
17F：→ hwanger : 因為TSP是NP-complete problem 所以這題有極大的可 10/01 14:55
18F：→ hwanger : 能是不行用整數規劃去處理的 10/01 14:55
19F：→ hwanger : 或許可以參考TSP最新的研究進度 10/01 14:58
20F：→ hwanger : 原po是從shortest Hamiltonian path in a weighted 10/02 21:27
21F：→ hwanger : complete graph推到這個問題的嗎? 10/02 21:28
感謝您的回復，我在想看看離散數學的方式能不能找最佳解
這個是目前實務碰到的問題的簡化版
因為感覺跟之前看過作業研究的題目很像
但是又有點不同，才想確認看是否用錯方法哈
感覺這個問題跟TSP問題較相似，但是距離是多維而非原本的1維
※ 編輯: tokyo291 (125.227.214.67 臺灣), 10/05/2020 09:38:03
22F：→ hwanger : ??? 我不太懂你多維的意思 所以A,B,C的index是各自 10/05 10:17
23F：→ hwanger : 跑的嗎 那只要各自monotone就好了 根本就不需要TSP 10/05 10:18
24F：→ hwanger : 就是因為不是各自跑 所以才變成TSP 冏 10/05 10:19
不是各自跑沒錯
那個多維的部分是想形容原本TSP的問題中不同城市間的距離(1維)變成多維
有點難形容@@
原本的TSP問題，只要考慮不同城市間的距離
但是我碰到的狀況除了考慮城市間的距離
還需要考慮城市間的人口數差、出生率差異、性別比、待職人數差異...等等
考慮這些東西來決定最佳路徑
※ 編輯: tokyo291 (125.227.214.67 臺灣), 10/05/2020 13:32:00
25F：→ hwanger : 是不是指city i和city j的weight wij實際上是有一 10/05 15:23
26F：→ hwanger : 堆的參數的函數 例如原例中 wij是Aij Bij Cij的函 10/05 15:23
27F：→ hwanger : 數 10/05 15:23
28F：→ hwanger : 應該是我摸不太清楚你多維的意思 囧 我不太能想像 10/05 15:23
29F：→ hwanger : 多維的TSP XD 10/05 15:23
我用原本題目的說法嘗試說一次看看能不能表達我的意思哈
現在有10個樣本編號1~10(也就是10個城市)
每個樣本分別有ABCDE五種數值
ex:1號樣本的A=5、B=6、C=7、D=8、E=9
現在希望可以找出一個順序去牌這10個樣本
讓相鄰的樣本ABCDE的數值可以相差最少
如果只有A一個的話(每個城市的距離)，就可以看成是一般的TSP
然後我的想法是因為多了BCDE，就想成多維的城市距離的情況
以上是我的理解
如果有錯誤的觀念還希望能更正><
※ 編輯: tokyo291 (118.170.119.144 臺灣), 10/05/2020 22:55:05
30F：→ hwanger : XD 如果只有A一個的話 雖然有違直覺 為了使排序完後 10/06 00:05
31F：→ hwanger : 的 |A1-A2| + |A2-A3| +...+ |A9-A10|最小 或 10/06 00:07
32F：→ hwanger : (A1-A2)^2 + (A2-A3)^2 +...+ (A9-A10)^2 最小 其實 10/06 00:08
33F：→ hwanger : 排的依據就是將data increasing或decreasing的排 10/06 00:10
34F：→ hwanger : 其實不用特別考慮TSP 冏 10/06 00:12
35F：→ hwanger : 如果有ABCDE 5種數值的話 此時i號樣本和j號樣本的距 10/06 00:16
36F：→ hwanger : 離 dij就可能可以定義成(Ai-Aj)^2 + (Bi-Bj)^2 + 10/06 00:18
37F：→ hwanger : (Ci-Cj)^2+(Di-Dj)^2+(Ei-Ej)^2 此時才需要TSP 冏 10/06 00:22
抱歉我忘了強調一個需求前題
就是排序的目的是為了讓10個樣本排序後的散布能接近水平線
(排序後樣本點的折線圖接近水平)
所以必須避免排序後出現increasing或decreasing的結果
例如:目前有5個樣本，A的數值分別為5、6、7、8、9
排序成5、6、7、8、9或是9、8、7、6、5
相鄰的差會最小，但是散布的情況不是水平線
排成6、8、5、9、7(這邊先忽略相鄰最小的需求)會接近水平線
※ 編輯: tokyo291 (125.227.214.67 臺灣), 10/06/2020 08:31:05
38F：→ hwanger : 所以是不是應該要再加一個額外條件 假設排完後 各自 10/06 09:24
39F：→ hwanger : 線性迴歸的斜率為mA, mB, mC, mD, mE 然後希望前面 10/06 09:26
40F：→ hwanger : 算出來的距離和D 及 mA^2+mB^2+mC^2+mD^2+mE^2能同 10/06 09:27
41F：→ hwanger : 時越小越好 (還是其實只要求後者越小越好?) 不管怎 10/06 09:30
42F：→ hwanger : 樣 其實已經不是TSP了 可能要重新定義問題然後從頭 10/06 09:32
43F：→ hwanger : 分析方法了 冏 10/06 09:32
44F：→ tokyo291 : 對，討論到後來發現已經不是TSP...碰到的這個問題太 10/06 16:13
45F：→ tokyo291 : 複雜哈哈 10/06 16:14
46F：→ hwanger : 雖然問題變複雜了 不過可以用的方法可能變多了 例如 10/06 23:22
47F：→ hwanger : 只考慮mA^2+mB^2+mC^2+mD^2+mE^2的最小值的話 那分 10/06 23:22
48F：→ hwanger : 析、線代、群表現論的技巧可能就可以用進來找解(或 10/06 23:24
49F：→ hwanger : 找"夠好的"解) 10/06 23:24