优化求解器之LP文件的格式简介

这篇文章是系列的第二篇,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

请注意,同变量边界一样,在generalbinary中列出的所有变量必须出现在目标函数或约束条件中。


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

优化求解器之LP文件的格式简介

上一篇:基于wsdl2java访问外来service服务


下一篇:优化求解器之MPS文件的格式简介