这篇文章是系列的第二篇,MindOpt支持带有一些扩展名的 LP 文件格式。LP 格式不是一个明确定义的标准,不同的优化包解释同一个LP 文件的方式可能会略有不同。下列通过一个案例来详细讲述LP文件的命名规范。
线性规划模型:
max x1 + 2 x2 + 3 x3 + x4
s.t. − x1 + x2 + x3 + 10 x4 ≤ 20
x1 − 3 x2 + x3 ≤ 30
x2 - 3.5 x4 = 0
0 ≤ x1 ≤ 40,x2 ≥ 0,x3 ≥ 0,2 ≤ x4 ≤ 3
如果写成LP文件,展示如下:
Maximize
obj: x1 + 2 x2 + 3 x3 + x4 #目标函数
Subject To #约束条件
c1: - x1 + x2 + x3 + 10 x4 <= 20
c2: x1 - 3 x2 + x3 <= 30
c3: x2 - 3.5 x4 = 0
Bounds #表示变量的边界,里面若有 free 则表示该变量无上下界
0 <= x1 <= 40
2 <= x4 <= 3
General #定义变量类型,General表示整数变量
x4
End #结束
结合上述优化模型来说明LP文件的命名规范:
1,LP文件内容
LP文件包含了多个指定目标,约束条件,变量类型和变量边界。LP文件中部分关键字的组合可以为任意大小写字母。
2,目标函数
目标函数通常以max、maximum、maximize、min、minimum、minimize关键字开头。这类关键字定义了目标函数的求解目标,即: x1 + 2 x2 + 3 x3 + 4 x4
目标函数可以自己命名。如果没有命名,则默认为obj
目标函数包含线性项和二次项(MindOpt优化求解器暂不支持对二次规划问题的求解,这一功能将在后续版本中发布)。线性项如: 3x1 + x2 - 0.3 x3
二次项如:
minimize
myobj: 3 x1 + 2x2 - 0.5 x3 + [ x1^2 + 3 x1 * x2 ]/2
其实等同于 minimize 3 x1 + 2 x2 − 0.5⋅ x3 + 1/2(x12 + 3⋅ x1⋅ x2)
3,约束条件
约束条件部分应该以subj to、subject to、s.t.、st之一开头。约束条件包含名称(可不填)、相应的表达式和边界。
Subject To
c1: - x1 + x2 + x3 + 10 x4 <= 20
c2: x1 - 3 x2 + x3 <= 30
c3: x2 - 3.5 x4 = 0
4,变量边界
可以指定变量的边界。
bound
bounds
bounds部分可不填,但如果填写了,则要遵从边界约束条件。
请注意,在变量边界中列出的所有变量,必须出现在目标函数或约束条件中。
变量边界默认的下限为0,上限为+∞。
如果变量用关键字free,则表示变量的区间为(−∞ ,+∞)
常见的变量边界表示:
UP - 上界
LO - 下界
MI - 下界为负无穷
PL - 上界为正无穷
FX - 固定值
FR - ( − ∞ , ∞ )
例如:
bounds
x1 < 2
0.5 <= x1
x2 free
x3 = 5
1 <= x4 < +inf
5,变量类型
变量类型这部分可以用以下两种方式之一来表达
bin
binaries
binary
或
gen
general
另外,还需要在general
下面列出所有的整数变量,在binary
下面列出所有的二进制(也就是变量边界为0和1的整数变量)。
general
x1 x2
binary
x3 x4
请注意,同变量边界一样,在general
和binary
中列出的所有变量必须出现在目标函数或约束条件中。
6,结束部分
结尾,LP 格式的文件必须以关键字end
结束。
end
此外,请注意LP文件格式对于命名有严格的要求。
目标函数、约束条件和变量的名称可以由小写字母a-z、大写字母A-Z、数字0-9以及如下的字符组成:
aB6`*!(),/~
注意:数字、句号、字母e和字母E不能用作名称的开头。关键字也不得用于命名。
另外,当使用如 \0
等在 LP 文件中不被允许的名称,那么求解器将自动更改该名称,并且还会返回 Warning 信息。
LP文件中生成有效命名的工作原理如下:
首先名称被表示为 utf-8
编码的字符串,对于其中的任意一个Unicode 字符c
,分为以下几种情况:
- 如果
c==_
(下划线),则输出为__
(两个下划线)。 - 如果
c
是有效的 LP 名称字符,则输出仅为c
. - 如果
c
是 ASCII 范围内的另一个字符,则输出为_XX
,其中XX
是该字符的十六进制代码。 - 如果
c
是127-65535范围内的字符,则输出为_uXXXX,其中XXXX是该字符的十六进制代码。 - 如果
c
是大于 65535 的字符,则输出为_UXXXXXXXX
,其中XXXXXXXX
是该字符的十六进制代码。
无效的utf-8
子字符串转义为_XX'
,如果名称以句点e
或开头E
,则该字符转义为_XX
。
联系我们:
邮箱:solver.damo@list.alibaba-inc.com
钉钉群:32451444
更多更新通知:https://solver.damo.alibaba.com