求解日志

杉数求解器COPT在求解过程中会输出日志,用户可以从其中获取求解结果信息,追踪优化求解的处理过程和迭代步骤。本章将会分别对不同算法的求解日志进行解读,内容构成如下:

求解日志相关参数和函数

用户可以通过设置求解日志相关参数,来控制是否显示求解日志。

  • Logging

    整数参数

    是否显示求解日志

    默认值 1

    可选值

    0: 不显示求解日志。

    1: 显示求解日志。

  • LogToConsole

    整数参数

    是否显示求解日志到控制台

    默认值 1

    可选值

    0: 不显示求解日志到控制台。

    1: 显示求解日志到控制台。

杉数求解器COPT提供的和求解日志相关操作有:设置求解日志文件等。

COPT提供设置求解日志文件的相关函数,将求解日志写入至指定的文件(文件名后缀为 .log )中,以便用户对日志进行保存。不同编程接口的函数如 表 48 所示:

表 48 不同编程接口设置求解日志文件函数一览

编程接口

设置求解日志文件函数

C

COPT_SetLogFile

C++

Model::SetLogFile()

C#

Model.SetLogFile()

Java

Model.setLogFile()

Python

Model.setLogFile()

注意: 在调用该函数时,用户需通过参数 logfile 指定保存求解日志的文件名。

求解日志基础信息部分

杉数求解器COPT会根据问题类型运用不同的算法进行求解,在开始求解前均会输出以下基础信息:

Model fingerprint: 2c27ab28

Hardware has 64 cores and 128 threads. Using instruction set X86_AVX512_E1 (14)
Minimizing a MIP problem

其中, Model fingerprint 当前求解模型的唯一编码;

接下来输出的是求解所使用的硬件信息,包括:CPU核数( cores )和线程数( threads )等;

最后是问题类型和优化方向,如:

Minimizing an LP problemMinimizing a MIP problemMinimizing an SDP problem 等。

单纯形法(Simplex)求解日志

按照求解过程的不同阶段,单纯形法求解日志可以划分为以下3个部分:

  1. 预求解(Presolve)

  2. 单纯形法求解过程

  3. 求解结果汇总

这里将会以 afiro.mps 算例的求解日志为例,对单纯形法求解日志中的信息进行解读。

预求解(Presolve)

默认参数设置下,使用单纯形法开始求解前,杉数求解器COPT会对模型进行预求解,以改善模型质量,传给求解器COPT的是经过预处理后的模型。

日志的预求解(Presolve)部分会输出预求解前后模型规模的变化:

The original problem has:
    27 rows, 32 columns and 83 non-zero elements
The presolved problem has:
    7 rows, 10 columns and 28 non-zero elements

LP 问题规模描述包括以下信息项:

  • 约束( rows )数目

  • 变量( columns )数目

  • 系数矩阵非零元素( non-zero elements )数目

以上的求解日志为例,经过预求解后,约束和变量数目,以及系数矩阵非零元素数目都有一定缩减。

单纯形法求解过程

此部分日志提供运用单纯形法求解迭代过程的相关信息。

Starting the simplex solver using up to 8 threads

Method   Iteration           Objective  Primal.NInf   Dual.NInf        Time
Dual             0   -4.8553789460e+02            3           0       0.00s
Dual             3   -4.6476735494e+02            0           0       0.00s
Postsolving
Dual             3   -4.6475314286e+02            0           0       0.00s

其中,首行信息输出显示当前求解算法为单纯形法,使用了8线程( threads )进行计算。

接下来是求解迭代过程,由6列信息项构成:

  • Method :使用的求解算法, "Dual" 表示对偶单纯形法( Dual Simplex

  • Iteration :迭代次数

  • Objective :目标函数值

  • Primal.NInf : 原始问题中不可行个数

  • Dual.NInf :对偶问题中不可行个数

  • Time :求解使用时间(单位:秒)

求解结果汇总

此部分日志是在求解完毕后,对模型求解结果和单纯形法迭代过程进行总结。

Solving finished
Status: Optimal  Objective: -4.6475314286e+02  Iterations: 3  Time: 0.00s

包括的信息项有:

  • 求解状态( Status ):若模型有最优解,则为 Optimal

  • 目标函数值( Objective ):若模型有最优解,Objective 则显示最优目标函数值

  • 总迭代数目( Iterations

  • 总求解时间( Time

若模型不可行,对应日志输出如下:

Solving finished
Status: Infeasible  Objective: -  Iterations: 2  Time: 0.00s

内点法(Barrier)求解日志

按照求解过程的不同阶段,内点法求解日志可以划分为以下 3 个部分:

  1. 预求解(Presolve)

  2. 内点法求解过程

  3. 求解结果汇总

注意: 通过设置优化参数 "LpMethod = 2",可以选择求解线性规划问题的算法为内点法。

同样,以 afiro.mps 算例的求解日志为例,对内点法求解LP问题日志中的信息进行解读。

预求解(Presolve)

默认参数设置下,使用内点法开始求解前,杉数求解器COPT会对模型进行预求解,以改善模型质量,传给求解器COPT的是经过预处理后的模型。

日志的预求解(Presolve)部分会输出预求解前后模型规模的变化:

The original problem has:
    27 rows, 32 columns and 83 non-zero elements
The presolved problem has:
    7 rows, 10 columns and 28 non-zero elements

模型信息部分

此部分日志呈现模型的相关数值信息:

Starting barrier solver using 64 threads

Problem info:
Dualized in presolve:            No
Range of matrix coefficients:    [4e-01,4e+00]
Range of rhs coefficients:       [8e+01,3e+02]
Range of bound coefficients:     [4e+01,1e+02]
Range of cost coefficients:      [2e-01,2e+00]

Factor info:
Number of free columns:          0
Number of dense columns:         0
Number of matrix entries:        2.800e+01
Number of factor entries:        2.800e+01
Number of factor flops:          1.140e+02

其中,首行信息输出显示当前求解算法为内点法,使用了64线程( threads ),其中:

  • Problem info 输出信息包括:是否求解对偶化模型、模型系数矩阵范围、右端项范围、约束变量边界范围和目标函数系数范围;

  • Factor info 输出信息包括:无边界变量数目、致密列数目、线性系统矩阵分解相关信息。

内点法(Barrier)求解过程

这部分日志内容呈现了杉数求解器COPT运用内点法求解的迭代过程,包含的信息项有:迭代( Iter )次数、目标函数值、求解时间( Time )等。 各信息项的解释如下:

  • Iter : 迭代次数

  • Primal.Obj :原始问题目标函数值

  • Dual.Obj : 对偶问题目标函数值

  • Compl:互补性冲突值(Complementarity violation)

  • Primal.Inf : 原始问题不可行的程度

  • Dual.Inf : 对偶问题不可行的程度

  • Time : 求解使用时间(s)

Iter       Primal.Obj         Dual.Obj      Compl  Primal.Inf  Dual.Inf    Time
   0  +2.07010046e+01  -4.97632246e+02   5.89e+03    4.50e+02  2.65e+00   0.02s
   1  -1.18912241e+02  -5.91808560e+02   7.58e+02    3.36e+01  1.61e-01   0.02s
   2  -3.98096520e+02  -4.77597371e+02   2.28e+02    9.32e+00  7.45e-02   0.02s
   3  -4.55223227e+02  -4.68222895e+02   1.86e+01    3.60e-01  2.63e-03   0.02s
   4  -4.64587726e+02  -4.64803786e+02   2.52e-01    7.80e-03  7.93e-06   0.02s
   5  -4.64753143e+02  -4.64753143e+02   3.11e-07    7.80e-09  1.56e-11   0.02s

内点法(Barrier)求解总结

主要信息包括:求解状态、原始和对偶问题最优目标函数值等。

Barrier status:                  OPTIMAL
Primal objective:                -4.64753143e+02
Dual objective:                  -4.64753143e+02
Duality gap (abs/rel):           2.61e-07 / 5.63e-10
Primal infeasibility (abs/rel):  7.80e-09 / 2.60e-11
Dual infeasibility (abs/rel):    1.56e-11 / 6.99e-12

Crossover过程

Starting crossover using up to 8 threads

    1 primal pushes remaining      0.03s
    0 primal pushes remaining      0.03s
    1 dual pushes remaining        0.03s
    0 dual pushes remaining        0.03s

Method   Iteration           Objective  Primal.NInf   Dual.NInf        Time
Dual             1   -4.6475314286e+02            0           0       0.03s
Postsolving
Dual             1   -4.6475314286e+02            0           0       0.03s

求解结果汇总

此部分日志是在求解完毕后,对模型求解结果和单纯形法迭代过程进行总结。

Solving finished
Status: Optimal  Objective: -4.6475314286e+02  Iterations: 1  Time: 0.03s

和单纯形法求解日志一样,此处包括的信息项有:

  • 求解状态( Status ):若模型有最优解,则为 Optimal

  • 目标函数值( Objective ):若模型有最优解, 则 Objective 显示最优目标函数值

  • 总迭代数目( Iterations

  • 总求解时间( Time

分支切割法(Branch-and-Cut)求解日志

按照求解过程的不同阶段,分支切割法求解日志的内容可划分为3个部分:

  1. 预求解(Presolve

  2. 分支切割法搜索求解过程

  3. 结果汇总

这里将会以 cutstock.mps.gz 算例的求解日志为例,对MIP求解日志中的信息进行解读,该算例在COPT安装包 "/examples/data" 目录下。

预求解(Presolve)

为了简化模型,杉数求解器COPT会对MIP模型进行预求解,以去除冗余的约束或变量范围。交给COPT的是经过预处理后的模型,接下来会基于预处理后的模型,开始使用分支切割法进行求解。

Presolve 日志中输出的是预求解前后模型规模的变化:包括原始问题规模和预求解后问题规模的变化。

The original problem has:
    404 rows, 1200 columns and 2598 non-zero elements
    200 binaries and 1000 integers

Presolving the problem

The presolved problem has:
    373 rows, 1169 columns and 2505 non-zero elements
    369 binaries and 800 integers

MIP问题规模描述包括以下信息项:

  • 约束( rows )数目

  • 变量( columns )数目

  • 系数矩阵非零元素( non-zero elements )数目

  • 0-1变量( binaries )数目

  • 整数变量( integers )数目

注意

  • 这里的变量数目( cols )统计的是模型中全部变量的个数,包括连续性变量、整数型变量和0-1变量;

  • 在理论上来说,0-1变量属于特殊的整数型变量,但是此处二者是分开统计的。

以上的求解日志为例,经过预处理后,问题规模(约束和变量数目)得到了缩减。

求解过程

此部分日志输出了分支切割法(Branch-and-Cut)搜索求解的过程。

Starting the MIP solver with 8 threads and 32 tasks

    Nodes    Active  LPit/n  IntInf     BestBound  BestSolution    Gap   Time
        0         1      --       0  3.100000e+01            --    Inf  0.05s
H       0         1      --       0  3.100000e+01  6.800000e+01  54.4%  0.70s
H       0         1      --       0  3.100000e+01  6.600000e+01  53.0%  0.70s
H       0         1      --       0  3.100000e+01  6.500000e+01  52.3%  0.71s
        0         1      --      86  5.591304e+01  6.500000e+01  14.0%  0.72s
H       0         1      --      86  5.591304e+01  6.200000e+01  9.82%  0.74s
        1         2     0.0      86  5.591304e+01  6.200000e+01  9.82%  0.76s
H       1         1    2129       6  6.000000e+01  6.000000e+01  0.00%  0.87s
        2         0    1064       6  6.000000e+01  6.000000e+01  0.00%  0.87s
        2         0    1064       6  6.000000e+01  6.000000e+01  0.00%  0.87s

:由于篇幅限制,此处只呈现求解日志的部分内容,目的是为了日志内容解读的需要。

按照信息项的含义,可将求解过程日志分为以下三部分内容,下面会分别解读各信息项含义:

  • 节点( Nodes )搜索信息(1-4列)

  • 可行解区间信息(5-7列)

  • 求解时间信息(第8列)

节点搜索信息(1-4列):

Nodes:已搜索过的节点个数

Active:尚未被搜索的叶子节点个数

LPit/n:每个节点单纯形法(Simplex)迭代平均次数

IntInf:当前线性松弛(LP relaxtion)的解中尚未取到整数值的整数变量个数

可行解区间信息(5-7列):

BestBound:当前最优的目标边界

BestSolution:当前最优的目标函数值

Gap:上下界之间的相对容差,若小于参数 RelGap 的值,将会停止求解

求解时间信息(第9列):

Time:求解所用时间

注意:

  • Nodes 第1列前的标记(H/*)表示找到了一个新的可行解。

    • H :通过启发式(heuristic)方法找到;

    • * :通过分支(branching)求解子问题的方法找到。

  • 有时会看到 Nodes (已搜索过的节点个数)长时间为0,这说明COPT在处理根节点。在根节点做的工作主要有:产生割平面以及尝试多种启发式方法,以获取最优可行解,目的是减小后续搜索的规模。

求解结果汇总

这部分是求解完毕后,对MIP问题的最终求解状态和分支切割法的搜索过程进行总结,主要包括:模型求解结果和求解搜索工作量两部分内容。

Best solution   : 60.000000000
Best bound      : 60.000000000
Best gap        : 0.0000%
Solve time      : 0.87
Solve node      : 2
MIP status      : solved
Solution status : integer optimal (relative gap limit 0.0001)

Violations    :     absolute     relative
bounds        :            0            0
rows          :            0            0
integrality   :            0

求解结果:

  • 最优目标函数值( Best solution

  • 最优下界( Best bound

  • 最优容差( Best gap

  • 求解状态( Solution status

求解搜索工作量:

  • 求解时间( Solve time

  • 搜索节点个数( Solve node

其中 Violations 部分表示最优解对模型约束和变量范围的满足程度,其中包括:

  • 变量( bounds )和约束( rows )的冲突值

  • 变量整数解( integrality )冲突值

一阶算法(PDLP)GPU求解日志

对于线性规划问题,如果选择PDLP算法(设置参数 LpMethod=6 )进行求解,则可以使用GPU求解模式(运行机器需要配置支持的GPU型号,并且部署所需的CUDA函数库)。

GPU求解模式的日志可以划分为以下几个部分,和CPU求解器略有不同,主要区别点在第2部分:

  1. 预求解部分

  2. 机器GPU硬件信息

  3. 一阶算法PULP求解过程

  4. Crossover部分

  5. 求解结果汇总部分

以LP公开测评集中 "thk_63" 这一算例为例,以下GPU求解模式的求解日志:

机器GPU硬件信息

这一部分日志会输出当前运行机器的GPU硬件信息,以及CUDA版本信息。

Hardware has 1 supported GPU device with CUDA 12.3
  GPU 0: NVIDIA GeForce RTX 4090 (CUDA capability 8.9)

注意:

  1. 日志中的CUDA 12.3指的是当前安装的CUDA driver所能支持的最高版本的CUDA Toolkit。

  2. COPT的GPU求解模式对CUDA库的最低版本要求是11.7(针对Linux系统,对应的CUDA Driver最低版本要求是525.60.13;针对Windows系统,对应的 CUDA Driver最低版本要求是527.41);推荐直接安装CUDA 12.0及以上版本。如需要使用11.7的CUDA库,请分别安装CUDA Toolkit和CUDA Driver, 具体请参考 常见问题章节:GPU使用相关

一阶算法PULP求解过程

这一部分日志会输出PDLP算法的求解迭代过程,以及求解完成后的总结部分,包括PDLP的迭代次数,以及原问题和对偶问题的最优目标值、对偶间隙等。

Starting PDLP solver on GPU 0

Iterations      Primal.Obj        Dual.Obj         Gap  Primal.Inf  Dual.Inf    Time
        0  +6.00000000e+00  +6.00000000e+00  +0.00e+00    7.87e+00  0.00e+00  21.63s
     4000  +1.95436674e+03  -1.77166004e+03  +3.73e+03    2.09e-02  0.00e+00  33.37s
     8000  +1.90433201e+03  +1.55817851e+03  +3.46e+02    1.51e-02  0.00e+00  44.75s
    12000  +1.87801607e+03  +1.85689627e+03  +2.11e+01    1.74e-02  0.00e+00  56.27s
    16000  +1.86810632e+03  +1.86897715e+03  +8.71e-01    4.92e-03  0.00e+00  67.72s
    20000  +1.87022842e+03  +1.86994685e+03  +2.82e-01    3.42e-03  0.00e+00  79.18s
    23640  +1.87099459e+03  +1.87099144e+03  +3.15e-03    4.69e-05  0.00e+00  89.68s

PDLP status:                     OPTIMAL
PDLP iterations:                 23640
Primal objective:                1.87099459e+03
Dual objective:                  1.87099144e+03
Primal infeasibility (abs/rel):  4.69e-05 / 6.20e-07
Dual infeasibility (abs/rel):    0.00e+00 / 0.00e+00
Duality gap (abs/rel):           3.15e-03 / 8.43e-07

Experimental: using crossover to find a basic solution after PDLP
Please set parameter Crossover to 0 if the basic solution is not required
Please set parameter PDLPTol to a smaller value if the crossover cleanup takes too long

Starting crossover using up to 8 threads

50320 primal pushes remaining     92.09s
12495 primal pushes remaining     97.71s
 4124 primal pushes remaining       102s
  202 primal pushes remaining       104s
    0 primal pushes remaining       104s
1480858 dual pushes remaining       104s
 589582 dual pushes remaining       106s
      0 dual pushes remaining       107s

Method   Iteration           Objective  Primal.NInf   Dual.NInf        Time
Dual        986011    1.8710000000e+03            0           0     107.97s
Postsolving
Dual        986011    1.8710000000e+03            0           0     110.56s
Unfolding
Dual       1036742    1.8710000000e+03            0           0     157.25s

Solving finished
Status: Optimal  Objective: 1.8710000000e+03  Iterations: 1036742  Time: 157.69s

注意:使用一阶算法(PDLP)求解后,如果求解至最优( Status: Optimal ),会默认执行Crossover过程至基解, 也可设置 参数 Crossover 为0关闭)。