加速PySCIPOpt实现Tournament的Median Order求解的MIP程序

问题描述 #

给定含n个顶点的竞赛图T，中位序是一种顶点排列，可使排列中“递增”方向的边数最大化。针对顶点集{0,...,n-1}，已将问题线性化为混合整数规划（MIP）并基于PySCIPOpt实现，n≤7时运行正常，但n=10时运行超1小时仍无结果，推测是模型含O(n⁴)变量导致性能骤降，询问该现象是否正常，以及简便的加速方法或更优实现方案。

解答 #

现象是否正常？ #

完全正常。MIP的求解复杂度随变量规模呈指数级增长，O(n⁴)变量在n=10时变量数达到10000，再加上约束规模的膨胀，求解器的分支定界树会变得异常庞大，搜索时间急剧增加是典型的表现。

简便加速方法 #

• 精简变量模型：检查是否存在冗余变量。中位序问题通常可以用O(n²)的0-1变量建模——定义x_ij=1表示顶点i在排列中位于j之前，目标是最大化Σ(i<j) [a_ij x_ij + a_ji (1-x_ij)]（其中a_ij是竞赛图中i到j的边存在与否的指示符），同时添加传递性约束x_ij + x_jk ≤ 1 + x_ik。n=10时仅45个变量，远低于O(n⁴)的规模。
• 调整求解器参数：在PySCIPOpt中提升启发式强度，比如设置model.setParam('heuristics/rins/freq', 10)增加启发式调用频率；或设置时间限制并聚焦目标优化：model.setParam('limits/time', 3600)、model.setParam('focus/focusobj', 1)，优先找到可行解。
• 强化预处理：启用SCIP的强预处理，设置model.setParam('presolving/maxrounds', 100)，让求解器自动消除冗余约束和变量。

更优实现方案 #

• 改用线性排序问题（LOP）标准模型：中位序本质是LOP的特例，业界通用的LOP模型采用O(n²)变量+O(n³)约束，比自定义的O(n⁴)模型紧凑得多，求解效率会大幅提升。
• 启发式算法替代：若不需要严格最优解，可采用贪心算法（每次选择能增加最多同向边的顶点加入排列）或局部搜索（交换相邻顶点验证目标值提升），n=10时能瞬间得到近似解，甚至可能是最优解。
• 利用竞赛图特性：竞赛图的中位序等价于寻找反向边数最少的排列。可尝试基于顶点出度排序的启发式：先按出度从高到低排列，再进行局部调整，这类方法在竞赛图问题上往往效果显著。

内容的提问来源于stack exchange，提问作者alosc