LP格式文件说明

概述

LP格式作为一种在学界与业界都十分常用的文件格式，具有比MPS格式更易阅读的优点，与MPS文件是列格式不同，LP文件采用行表达式描述问题，且没有固定的书写范围和长度。但从处理性能和阅读难易的角度出发，各家求解器都规范了每行的最字节长度。OptVerse求解器以不超过5000列作为限制。下面我们给出一个标准的LP文件：

\ENCODING-ISO-8859-1
\Problem name:Maximize
Maximizeobj:x1 + 2 x2 + 3 x3 + x4
Subject Tor1: - x1 + x2 + x3 + 10 x4 <= 20
r2: x1 - 3 x2 + x3 <= 30
r3: x2 - 3.5 x4 = 0
Bounds
0 <= x1 <=40
2 <= x4 <= 3
Generals
x4
Binaries
x3
End

`Maximize, Subject to, Bounds, Generals, Binaries,End `分别是各节的指示词，虽然我们求解器对他们的顺序没有强制要求，但最好遵照标准文件中的顺序。各节指示词必须是单独一行书写，且对大小写不敏感。 下面我们对文件的各部分给出详细的描述。

LP格式的注释

反斜杠 (\\) 后面的内容被认为注释，求解器不对其进行解析，于是将被忽略；对于文件中的空白行同样会被忽略。如上例中的

\ENCODING-ISO-8859-1
\Problem name:Maximize

LP格式的关键字

LP格式中的关键字不区分大小写

问题最小(大)化关键词实际上是格式的第一行有效字段有时该行也可以省略，如果省略则默认为最小化问题；End关键词是问题描述的结束，End之后即便还存在字段也不会被解析。

LP格式的节

在介绍节之前，我们首先介绍两个概念：令牌和表达式。令牌是单次能够处理的最小单位，不可通过插入任意字符分割，如空格或换行符。我们将常数、字符串、关键词、操作符、关系符视为令牌。表达式是令牌通过加入空格组合的令牌组，我们仅支持采用空格作为令牌组的令牌分隔符。如表达式: `10 x1 + x2 + 2000 `中的10 和 2000 是常数令牌，变量名 `x1` 和 `x2` 是字符串令牌，令牌之间采用空格分隔； 表达式 `10,x1,+,x2,+,2000`则不是令牌组，仅仅是个字符串。且不是变量名，因为变量名、约束名、目标函数名需要满足：彼此不同，名字长度不超过255个字符，不能用数字或者操作符+,-, *, ^,与关系符 <, >, = 开头且不能是关键词，变量名最好不要用 `E`+数字形式，如 `E9、e9`；这会被理解成数字。推荐使用字符和数字组合，如 `var001。`

OBJECTIVE FUNCTION节

目标函数可采用 `maximize`或 `minimize`关键词开始，关键词后不能再出现其它字符，形式为：

minimize
-x1 + x2 + -x3 + 0.5 x1 + 100 + x4 + 20

如上形式可以看出：

1. `minmize` 单独一行。

2. 变量可以直接与负号(`-`)连接，如 ` x1,x3`。

3. 变量可以多次出现，我们采用聚合多次系数，本例中为 `x1`的系数终于为 `0.5(-1+0.5)`。

4. 偏移量可以出现在表达式中间或结尾，如 100 和 20。

在实际使用中目标函数可以提供一个名字，并且可以多行书写，但需注意一些细节，如

minimize
obj:-x1 + x2 + -x3 + 0.5 x1
     100 + x4 + x5 + 1.5 + 2.0
     x6

CONSTRAINTS节

约束满足节的关键词 subject to 同样需要单独一行书写。每个新的约束必须另起一行。约束可以提供约束名，在约束名之后跟冒号。约束名必须遵循与变量名称相同的规则。我们要求必须为约束指定约束名。

约束被定义为通过变量、常数、操作符组成的线性表达式，后跟关系符和数字右侧系数。使用以下关系符之一可以直观地指示约束的意义：`>=、<=`或 `=`。例如，这是一个命名约束：

subject to:
depts01： -x1 + 0.5 x2 <= 40

BOUNDS节（可选）

bounds节是可选的，如果存在则表明需要对变量使用提供的变量界。根据界被提供的个数，每一行表达式可以分为单边界或双边界。单边界可为 `x>=10`或者 `x<10`，双边界可为 `10 <= x <= 15`，这两种界都不允许多行书写。如果没有提供变量界，则默认采用求解器的内部值。如果为变量定义了单个边界，则将使用适当的默认边界作为第二个边界。有几条准则需要遵守：

1. 固定边界表达式不被允许，即不能写为 `x1=20` 而要统一写为 `20<=x1<=20`。

2. 支持 `+(-)inf`， 如 `x1> -inf`。

3. 支持 `free`, 如 `x1 free`。

GENERALS和BINARIES节（可选）

LP 文件的 generals 和 binaries 节用于指示在可行解中必须具有整数值的变量。这两节由于形式相似，我们将其放在同一个部分介绍，实际上他们是否同时存在互不影响。注册在这两节的变量将具有的默认边界的定义。对于在generals 部分注册的变量，默认范围是 0 和$10^{20}$。对于在 binaries 部分注册的变量，默认边界是 0 和 1。 变量注册的方式是通过将变量罗列到对应节，如

Generals
x4 x5 x6 x7
x8 x9
Binaries
x1 x2 x3 x4

可见，不同变量之间通过空格分割，允许多行书写, 同时我们允许变量注册到不同节，如变量 `x4`，最终的变量类型为其可行区间最小的类型。

注：现阶段我们求解器仅支持线性问题，对于非线性字段和半连续、半整型暂不支持。