跳转至内容

GLPK/建模技巧

来自Wikibooks,开放世界中的开放书籍

此页面提供有关在GLPK中制定优化问题的建议——无论是用MathProg语句加上任何所需的GLPSOL选项表示,还是作为自定义程序编码,这些程序直接或通过绑定使用GLPK函数。


大M法是一种通过引入一个人工量并为其分配一个足够大的常数值来制定某些类型问题的的方法。例如,以下MathProg模型,其中必须要么小于参数要么大于参数,并且其中

param x1;
param x2;
param M;
var x;
var b, binary;
# constraint is active when b = 0
s.t. c1 : x <= x1 + b * M;
# constraint is active when b = 1
s.t. c2 : x >= x2 - (1 - b) * M;

应选择为接近最小值,该值不会减少解空间。在这种情况下,选择过大的可能会导致由于数值精度低而导致的低质量解。有关大M法的更多信息,请参阅教科书。

识别所有解

[编辑 | 编辑源代码]

有时,会提出识别给定线性规划、混合整数规划或整数规划优化问题的所有可行解或所有最优解的问题。GLPK只能返回一个解,顺便说一句,由于可行域既是凸的又是有界的,因此保证它是全局最优的。

这个2011年4月的帖子(多个帖子之一)讨论了在GLPK中添加解枚举功能的优点。提供所有最优(甚至接近最优)解的一个原因是,允许随后的人工干预根据不易于正式建模的次要标准选择要部署的解。

所有最优解

[编辑 | 编辑源代码]

在某些情况下,最优解不是唯一的。

GLPK无法枚举所有最优解。但是,通过使用外部编码,可以创建一个迭代方法,通过该方法,通过应用一个虚假的二元约束使当前的最优解不可行,然后重新提交修改后的问题。在终止时,可以收集各种解以进行进一步分析。这种方法绝不认为是不优雅的。Khachiyan等人(2008)[1]和Provan(1994)[2]提供了更多的一般背景。另请参见此2010年1月的帖子,其中建议使用symphony

N个最佳解

[编辑 | 编辑源代码]

对于IP和MIP问题,此主题的一个变体是识别个最佳解的要求。一种策略涉及维护一个良好的解的动态池,并在发现更好的解时丢弃和替换这些解。这种方法的可行性尚未确定,但这个2011年5月的帖子应该提供一些见解。

所有可行解

[编辑 | 编辑源代码]

在某些情况下,需要寻找所有可行解。

GLPK无法枚举所有可行解。可以使用与上面描述类似的方法,但将目标函数设置为null(或省略)。当目标函数为null时,GLPK自然会在第一个可行解处停止。

另一种方法是使用SCIP,它也能够计算可行解的数量。项目主页有更多细节。SCIP在ZIB学术许可证下发布,这排除了商业用途。

接近零的值

[编辑 | 编辑源代码]

如果生成它们的例程也创建数值上接近零的系数——比如值约为1.0e−10——无论是作为浮点运算的产物、由于设计不良还是两者兼而有之,则自动生成的问题很容易变得缩放不良。同样,当结果中充斥着接近零的值时,无论是来自手工制作的问题还是生成的问题,解都可能难以解释。

GLPK 不提供输入舍入支持——在问题构建时将任何接近零的值设置为真零。该任务仍然是客户端代码的责任。GLPK 也不提供输出舍入支持——在报告时将接近零的值设置为真零。[3]

选择合适的容差来测试和重置接近零的值是客户端的决定,但有时建议使用 1.0e−09。

MathProg 输出

[编辑 | 编辑源代码]

在使用 MathProg 输出模型结果时省略接近零值的变量——在本例中,来自矩阵x[i,j]在 1.0e−03 的容差下——使用以下语句作为模板

printf{i in I, j in J: abs(x[i,j]) >= 0.001} "...", x[i,j], ... ;

您还可以调用其他条件语句来选择或抑制输出。并且您可以调用display代替printf.

非凸函数

[编辑 | 编辑源代码]

非凸函数——无论是约束还是目标函数——不能使用混合整数(线性)规划直接表示。但在某些情况下,可以使用分段线性近似来令人满意地捕捉非凸函数。Croxton 等人 (2002) 描述了三种等价的公式。[4]

通用方法使用二元变量来“切换”所需的分段,并依赖于第 2 类特殊有序集 (SOS2) 约束。以下文档,glpk-sos2.pdf,详细解释了如何在 GLPK 中对非凸分段线性函数建模。

非线性目标函数

[编辑 | 编辑源代码]

极值项

[编辑 | 编辑源代码]

形式为非线性目标函数

可以使用 GLPK MathProg 如下所示建模为 LP(目标函数仍然是凸的)

z =  max_x1_x2 + max_x3_x4 + ...

s.t. max_x1_x2 >= x1
     max_x1_x2 >= x2
     max_x3_x4 >= x3
     max_x3_x4 >= x4
     . . .

更复杂的情况

可以通过用替换来解决,因为两者是等价的。使用类似的想法,最大化的情况

可以通过乘以负一(未显示)来进行类似的转换。有关更多信息,请参阅 2011 年 4 月的帖子

SLP 技术

[编辑 | 编辑源代码]

连续线性规划 (SLP) 使用泰勒级数 展开来逼近非线性目标函数。请参阅 2011 年 4 月的帖子,了解有关 SLP 技术和 GLPK 的讨论,特别是 GLPK 问题对象的管理和热启动的使用。另请注意C# 示例文件t1.cs在 GLPK 示例目录中。

特殊有序集

[编辑 | 编辑源代码]

SOS1:第 1 类特殊有序集

[编辑 | 编辑源代码]

一类特殊有序集 (SOS1),有时记为,表示最多只有一个变量可以非零。

如果所有变量都是二进制的,则 SOS1 等价于,在 MathProg 中

x[1] + x[2] + ... + x[n] <= 1

如果变量是连续的,假设0 <= x[j] <= u[j],其中u[j]x[j]的上界,则 SOS1 可以用 MathProg 表示如下

x[j] <= u[j] * z[j]  for j = 1,...,n,
z[1] + ... + z[n] <= 1,

其中z[j]是辅助二进制变量。

SOS2:二类特殊有序集

[编辑 | 编辑源代码]

请参考此处

例如,在 mathprog 中使用 SOS2 对分段线性函数建模,以下是一个简单的例子,它创建了一个基于澳大利亚国家电力市场昆士兰地区公布的价格敏感度的分段线性电力池价格模型。在市场中的每个半小时,都会计算实际交易区间之前每个半小时交易区间的价格敏感度。对于 2012 年 11 月 22 日 13:00 结束的时期,发布了以下价格敏感度

需求偏移 (MW) 价格
-500 $49.47
-200 $51.54
-100 $51.97
+100 $56.09
+200 $57.25
+500 $155.01
+1000 $450.34

要确定任何需求偏移-500 MW <= x <= +1000 MW时的价格,则可以运行以下 GLPK mathprog 模型

#
#  SOS2 example
#
#  Piecewise linear approximation of 2012-11-22 13:00
#  QLD price sensitivities
#
#  Dr. H J Mackenzie
#  HARD software
#  [email protected]
#

param n >= 0;

set NO_POINTS := 1..n;
set NO_SEGMENTS := 1..(n-1);

param x{NO_POINTS};
param y{NO_POINTS};

param x_value;

var z{i in NO_SEGMENTS} binary;
var s{i in NO_SEGMENTS} >= 0; 
var y_value;

s.t. z_constraint : 
  1 = sum {i in NO_SEGMENTS} z[i];
  
s.t. s_constraint {i in NO_SEGMENTS} : 
  s[i] <= z[i];

s.t. x_constraint :   
  x_value = sum {i in NO_SEGMENTS} ((z[i] * x[i]) + ((x[i+1] - x[i]) * s[i]));

s.t. y_constraint :
  y_value = sum {i in NO_SEGMENTS} ((z[i] * y[i]) + ((y[i+1] - y[i]) * s[i]));

maximize total : y_value;   
solve;

printf "\nx value = %10.2f\n", x_value;
printf "y value = %10.2f\n\n", y_value;
printf "\n\n";

data;

param n := 7;

param : x y :=
  1 -500  49.47
  2 -200  51.54
  3 -100  51.97
  4  100  56.09
  5  200  57.25
  6  500  155.01
  7 1000  450.34
;

param x_value := 260;

end;

网络规划问题

[编辑 | 编辑源代码]

术语“网络规划”源自运筹学。其基础数学属于图论,特别是专门研究有向图的那一部分。

一个常见的网络规划任务是最小费用流问题 (mincost),它寻求一组网络流,以最小化给定的一组与流相关的特定成本。mincost 问题可以用来模拟各种各样的实际优化问题。

GLPK 通过 DIMACS 图数据格式和各种网络算法为网络规划提供了专门的支持。

DIMACS 图格式

[编辑 | 编辑源代码]

GLPK 支持图论问题的一种 DIMACS 格式变体。详细信息在官方文档中进行了全面介绍,因此此处不再赘述。可以在互操作性页面上找到其他背景信息。

API 调用

[编辑 | 编辑源代码]

GLPK 通过函数glp_mincost_okalg支持“超出允许范围”的 mincost 算法。有关更多详细信息,请参阅官方文档。

在相对复杂性方面,一位用户报告(2011 年 4 月),概括地说,“超出允许范围”算法运行速度大约是单纯形法的 5 倍,对于相同问题,使用的内存是 2/3。

GLPK 的 4.49 版本添加了 Bertsekas 和 Tseng 提出的松弛方法,用于解决最小成本流问题。在大规模实例中,RELAX-IV 应该比标准的原始单纯形法快 100 到 1000 倍。此功能是从原始的Fortran 代码转换而来,现在已获得GPLv3 许可。API 调用是通过函数glp_mincost_relax4进行的。该算法本身由麻省理工学院的 Dimitri Bertsekas 开发。[5]

两者glp_mincost_relax4都不glp_mincost_okalg允许非整数数据——所有流量下界、弧容量和单位成本都应该是整数(尽管它们作为双精度类型传递到各自的函数)。

最小成本流 (MCF) 问题基准

[编辑 | 编辑源代码]

以下是一些 Klingman 标准最小成本流实例子集的基准测试(由glp_netgenglp_netgen_prob).

生成)
最小成本流基准时间(秒) 问题 节点 最优值 原始迭代次数 单纯形法时间 [s] OKALG 时间 [s]
101 5000 25536 6191726 17560 104.4 32.5 0.1
102 5000 25387 72337144 23633 152.3 49.5 0.2
103 5000 25355 218947553 28101 186.4 68.4 0.3
104 5000 25344 RELAX-IV 时间 [s] 16808 104.3 117.6 0.2
105 5000 25332 31192578 17239 107.4 28.0 0.2
106 5000 12870 4314276 11401 44.2 16.6 0.1
107 5000 37832 7393769 20315 171.0 48.5 0.2
108 5000 50309 8405738 22806 244.5 76.7 0.3
109 5000 75299 9190300 27267 411.9 110.7 0.5
110 5000 12825 8975048 11215 44.2 17.3 0.1

OKALG 是“超出允许范围”算法。

有关更多详细信息,请参阅此帖子

不幸的是,GLPSOL(GLPK 求解器的命令行接口)无法访问网络规划算法。该--mincost选项目前仅表示要输入的数据为 DIMACS 格式。截至 2013 年 4 月,GLPSOL 通过将其转换为线性程序,然后调用单纯形法求解器来解决 mincost 问题。“超出允许范围”和 RELAX-IV 算法在此上下文中不可用。

第三方计划

[编辑 | 编辑源代码]

LEMON 是一个用C++ 编写的开源图库,因为它属于 COIN-OR 项目的一部分,因此可以与 GLPK 求解器通信。LEMON 接口支持与图形和网络相关的组合优化任务,并且可以识别许多常见的基于图形的数据结构。LEMON 在 Boost 自由软件许可下发布。

集合和数字

[编辑 | 编辑源代码]

集合包含对象——例如数字、字符串和其他集合。不能说集合保存数字条目,但是param可以。所以技巧是创建一个param数组,将集合中的数字对象转换为其数值。考虑以下代码

model;
param tmax;
set T:= 1..tmax;
param tt{t in T} := t;

data;
param tmax := 720;
end;

稍后在模型部分中,使用结构

tt[t]

恢复真实值——可以作为浮点数进行操作或打印的值。

参考文献

[编辑 | 编辑源代码]
  1. Khachiyan,Leonid;Boros,Endre;Borys,Konrad;Elbassioni,Khaled M;Gurvich,Vladimir(2008)。"生成多面体的所有顶点是困难的"离散与计算几何39:174–190。doi:10.1007/s00454-008-9050-5ISSN 0179-5376.
  2. Provan, J Scott (1994). "与网络线性规划相关的多面体顶点的有效枚举". 数学规划. 63 (1–3): 47–64. doi:10.1007/BF01582058. ISSN 0025-5610.
  3. 虽然调用已弃用的 lpx_set_int_parm(lp, LPX_K_ROUND, 1) 仍然可以编译,但它没有任何效果。
  4. Croxton, Keely L; Gendron, Bernard; Magnanti, Thomas L (2002). 非凸分段线性成本最小化问题的混合整数规划模型比较——运筹学研究中心工作论文 OR 363-02. 波士顿,美国:麻省理工学院运筹学研究中心。 {{cite book}}: 未知参数 |month= 被忽略 (帮助)
  5. Bertsekas, Dimitri P; Tseng, Paul (1994). RELAX-IV:一个用于求解最小成本流问题的 RELAX 代码的更快版本 (PDF). 波士顿,美国:麻省理工学院 LIDS。 {{cite book}}: 未知参数 |month= 被忽略 (帮助)
华夏公益教科书