作者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/cn.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