跳轉到內容

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].
華夏公益教科書