SCIP对偶解符号标识、API获取及变量基性判定问题咨询

背景信息 #

MPS格式模型 #

NAME          scip
OBJSENSE
  MIN
ROWS
 N  Obj
 G  THISROW
 L  THATROW
 L  LASTROW
COLUMNS
    COLONE    Obj                              1  THATROW                       0.24
    COLTWO    THISROW                      78.26  Obj                              3
    COLTHREE  Obj                           6.24  LASTROW                         -1
    COLTHREE  THATROW                      11.31
    COLFOUR   THISROW                        2.9  Obj                            0.1
RHS
    RHS       THISROW                       92.3  THATROW                       14.8
    RHS       LASTROW                       -0.1
BOUNDS
 LO Bound     COLONE                         0.6
 PL Bound     COLONE
 PL Bound     COLTWO
 PL Bound     COLTHREE
 LO Bound     COLFOUR                         18
 UP Bound     COLFOUR                       31.5
ENDATA

SCIP执行命令 #

SCIP> set presolving emphasis off
SCIP> set propagating maxrounds 0
SCIP> set propagating maxroundsroot 0
SCIP> read model.mps
SCIP> optimize
SCIP> display dualsolution

执行结果 #

THISROW                            0.0383337592639918
LASTROW                                          6.24*

已知结果数值正确，但LASTROW实际对偶值应为-6.24，针对以下问题解答：

问题1：数值后的*是否代表符号标识？若是，如何通过API获取该符号信息？目前调用SCIPgetDualSolVal返回的是6.24。 #

• 是的，*符号对应对偶解的符号修正逻辑。SCIP输出中，*表示该约束是L型（小于等于）约束，此时SCIP内部返回的对偶解符号与线性规划对偶理论的直观定义相反，实际值需要取反。
• API获取符号修正方式：
  1. 调用SCIPgetRowType(row)获取约束类型；
  2. 若约束类型为SCIP_ROWTYPE_LE（L型），实际对偶解为-SCIPgetDualSolVal(scip, row)；若为SCIP_ROWTYPE_GE（G型），直接使用SCIPgetDualSolVal的返回值；目标行（N型）对偶解无意义。

问题2：参数boundconstraint对LASTROW为true，对THISROW为false，这是否对应*标识？若不是，boundconstraint的含义是什么，如何获取正确符号？ #

• 不对应。boundconstraint指该约束是否由变量上下界自动转化而来（比如变量的LO/UP边界被转为单独行约束），和*标识无关。
• 正确符号仍通过约束类型判断，参考问题1的逻辑：根据SCIPgetRowType返回的约束类型，对L型约束的对偶解取反，G型约束直接使用返回值。

问题3：SCIPgetVarRedcost对基变量也返回非零值，不符合需求，如何通过API判断变量在最终解中是基变量还是非基变量？ #

• 使用SCIPgetVarBasisStatus函数判断：
  1. 调用SCIPgetVarBasisStatus(scip, var)，返回值为SCIP_BASESTAT_BASIC时，该变量为基变量；
  2. 返回值为SCIP_BASESTAT_LOWER（处于下界）、SCIP_BASESTAT_UPPER（处于上界）、SCIP_BASESTAT_ZERO（非基且值为0）时，均为非基变量。
• 注意：该函数仅在问题被成功求解为基可行解时有效（如线性规划求解完成后）。

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