不可行模型的处理

本章将介绍杉数求解器COPT对不可行问题的两种处理方式,章节内容构成如下:

在对现实问题进行建模时,我们通常会遇到模型不可行的情况,对应的解状态码为 COPT.INFEASIBLE 。导致模型不可行的原因通常有以下两种:

  1. 描述模型的参数数据输入出错(例如某条约束左端项为空);

  2. 问题本身就不可行,某些约束条件或变量范围之间冲突。

COPT提供两种不可行模型的分析和处理方式,支持的问题类型包括线性规划(LP)和混合整数线性规划(MILP):

  1. 计算不可行模型的IIS:定位导致模型不可行的关键约束和变量范围;

  2. 可行化松弛(FeasRelax):定量给出导致模型不可行的约束或变量范围的冲突值(Violations)。

不可行模型的IIS

IIS(不可约不一致子系统,Irreducible Inconsistent Subsystem)是导致模型不可行的最小冲突集,具有以下特点:

  1. 仍然是不可行的;

  2. 剔除IIS中任意一条约束或变量范围,这个子系统会变得可行;

注意: COPT计算得到的IIS不一定是最小的,也不是唯一的。因此有时需要多次调整约束条件后,重新计算IIS,才能使模型最终变得可行。

下面是一个不可行线性规划模型的例子:

(39)\[\begin{split}\max\quad &z=12x_{1}+8x_{2}\\ \text{s.t.}\quad &5 x_{1} + 2 x_{2} \geq 140\\ &2 x_{1} + 3 x_{2} \leq 90\\ &4 x_{1} + 2 x_{2} \leq 100\\ &x_{1}, x_{2}\geq0\end{split}\]

模型的可行域如下图所示:

_images/copt-iisexample.png

从图示中我们可以清楚看出,相互冲突的两条约束为:

(40)\[\begin{split}&c1:5 x_{1} + 2x_{2} \geq 140\\ &c3:4 x_{1} + 2x_{2} \leq 100\end{split}\]

计算上述模型的IIS结果并写入文件( .iis 格式),文件内容如下,和图示结果一致:

\Generated by Cardinal Operations

Maximize
   12 x[1] + 8 x[2]
Subject To
 c1: 5 x[1] + 2 x[2] >= 140
 c3: 4 x[1] + 2 x[2] <= 100
END

计算IIS

COPT支持的编程接口提供计算不可行模型IIS的函数,得到一个包含模型中相互冲突约束和变量的集合。 用户也可以将IIS计算结果写入文件,指定文件名后缀为 .iis (如: example.iis ), 相关函数名称如 表 37 所示:

表 37 不可行模型IIS计算功能的函数

编程接口

计算IIS

将IIS计算结果写入文件

C

COPT_ComputeIIS

COPT_WriteIIS

C++

Model::ComputeIIS()

Model::WriteIIS()

C#

Model.ComputeIIS()

Model.WriteIIS()

Java

Model.computeIIS()

Model.writeIIS()

Python

Model.computeIIS()

Model.writeIIS()

获取变量和约束的IIS状态

获取变量IIS状态相关函数

计算不可行模型IIS完成后,可以通过获取变量(下/上界)的IIS状态,状态输出值表明变量边界是否在IIS中:

  • 1:指定变量(下界/上界)在IIS中

  • 0:指定变量(下界/上界)不在IIS中

不同编程语言接口提供函数如 表 38 所示:

表 38 获取变量IIS状态相关函数

编程接口

变量下界IIS状态

变量上界IIS状态

C

COPT_GetColLowerIIS

COPT_GetColUpperIIS

C++

Model::GetVarLowerIIS()

Model::GetVarUpperIIS()

C#

Model.GetVarLowerIIS()

Model.GetVarUpperIIS()

Java

Model.getVarLowerIIS()

Model.getVarUpperIIS()

Python

Model.getVarLowerIIS()

Model.getVarUpperIIS()

注意

  • 以上函数的输入值均可以为单个变量( Var 类对象)或一组变量( VarArray 类或 tupledict 类对象);

  • 除C API外,其余编程语言接口的 Var 类还提供获取单个变量IIS状态的函数。

    以Python为例, Var.getLowerIIS()Var.getUpperIIS()

  • 在Python API中,还可以直接访问 Var 类对象的成员属性获取单个变量的IIS状态:

    Var.iislb 获取变量下界IIS状态, Var.iisub 获取变量上界IIS状态。

获取约束IIS状态相关函数

计算不可行模型IIS完成后,COPT支持获取约束(下/上边界)的IIS状态,状态输出值表明约束边界是否在IIS中:

  • 1:指定约束(下边界/上边界)在IIS中

  • 0:指定约束(下边界/上边界)不在IIS中

不同编程语言接口提供函数如 表 39 所示:

表 39 获取约束边界IIS状态相关函数

编程接口

约束下边界IIS状态

约束上边界IIS状态

C

COPT_GetRowLowerIIS

COPT_GetRowUpperIIS

C++

Model::GetConstrLowerIIS()

Model::GetConstrUpperIIS()

C#

Model.GetConstrLowerIIS()

Model.GetConstrUpperIIS()

Java

Model.getConstrLowerIIS()

Model.getConstrUpperIIS()

Python

Model.getConstrLowerIIS()

Model.getConstrUpperIIS()

  • 以上函数的输入值均可以为单条约束( Constraint 类对象)或一组约束( Constraint 类或 ConstrArray 类对象);

  • 除C API外,其余编程语言接口的 Constraint 类还提供获取单条约束IIS状态的函数。

    以Python为例, Constraint.getLowerIIS()Constraint.getUpperIIS()

  • 在Python API中,还可以直接访问 Constraint 类对象的成员属性获取单条约束的IIS状态:

    Constraint.iislb 获取约束下边界IIS状态, Constraint.iisub 获取约束上边界IIS状态。

获取特殊约束IIS状态

此外,COPT提供如 表 40 所示函数,分别获取 SOS 约束和 Indicator 约束的IIS状态。

表 40 获取特殊约束IIS状态相关函数

编程接口

SOS约束

Indicator约束

C

COPT_GetSOSIIS

COPT_GetIndicatorIIS

C++

Model::GetSOSIIS()

Model::GetIndicatorIIS()

C#

Model.GetSOSIIS()

Model.GetIndicatorIIS()

Java

Model.getSOSIIS()

Model.getIndicatorIIS()

Python

Model.getSOSIIS()

Model.getIndicatorIIS()

关于计算和获取IIS状态的函数具体用法和详细介绍,请进一步参考不同编程接口API参考手册的对应章节:

IIS相关参数、属性和信息

优化参数

用户可以通过设置参数 "IISMethod" 的不同取值,选择计算IIS的方法。 不同编程接口的参数设置方法,请参考:参数章节

  • IISMethod

    整数参数。

    计算IIS的方法。

    默认值 -1

    可选值

    -1: 自动选择。

    0: 计算结果质量优先。

    1: 计算效率优先。

属性

COPT提供相关属性,用来描述IIS的计算结果,主要包括判断IIS是否存在以及统计IIS中变量和约束数目两类属性。 不同编程接口的属性获取方法,请参考:属性章节

表 41 IIS计算结果相关属性总览

属性名

类型

属性含义

HasIIS

整数属性

是否存在IIS。

IsMinIIS

整数属性

计算出的IIS是否为极小。

IISCols

整数属性

组成IIS的变量边界的数目。

IISRows

整数属性

组成IIS的约束的数目。

IISSOSs

整数属性

组成IIS的SOS约束的数目。

IISIndicators

整数属性

组成IIS的Indicator约束的数目。

示例代码

用户可以将不可行问题写成模型文件的格式,COPT支持读取模型文件后,直接计算不可行模型的IIS。以Python为例,具体实现示例如下:

from coptpy import *
env = Envr()
model = env.createModel("example")
model.read("example.lp")
model.computeIIS()
model.writeIIS ("example.iis")

用户可以在COPT安装包的 "examples" 文件夹下找到不同编程语言处理不可行模型IIS的示例代码,文件名为: "iis_ex1.py" , 以COPT 7.0版本和Python语言为例,相应的文件路径为: "copt70/examples/python/iis_ex1.py"

不可行模型的可行化松弛

可行化松弛(Feasibility Relaxation)的过程就是通过最小化原不可行模型约束和变量的冲突值,求解变量和约束上下界的松弛量。 用户可以根据可行化松弛定量计算的结果,相应地调整约束或变量范围,从而使得模型变得可行。

计算可行化松弛

COPT支持的编程接口提供计算可行化松弛的函数,同时也可以将可行化松弛模型写入文件,指定文件名后缀为 .relax (如: example.relax ), 相关函数名称如 表 42 所示:

表 42 不可行模型IIS计算功能的函数

编程接口

计算可行化松弛

将可行化松弛模型写入文件

C

COPT_FeasRelax

COPT_WriteRelax

C++

Model::FeasRelax()

Model::WriteRelax()

C#

Model.FeasRelax()

Model.WriteRelax()

Java

Model.feasRelax()

Model.writeRelax()

Python

Model.feasRelax()

Model.writeRelax()

COPT提供了两种方式计算可行化松弛,在除Python之外的编程接口中,用户可以通过对函数的不同参数进行赋值来实现:

  1. 简化版:对模型中全部变量和约束的可行化松弛,只需提供2个参数,以选择全部变量或全部约束

    • ifRelaxVars :是否对变量进行松弛,默认值为: True

    • ifRelaxCons :是否对约束进行松弛,默认值为: True

  2. 完整版:可以提供更多参数输入(指定变量/约束,设置变量/约束边界的惩罚因子)

    • vars:待松弛变量

    • cons:待松弛约束

    • colLowPen:变量下界的惩罚因子

    • colUppPen:变量上界的惩罚因子

    • rowBndPen:约束边界的惩罚因子

    • rowUppPen:若 cons 为双边约束,则表示约束上边界的惩罚因子

    注意: 一般情况下,设置 rowUppPenNULL 即可。

可行化松弛计算函数在不同编程接口中的调用方式和参数名称 略有不同 ,但是函数功能和参数含义是一致的,请进一步参考不同编程接口API参考手册的对应章节获取具体介绍:

注意

  • 针对简化版(Simplified)的可行化松弛计算方式,COPT的Python接口另外提供函数: Model.feasrelaxS(vrelax, crelax),只需输入两个参数( vrelaxcrelax ):

    • vrelax :是否对变量进行松弛,默认值为: True

    • crelax :是否对约束进行松弛,默认值为: True

可行化松弛的相关参数、属性和信息

优化参数

用户可以通过设置参数 "FeasRelaxMode" 的不同取值,选择计算可行化松弛的方法。 不同编程接口的参数设置方法,请参考:参数章节

  • FeasRelaxMode

    整数参数。

    计算可行化松弛的方法。

    默认值 0

    可选值

    0: 最小化加权冲突值。

    1: 计算最小化加权冲突下的原始模型最优可行化松弛。

    2: 最小化冲突数目。

    3: 计算最小化冲突数目下的原始模型最优可行化松弛。

    4: 最小化加权平方冲突值。

    5: 计算最小化加权平方冲突下的原始模型最优可行化松弛。

属性

COPT提供相关属性,用来描述可行化松弛的结果,如 表 43 所示。 不同编程接口的属性获取方法,请参考:属性章节

表 43 可行化松弛结果相关属性总览

属性名

类型

属性含义

HasFeasRelaxSol

整数属性

是否存在可行化松弛结果。

FeasRelaxObj

浮点数属性

可行化松弛值。

信息

COPT提供以下信息,分别表示变量(或约束)下界的可行化松弛量,以及变量(或约束)上界的可行化松弛量。 不同编程接口的信息获取方法,请参考:信息章节

  • RelaxLB

    浮点数信息。

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

  • RelaxUB

    浮点数信息。

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

示例代码

用户可以在COPT安装包的 "examples" 文件夹下找到不同编程语言实现可行化松弛的示例代码,文件名为: "feasrelax_ex1.py" ,以COPT 7.0版本和Python语言为例, 相应的文件路径为: "cop70/examples/python/feasrelax_ex1.py"