信息

信息常数描述了模型构成要素(目标函数、约束条件和决策变量)、求解结果以及可行化松弛计算结果等的相关信息。本章节将介绍杉数求解器COPT提供的信息常数及其含义。章节内容构成如下:

表 14 COPT信息常数总览

信息名

类型

信息含义

Obj

浮点数信息

变量(列)的目标函数系数

LB

浮点数信息

变量(列)或者约束(行)的下界

UB

浮点数信息

变量(列)或者约束(行)的上界

Value

浮点数信息

变量(列)的取值

Slack

浮点数信息

松弛变量的取值,也叫做约束的活跃程度(activities),仅适用于线性规划模型

Dual

浮点数信息

对偶变量的取值,仅适用于线性规划模型

RedCost

浮点数信息

变量的Reduced cost,仅适用于线性规划模型

DualFarkas

浮点数信息

对偶Farkas(也叫做对偶极射线),适用于线性规划模型,无可行解或无界情况

PrimalRay

浮点数信息

主元射线(也叫做极射线),适用于线性规划模型,无可行解或无界情况

BestObj

浮点数信息

当前最优目标函数值

BestBnd

浮点数信息

当前最优目标下界

HasIncumbent

整数信息

当前是否有最优可行解

Incumbent

浮点数信息

当前最优可行解

MipCandObj

浮点数信息

当前可行解对应的目标函数值

MipCandidate

浮点数信息

当前可行解

RelaxSolObj

浮点数信息

当前LP松弛问题的目标函数值

RelaxSolution

浮点数信息

当前LP松弛问题的解

RelaxLB

浮点数信息

变量(列)或者约束(行)下界的可行化松弛量

RelaxUB

浮点数信息

变量(列)或者约束(行)上界的可行化松弛量

RelaxValue

浮点数信息

可行化松弛模型中原始模型变量(列)的解

NodeStatus

整数信息

当前节点LP松弛问题的求解状态

注意: Double这个词的准确翻译应是双精度浮点数。表格中和下文为了简便,称之为浮点数。

模型相关信息

  • Obj

    浮点数信息。

    变量(列)的目标函数系数。

  • LB

    浮点数信息。

    变量(列)或者约束(行)的下界。

  • UB

    浮点数信息。

    变量(列)或者约束(行)的上界。

求解结果相关信息

  • Value

    浮点数信息。

    变量(列)的取值。

  • Slack

    浮点数信息。

    松弛变量的取值,也叫做约束的活跃程度(activities)。仅适用于线性规划模型。

  • Dual

    浮点数信息。

    对偶变量的取值。仅适用于线性规划模型。

  • RedCost

    浮点数信息。

    变量的Reduced cost。仅适用于线性规划模型。

对偶Farkas和主元射线

进阶话题。

当线性规划问题无可行解或者无界时, 求解器可以返回对偶Farkas(也叫做对偶极射线) 或者主元射线(也叫做极射线)作为证明。

  • DualFarkas

    浮点数信息。

    线性规划问题无可行解时,线性约束的对偶Farkas(也叫做对偶极射线)。 请设置 "ReqFarkasRay" 这一参数, 以确保求解器可以返回对偶Farkas。

    对偶Farkas的作用可以用形如 \(Ax = 0 \text{ and } l \leq x \leq u\) 的线性规划约束解释。 当该线性规划无可行解时,使用对偶Farkas向量 \(y\) 可以证明线性约束系统存在冲突: \(\max y^TAx < y^T b = 0\)。 如何计算 \(\max y^TAx\): 使用向量 \(\hat{a} = y^TA\),当 \(\hat{a}_i < 0\) 时选择 \(x_i = l_i\) 或者 \(\hat{a}_i > 0\) 时选择 \(x_i = u_i\) , 可以计算出表达式 \(y^TAx\) 的最大可能取值。

    有些应用依赖于另一种等价的线性系统冲突证明: \(\min \bar{y}^TAx > \bar{y}^T b = 0\)。 对于此种情况,可以对求解器返回的对偶Farkas取负值实现,即 \(\bar{y}=-y\)

    在极端情况下,求解器可能无法返回有效的对偶Farkas。 例如当线性规划问题的不可行性微乎其微时。 此时,我们建议用FeasRelax功能研究或者修复线性规划的不可行性。

  • PrimalRay

    浮点数信息。

    线性规划问题无界时,变量的主元射线(也叫做极射线)。 请设置 "ReqFarkasRay" 这一参数,以确保求解器可以返回主元射线。

    对于一个求解最小值的线性规划问题 \(\min c^T x, Ax = b \text{ and } x \geq 0\), 主元射线向量 \(r\) 满足以下条件: \(r \geq 0, Ar = 0\) 以及 \(c^T r < 0\)

可行化松弛结果相关信息

  • RelaxLB

    浮点数信息。

    变量(列)或者约束(行)下界的可行化松弛量。

  • RelaxUB

    浮点数信息。

    变量(列)或者约束(行)上界的可行化松弛量。

  • RelaxValue

    浮点数信息。

    可行化松弛模型中原始模型变量(列)的解。

Callback相关信息

Callback相关信息包括可以在回调函数中获取到的信息。

  • BestObj

    浮点数信息。

    当前最优目标函数值。

  • BestBnd

    浮点数信息。

    当前最优目标下界。

  • HasIncumbent

    整数信息。

    当前是否有最优可行解。

  • Incumbent

    浮点数信息。

    当前最优可行解。

  • MipCandObj

    浮点数信息。

    当前可行解对应的目标函数值。

  • MipCandidate

    浮点数信息。

    当前可行解。

  • RelaxSolObj

    浮点数信息。

    当前LP松弛问题的目标函数值。

  • RelaxSolution

    浮点数信息。

    当前LP松弛问题的解。

  • NodeStatus

    整数信息。

    当前节点LP松弛问题的求解状态。可取值请参考:一般常数章节:解状态(部分) ,除去 NODELIMIT, UNSTARTED, INF_OR_UNB ,其他均为其可能取值。

信息获取方式

在不同的编程接口中,获取信息的方式略有差别,具体请参考: