[其他] 整數規劃問題

看板Math作者 (工口工口)時間5年前 (2020/09/30 17:29), 編輯推噓0(0推 0噓 21→)
留言21則, 1人參與, 5年前最新討論串1/1
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://www.ptt.cc/bbs/Math/M.1601458145.A.36E.html
→
09/30 23:29, 5年前 , 1F
按照原po的敍述 ABC的index似乎不是各排各的 所以
09/30 23:29, 1F
→
09/30 23:29, 5年前 , 2F
想要minimize的式子 應該是
09/30 23:29, 2F
→
09/30 23:29, 5年前 , 3F
sum of (A_ij+B_ij+C_ij)X_ij over all i != j
09/30 23:29, 3F
→
09/30 23:29, 5年前 , 4F
而此時domain應該是
09/30 23:29, 4F
→
09/30 23:29, 5年前 , 5F
{ X: i,j,k,h are distinct and X_ij=X_jk=X_kh=1,
09/30 23:29, 5F
→
09/30 23:29, 5年前 , 6F
X_st=0 for all (s,t)!=(i,j),(j,k),(k,l) }
09/30 23:29, 6F
→
09/30 23:38, 5年前 , 7F
domain的形狀太奇怪 可能不應該用線性規劃 而是用
09/30 23:38, 7F
→
09/30 23:38, 5年前 , 8F
離散的技巧 不過我目前也沒想到比較漂亮的手法
09/30 23:38, 8F
→
09/30 23:38, 5年前 , 9F
至少這一題只有4!=24個點 當考慮n! n夠小時 跑程式
09/30 23:38, 9F
→
09/30 23:38, 5年前 , 10F
暴力破解是ok的
09/30 23:38, 10F
→
10/01 14:43, 5年前 , 11F
想了一下 其實這是Travelling salesman problem的變
10/01 14:43, 11F
→
10/01 14:46, 5年前 , 12F
形 考慮5座城市 C0,C1,C2,C3,C4 其中C0和其他四座的
10/01 14:46, 12F
→
10/01 14:47, 5年前 , 13F
距離的0 而Ci和Cj的距離是(A_ij+B_ij+C_ij) (這裡要
10/01 14:47, 13F
→
10/01 14:49, 5年前 , 14F
注意的是因為取平方的關係 A_ij=A_ji B_ij=B_ji
10/01 14:49, 14F
→
10/01 14:51, 5年前 , 15F
C_ij=C_ji 所以上述定義是well-defined的) 現在希望
10/01 14:51, 15F
→
10/01 14:52, 5年前 , 16F
從C0出發 每個城市都走過一遍並回到C0 問最短的走法
10/01 14:52, 16F
→
10/01 14:55, 5年前 , 17F
因為TSP是NP-complete problem 所以這題有極大的可
10/01 14:55, 17F
→
10/01 14:55, 5年前 , 18F
能是不行用整數規劃去處理的
10/01 14:55, 18F
→
10/01 14:58, 5年前 , 19F
或許可以參考TSP最新的研究進度
10/01 14:58, 19F
→
10/02 21:27, 5年前 , 20F
原po是從shortest Hamiltonian path in a weighted
10/02 21:27, 20F
→
10/02 21:28, 5年前 , 21F
complete graph推到這個問題的嗎?
10/02 21:28, 21F
‣ 更多 tokyo291 的文章
文章代碼(AID): #1VT4_XDk (Math)