跳转到内容

GLPK/建模上下限

来自维基教科书,开放的书籍,为开放的世界


约束上的界限

[编辑 | 编辑源代码]

GLPK 预处理器(截至版本 4.45)无法消除或合并重复的行。1 因此,为了减少行数并因此减少求解时间,应该手动合并线性相关的约束方程。例如

s.t. c1 : x + 2 * y <= 4;
s.t. c2 : 2 * x + 4 * y >= 3;

可以替换为

s.t. c3 : 1.5 <= x + 2 * y <= 4;

变量上的界限

[编辑 | 编辑源代码]

在优化变量上设置下限和/或上限,可以在定义时设置,也可以通过专用约束来实现。请注意,MathProg 中的变量是无界的,除非随后被限定或限制(与它们的 API 对应物不同,它们默认情况下为零)。

专用约束

[编辑 | 编辑源代码]

可以使用专用约束轻松实现变量上的界限。

例如,一个斜坡变量,对称地受max_ramp_rate参数

param max_ramp_rate;
var ramp {I};
s.t. upper_feasible_ramp_rate {i in I}: ramp[i] <=  max_ramp_rate;
s.t. lower_feasible_ramp_rate {i in I}: ramp[i] >= −max_ramp_rate;

预处理器将自动消除仅包含一个变量的约束,并使用该信息来收紧该变量的界限——但在求解时,该过程会反转,并且原始约束的主值和对偶值将被适当地确定。或者,如果没有部署预处理器,建议至少将双约束减少到单个约束,以减少模型大小。上面的例子可以改写为

param max_ramp_rate;
var ramp {I};
s.t. feasible_ramp_rate {i in I}: −max_ramp_rate <= ramp[i] <= max_ramp_rate;

变量界限

[编辑 | 编辑源代码]

变量上的界限也可以在定义所述变量时设置。这通常是建模此类限制的首选方法。

因此,前面的斜坡率示例可以实现为

param max_ramp_rate;
var ramp {I}, >= −max_ramp_rate, <= max_ramp_rate;

两种方法的性能差异对于小型模型来说微不足道,但对于大型模型来说可能很重要。下表总结了每种方法的相对优势

专用约束 变量界限
  • 可能更容易理解
  • 对偶值可用于分析
  • 由于约束方程数量减少而加速
  • 内存消耗更少
1.^ 有一项建议要向 GLPK 预处理器添加此功能 [1].
华夏公益教科书