GLPK/Modeling Lower and Upper Bounds

From Wikibooks, open books for an open world
Jump to navigation Jump to search


Bounds on constraints[edit | edit source]

The GLPK presolver (as of version 4.45) cannot eliminate or combine duplicate rows.1 Therefore, in order to reduce the row count and hence the solution time, linearly dependent constraint equations should be manually combined. For example:

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

can be replaced by:

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

Bounds on variables[edit | edit source]

Placing lower and/or upper bounds on optimization variables can either be set on definition or achieved through dedicated constraints. Be aware that variables in MathProg are unbounded unless subsequently qualified or restricted (unlike their API counterparts, which are zeroed by default).

Dedicated constraints[edit | edit source]

Bounds on variables can be readily implemented using dedicated constraints.

Take, for instance, a ramp variable, symmetrically restricted by the max_ramp_rate parameter:

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;

The presolver will automatically eliminate constraints containing one variable only and use that information instead to tighten the bounds on that variable — on solution however, the process is reversed and the primary and dual values for the original constraint are duly determined. Alternatively, if the presolver is not deployed, it is advisable to at least reduce double constraints to a single constraint in order to lessen the model size. The above example can thus be recast:

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

Variable bounds[edit | edit source]

Bounds on variables may also be set when defining the variable in question. This is usually the preferred way to model such restrictions.

The previous ramp rate example can thus be achieved:

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

Comparison[edit | edit source]

The performance difference between the two methods is negligible for small models, but may be significant for larger models. The following table summaries the relative advantages of each method:

Dedicated constraints Variable bounds
  • possibly simpler to conceptualize 
  • dual value available for analysis
  • speed up due to reduced number of constraint equations 
  • less memory consumption

Notes[edit | edit source]

1.^ There is a proposal to add this feature to the GLPK presolver [1].