Re: [Help-glpk] sensitivity analysis table in glpk

[Andrew Makhorin]

>> I wonder if it is possible for the API to support printing
>> the sensitivity info for just one particular
>> variable/constraint? This is useful when one is only
>> interested in some of the sensitivity bounds.
>> 

> It might be even better if the API has routines to 
> calculate the max increase and max decrease of the
> bounds, for example:

> /**sensitivity bounds for coeficient in the objective*/
> glp_coef_sensit_bounds(GLP* lp, int var_idx, 
>    double* max_dec, double* max_inc);,

> /**sensitiviy bounds for the upper/lower bounds of a constraint*/
> glp_con_bounds_sensit(GLP* lp, int con_idx,
>    double* max_dec_lb, double* max_inc_lb,
>    double* max_dec_ub, double* max_inc_ub);

> /**sensitiviy bounds for the upper/lower bounds of a variable*/
> glp_var_bounds_sensit(GLP* lp, int var_idx, 
>    double* max_dec_lb, double* max_inc_lb,
>    double* max_dec_ub, double* max_inc_ub);

I included in glpk 4.42 the following new api routines:

/***********************************************************************
*  NAME
*
*  glp_analyze_bound - analyze active bound of non-basic variable
*
*  SYNOPSIS
*
*  void glp_analyze_bound(glp_prob *P, int k, double *limit1, int *var1,
*     double *limit2, int *var2);
*
*  DESCRIPTION
*
*  The routine glp_analyze_bound analyzes the effect of varying the
*  active bound of specified non-basic variable.
*
*  The non-basic variable is specified by the parameter k, where
*  1 <= k <= m means auxiliary variable of corresponding row while
*  m+1 <= k <= m+n means structural variable (column).
*
*  Note that the current basic solution must be optimal, and the basis
*  factorization must exist.
*
*  Results of the analysis have the following meaning.
*
*  value1 is the minimal value of the active bound, at which the basis
*  still remains primal feasible and thus optimal. -DBL_MAX means that
*  the active bound has no lower limit.
*
*  var1 is the ordinal number of an auxiliary (1 to m) or structural
*  (m+1 to n) basic variable, which reaches its bound first and thereby
*  limits further decreasing the active bound being analyzed.
*  if value1 = -DBL_MAX, var1 is set to 0.
*
*  value2 is the maximal value of the active bound, at which the basis
*  still remains primal feasible and thus optimal. +DBL_MAX means that
*  the active bound has no upper limit.
*
*  var2 is the ordinal number of an auxiliary (1 to m) or structural
*  (m+1 to n) basic variable, which reaches its bound first and thereby
*  limits further increasing the active bound being analyzed.
*  if value2 = +DBL_MAX, var2 is set to 0. */

/***********************************************************************
*  NAME
*
*  glp_analyze_coef - analyze objective coefficient at basic variable
*
*  SYNOPSIS
*
*  void glp_analyze_coef(glp_prob *P, int k, double *coef1, int *var1,
*     double *value1, double *coef2, int *var2, double *value2);
*
*  DESCRIPTION
*
*  The routine glp_analyze_coef analyzes the effect of varying the
*  objective coefficient at specified basic variable.
*
*  The basic variable is specified by the parameter k, where
*  1 <= k <= m means auxiliary variable of corresponding row while
*  m+1 <= k <= m+n means structural variable (column).
*
*  Note that the current basic solution must be optimal, and the basis
*  factorization must exist.
*
*  Results of the analysis have the following meaning.
*
*  coef1 is the minimal value of the objective coefficient, at which
*  the basis still remains dual feasible and thus optimal. -DBL_MAX
*  means that the objective coefficient has no lower limit.
*
*  var1 is the ordinal number of an auxiliary (1 to m) or structural
*  (m+1 to n) non-basic variable, whose reduced cost reaches its zero
*  bound first and thereby limits further decreasing the objective
*  coefficient being analyzed. If coef1 = -DBL_MAX, var1 is set to 0.
*
*  value1 is value of the basic variable being analyzed in an adjacent
*  basis, which is defined as follows. Let the objective coefficient
*  reaches its minimal value (coef1) and continues decreasing. Then the
*  reduced cost of the limiting non-basic variable (var1) becomes dual
*  infeasible and the current basis becomes non-optimal that forces the
*  limiting non-basic variable to enter the basis replacing there some
*  basic variable that leaves the basis to keep primal feasibility.
*  Should note that on determining the adjacent basis current bounds
*  of the basic variable being analyzed are ignored as if it were free
*  (unbounded) variable, so it cannot leave the basis. It may happen
*  that no dual feasible adjacent basis exists, in which case value1 is
*  set to -DBL_MAX or +DBL_MAX.
*
*  coef2 is the maximal value of the objective coefficient, at which
*  the basis still remains dual feasible and thus optimal. +DBL_MAX
*  means that the objective coefficient has no upper limit.
*
*  var2 is the ordinal number of an auxiliary (1 to m) or structural
*  (m+1 to n) non-basic variable, whose reduced cost reaches its zero
*  bound first and thereby limits further increasing the objective
*  coefficient being analyzed. If coef2 = +DBL_MAX, var2 is set to 0.
*
*  value2 is value of the basic variable being analyzed in an adjacent
*  basis, which is defined exactly in the same way as value1 above with
*  exception that now the objective coefficient is increasing. */

Based on these two routines I wrote new api routine glp_print_ranges
(also included in 4.42), which performs complete sensitivity analysis
and writes the analysis report in human-readable format to a text file.
The new routine replaces lpx_print_sens_bnds and makes it deprecated
(however, the latter has been kept in the package to provide backward
compatibility). The sensitivity analysis feature is also available in
glpsol.

Also I modified internal i/o stream routines to recognize special
filenames "/dev/stdin", "/dev/stdout", and "/dev/stderr". These
filenames can be specified in glpsol command-line parameters as
ordinary filenames. For example:

   glpsol -m /dev/stdin -o /dev/stdout

will read model from stdin and write solution to stdout. This feature
is platform-independent.