作者yr (Light be with you)
看板Prob_Solve
标题Re: [问题] 徵求神人帮解大地游戏分组的超难排列组合
时间Fri Jun 19 22:40:10 2015
刚试了一下，似乎是无解。（注：改了最後一个条件解出来了）
X[i][j][k][t] (BINARY): 0<=i,j<18 - team,
0<=k<10 - game,
0<=t<10 - time period
Maximize 0
s.t.
sum(X[i][i][k][t]) == 0, for all i 不配到自己
sum(X[i][j][k][t]) == 10, for all i 玩十场
sum(X[i][j][k][t]) == 1, for all (i,t) 每队每时段一场
sum(X[i][j][k][t]) == 1, for all (i,k) 每游戏每队只玩一次
sum(X[i][j][k][t]) <= 1, for all (i,j) 两队只对到一次
sum(X[i][j][k][t]) <= 1, for all (k,t) 每游戏在每个时段被玩最多一次
CPLEX 两秒告诉我无解，不知道这些条件有没有搞错。
--
Some people are born on third base and go through life
thinking they hit a triple.
- Barry Switzer
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.60.214.239
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1434724814.A.CE7.html
※ 编辑: yr (42.60.214.239), 06/19/2015 22:51:13
※ 编辑: yr (42.60.214.239), 06/19/2015 23:41:11
1F：→ scwg: 不准轮空一定无解吧? 18队凑成 9 对, 十个游戏一定要有轮空 06/20 06:21
※ 编辑: yr (155.69.185.196), 06/20/2015 10:54:32
2F：→ yr: 最後一个改 <= 就可以了 :p 06/20 10:54
3F：→ yr: 改了以後好像就有解了，风扇狂转中.... 06/20 10:56
大概五分钟解出来，如下。
t0: 0(0,1) 1(7,14) 2(15,17) 3(11,12) 4() 5(2,5) 6(4,6) 7(3,10) 8(8,13) 9(9,16)
t1: 0() 1(0,2) 2(8,9) 3(1,3) 4(13,14) 5(4,15) 6(16,17) 7(6,7) 8(10,12) 9(5,11)
t2: 0(14,16) 1(5,17) 2(0,3) 3(2,9) 4(1,10) 5(7,13) 6(8,12) 7() 8(4,11) 9(6,15)
t3: 0(7,17) 1(3,16) 2(2,12) 3(0,4) 4(6,9) 5(8,10) 6(5,13) 7(11,15) 8() 9(1,14)
t4: 0(6,11) 1() 2(1,13) 3(7,15) 4(0,5) 5(12,14) 6(9,10) 7(4,16) 8(3,17) 9(2,8)
t5: 0(3,9) 1(12,15) 2(11,16) 3(10,13) 4(8,17) 5(0,6) 6() 7(1,2) 8(5,14) 9(4,7)
t6: 0(4,12) 1(10,11) 2() 3(8,14) 4() 5(1,16) 6(0,7) 7(5,9) 8(2,6) 9(13,17)
t7: 0(2,10) 1(9,13) 2(4,5) 3(6,17) 4() 5(3,11) 6(14,15) 7(0,8) 8(1,7) 9()
t8: 0() 1(6,8) 2(7,10) 3(5,16) 4(2,4) 5() 6(1,11) 7(14,17) 8(0,9) 9(3,12)
t9: 0(5,8) 1(1,4) 2(6,14) 3() 4(7,11) 5(9,17) 6(2,3) 7(12,13) 8(15,16) 9(0,10)
※ 编辑: yr (155.69.185.196), 06/20/2015 11:07:48
※ 编辑: yr (155.69.185.196), 06/20/2015 11:48:41
4F：→ yr: 答案怪怪的，我再研究一下，照理每个时段最多空一个 06/20 11:52
改了一下，加一组 constraint 。
Maximize 0
s.t.
sum(X[i][i][k][t]) == 0, for all i 不配到自己
X[i][j][k][t] - X[j][i][k][t] == 0, for all i<j
sum(X[i][j][k][t]) == 10, for all i 玩十场
sum(X[i][j][k][t]) == 1, for all (i,t) 每队每时段一场
sum(X[i][j][k][t]) == 1, for all (i,k) 每游戏每队只玩一次
sum(X[i][j][k][t]) <= 1, for all (i,j) 两队最多只对到一次
sum(X[i][j][k][t]) <= 1, for all (k,t) i<j 每游戏在每个时段被玩最多一次
sum(X[i][j][k][t]) == 180 总共 180 场次（每个 match 算 2 场次）
横向是游戏，纵向是时间
0 1 2 3 4 5 6 7 8 9
0,1 3,11 13,14 7,9 2,10 6,17 4,5 15,16 8,12
10,15 0,2 9,16 5,11 8,13 6,14 1,3 7,17 4,12
2,11 14,15 0,3 6,12 5,9 7,8 4,10 13,16 1,17
5,12 4,8 10,17 1,6 3,16 0,13 7,11 2,15 9,14
4,14 1,5 12,15 2,16 3,17 0,10 9,11 6,8 7,13
6,16 9,13 1,10 8,14 4,7 11,12 2,17 0,5 3,15
13,17 6,7 3,4 0,16 5,14 1,15 9,12 10,11 2,8
8,9 7,12 2,5 1,13 11,14 4,15 0,17 3,6 10,16
3,7 6,10 4,17 8,15 2,9 12,16 5,13 1,14 0,11
16,17 8,11 0,15 12,13 1,7 3,10 2,14 4,9 5,6
※ 编辑: yr (155.69.185.196), 06/20/2015 13:02:52
5F：推 longlongint: 果然专家比较猛 06/20 13:47
6F：→ longlongint: 忘了有LP可以用 06/20 14:06
7F：→ longlongint: 说错 IP 06/20 14:07
8F：推 eieio: 请问一下，12 队 7 关 7 场，有解吗？ 07/22 07:40