benchmark - mofhu/cc-trevize GitHub Wiki

Benchmark

Phase I

Algorithms:

  • best
  • ip-trevize-iter: (2.0.4)
  • ip-trevize: with path constraint. (2.0.5)
  • ip-trevize-cbc: with CBC solver instead of Gunobi. (2.0.5)

Benchmark:

algorithm, case, time, result, detail
best, case0, 0.0030829906463623047, AC, 4
best, case1, 0.00448298454284668, AC, 71
best, case11, 9.059201002120972, AC, 555
best, case2, 0.049668073654174805, AC, 99
best, case3, 9.154275894165039, AC, 452
best, case4, 9.090671062469482, AC, 505
ip-trevize-iter, case0, 0.3284640312194824
ip-trevize-iter, case1, 0.3241910934448242
ip-trevize-iter, case11, 2.0731568336486816
ip-trevize-iter, case2, 0.599984884262085
ip-trevize-iter, case3, 0.4322829246520996
ip-trevize-iter, case4, 0.5978751182556152
ip-trevize, case0, 0.3294668197631836, AC, 4
ip-trevize, case1, 0.35698795318603516, AC, 71
ip-trevize, case11, 2.3008739948272705, AC, 444
ip-trevize, case2, 0.40952205657958984, AC, 99
ip-trevize, case3, 0.6932201385498047, AC, 375
ip-trevize, case4, 1.2009010314941406, AC, 447
ip-trevize-cbc, case0, 0.35024380683898926, AC, 4
ip-trevize-cbc, case1, 0.3519268035888672, AC, 71
ip-trevize-cbc, case11, 6.795530080795288, AC, 444
ip-trevize-cbc, case2, 0.8404319286346436, AC, 99
ip-trevize-cbc, case3, 0.8465139865875244, AC, 375
ip-trevize-cbc, case4, 1.6560168266296387, AC, 447

Notes:

  • 权重: IP 算法明显优于搜索
  • IP 求解器差别明显: Gurobi 显著快
  • iter vs cycle free: 有些出乎意料的是时间差不多; 说明增加的变量和约束数量弥补了迭代次数. 但也要考虑到复赛可能面临迭代次数更多的题目(特别考虑对手出的题). 目前更倾向于使用无迭代的算法(Trevize 2.0.5)
  • IP method 的速度在复赛 5+ 倍规模下表现如何还很难说, 但至少可作为一个正对照
⚠️ **GitHub.com Fallback** ⚠️