Gurobi求解小规模CVRP模型时预求解耗时久且无变量/行删减
2026-7-4
CVRP求解异常：少车辆多客户场景下Gurobi预求解耗时过长且无变量/行移除
- 用Gurobi 10.0.3求解CVRP，16客户8车辆模型耗时58秒表现正常，但切换到19客户2车辆模型时，耗时超1000秒仍未返回解
- 核心异常：预求解阶段耗时近70秒，但未移除任何行或变量；尝试关闭
PreSolve参数、减少Threads数量，问题依旧
求解日志
Set parameter Threads to value 56 Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (linux64) CPU model: Intel(R) Xeon(R) Platinum 8276 CPU @ 2.20GHz, instruction set [SSE2|AVX|AVX2|AVX512] Thread count: 112 physical cores, 112 logical processors, using up to 56 threads Optimize a model with 524310 rows, 684 columns and 40110732 nonzeros Model fingerprint: 0xf11e235e Variable types: 0 continuous, 684 integer (684 binary) Coefficient statistics: Matrix range [1e+00, 3e+01] Objective range [3e-01, 5e+00] Bounds range [1e+00, 1e+00] RHS range [1e+00, 2e+02] Found heuristic solution: objective 43.3769973 Presolve removed 0 rows and 0 columns (presolve time = 6s) ... Presolve removed 0 rows and 0 columns (presolve time = 13s) ... Presolve removed 0 rows and 0 columns (presolve time = 17s) ... Presolve removed 0 rows and 0 columns (presolve time = 20s) ... Presolve removed 0 rows and 0 columns (presolve time = 25s) ... Presolve removed 0 rows and 0 columns (presolve time = 32s) ... Presolve removed 0 rows and 0 columns (presolve time = 35s) ... Presolve removed 0 rows and 0 columns (presolve time = 40s) ... Presolve removed 0 rows and 0 columns (presolve time = 45s) ... Presolve removed 0 rows and 0 columns (presolve time = 50s) ... Presolve removed 0 rows and 0 columns (presolve time = 55s) ... Presolve removed 0 rows and 0 columns (presolve time = 64s) ... Presolve removed 0 rows and 0 columns (presolve time = 70s) ... Presolve time: 69.83s Presolved: 524310 rows, 684 columns, 40110694 nonzeros Variable types: 0 continuous, 684 integer (684 binary) Root relaxation presolved: 684 rows, 524994 columns, 40111378 nonzeros Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 0 -0.0000000e+00 0.000000e+00 5.700000e+01 115s 41 1.4942544e+01 0.000000e+00 0.000000e+00 115s 41 1.4942544e+01 0.000000e+00 2.000000e-06 115s Use crossover to convert LP symmetric solution to basic solution... Root crossover log... 1 DPushes remaining with DInf 0.0000000e+00 117s 0 DPushes remaining with DInf 0.0000000e+00 117s 27 PPushes remaining with PInf 0.0000000e+00 117s 0 PPushes remaining with PInf 0.0000000e+00 117s Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 117s Root simplex log... Iteration Objective Primal Inf. Dual Inf. Time 72 1.4942544e+01 0.000000e+00 0.000000e+00 117s 72 1.4942544e+01 0.000000e+00 0.000000e+00 119s 72 1.4942544e+01 0.000000e+00 0.000000e+00 121s Root relaxation: objective 1.494254e+01, 72 iterations, 46.50 seconds (39.46 work units) Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 14.94254 0 40 43.37700 14.94254 65.6% - 127s H 0 0 41.2306564 14.94254 63.8% - 135s 0 0 16.53206 0 32 41.23066 16.53206 59.9% - 161s 0 0 16.53206 0 32 41.23066 16.53206 59.9% - 203s H 0 0 37.7572196 16.53206 56.2% - 217s 0 0 16.53206 0 32 37.75722 16.53206 56.2% - 245s 0 0 16.53206 0 40 37.75722 16.53206 56.2% - 276s 0 0 16.53206 0 32 37.75722 16.53206 56.2% - 305s H 0 0 37.4178668 16.53206 55.8% - 320s 0 0 16.53206 0 32 37.41787 16.53206 55.8% - 325s 0 0 16.53206 0 32 37.41787 16.53206 55.8% - 352s 0 0 16.54588 0 50 37.41787 16.54588 55.8% - 388s H 0 0 37.1018717 16.54588 55.4% - 397s H 0 0 34.1244024 16.54588 51.5% - 400s 0 0 16.56291 0 57 34.12440 16.56291 51.5% - 409s 0 0 16.56934 0 58 34.12440 16.56934 51.4% - 421s 0 0 16.62160 0 64 34.12440 16.62160 51.3% - 444s 0 0 16.62160 0 64 34.12440 16.62160 51.3% - 465s 0 0 16.62160 0 56 34.12440 16.62160 51.3% - 489s 0 0 16.64008 0 50 34.12440 16.64008 51.2% - 529s 0 0 16.64405 0 56 34.12440 16.64405 51.2% - 555s 0 0 16.64405 0 57 34.12440 16.64405 51.2% - 573s 0 0 16.65711 0 65 34.12440 16.65711 51.2% - 597s H 0 0 31.7808513 16.65711 47.6% - 614s 0 0 16.66624 0 56 31.78085 16.66624 47.6% - 624s 0 0 16.66624 0 56 31.78085 16.66624 47.6% - 635s 0 0 16.66624 0 47 31.78085 16.66624 47.6% - 668s 0 0 16.66624 0 49 31.78085 16.66624 47.6% - 691s 0 0 16.69817 0 46 31.78085 16.69817 47.5% - 705s H 0 0 31.3353414 16.69817 46.7% - 720s 0 0 16.69817 0 50 31.33534 16.69817 46.7% - 732s 0 0 16.70180 0 57 31.33534 16.70180 46.7% - 760s H 0 0 26.8624304 16.70180 37.8% - 771s H 0 0 24.6815680 16.70180 32.3% - 778s 0 0 16.70180 0 57 24.68157 16.70180 32.3% - 784s 0 0 16.70180 0 56 24.68157 16.70180 32.3% - 801s 0 0 16.70180 0 56 24.68157 16.70180 32.3% - 824s 0 0 16.70180 0 49 24.68157 16.70180 32.3% - 863s
优化建议
1. 模型重构
- 清理冗余约束：19客户2车辆的CVRP模型无需52万+行约束，排查是否存在重复约束或过度复杂的子回路消除规则，替换为MTZ等轻量型子回路约束
- 精简变量：检查二进制变量是否存在冗余，比如合并无差异的路径变量，减少变量规模
2. Gurobi参数调整
- 彻底关闭预求解：设置
Presolve=0和Aggregate=0，跳过无意义的预求解步骤 - 降低线程数：对于小规模车辆的模型，线程过多会增加调度开销，建议设置
Threads=4或Threads=8 - 强化启发式求解：设置
Heuristics=0.5提升启发式优先级，RINS=2增强局部搜索，快速缩小可行解与下界的Gap - 更换根节点求解器：设置
Method=2使用屏障法求解根松弛，避免单纯形法在大规模约束下的低效迭代 - 设置时间/节点限制：通过
TimeLimit=300或NodeLimit=10先获取可行解，再逐步优化精度
3. 对称性消除
2辆车的无差异对称性会大幅降低求解效率，可通过以下方式处理：
- 固定第一辆车的起始路径（例如强制其访问第一个客户），打破对称性
- 设置
Symmetry=2启用高级对称性检测与消除功能
内容的提问来源于stack exchange，提问作者MAYA
相关产品推荐
相关产品推荐
