GLPK/Modeling Lower and Uppper Bounds

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


Bounds on constraints[edit]

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]

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]

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]

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]

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]

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