Re: [Help-glpk] sensitivity analysis
unlimitedly increase, value of c2 would be 1 (which is its upper bound). Must read which is its an implied upper bound due to other constraints. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis
I read again the documentation. The Chapter 4 helped me a lot. But I still do not understand the sensitivity analysis exactly. Let see again the the problem: max 9x1+20x2+45x3 subject to c1:2x1+5x2+15x3=5000 c2:4x1+6x2+8x3=2 end For the second constraint I get an activity range (6 000;10 000). The documentation says: For every auxiliary (row) or structural (column) non-basic variable the routine starts changing its active bound in both direction. The first of the two lines in the report corresponds to decreasing, and the second line corresponds to increasing of the active bound. Since the variable being analyzed is non-basic, its activity, which is equal to its active bound, also starts changing. What is the active bound for the second constraint? For me an activity range (+inf;10 000) would be logical. The RHS of c2:4x1+6x2+8x3=2 can be increased by any number (because the slack will be higher and nothing else happens) and can be reduced by 10 000, ie the constraint become c2:4x1+6x2+8x3=1 and the second auxiliary variable become non-basic variable. Could you write in one or two sentences how what does (6 000;10 000) activity range means for second constraints? Since row c2 is non-active, that is, its auxiliary variable is basic, the objective coefficient sensitivity analysis is performed, i.e. what happens if the objective coefficient at c2 (which initially is 0, because c2 is an auxiliary variable) starts changing in both direction. In the analysis report Obj.coef. range shows minimal and maximal values of the objective coefficient at that basic variable on which the basis is still not changed, and Activity range shows corresponding values of the basic variable if its objective coefficient would have that value. In your example, if c2 would have obj. coef. -.625, its value in the optimal basis would be 6000, and if the obj. coef. would unlimitedly increase, value of c2 would be 1 (which is its upper bound). Note that the analysis for basic variables has more sense for structural variables (columns) rather than for auxiliary ones (rows). ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis
I have some misunderstand about GLPK's sensitivity analysis. I read several times the GLPK documentation but some details no more clear for me. Let investigate the following problem: max 9x1+20x2+45x3 subject to 2x1+5x2+15x3=5000 4x1+6x2+8x3=2 end I get the following output: Status: OPTIMAL Objective: obj = 22500 (MAXimum) No. Row name St Activity Lower bound Upper bound Marginal -- -- - - - - 1 r.7 NU 50005000 4.5 2 r.8 B 1 2 No. Column name St Activity Lower bound Upper bound Marginal -- -- - - - - 1 x1 B 2500 0 2 x2 NL 0 0 -2.5 3 x3 NL 0 0 -22.5 The marginal column is the value of dual variable (as I understood). The value is OK, but why it is negative? Becuse the dual constraint is =? So, simply: the dual slack variables for nonnegative primal structural variables are always negatve? Because you maximize. See the glpk reference manual, Chapter 4 Advanced API Routines, Section 4.1 Background for details how reduced costs (i.e. Lagrange multipliers) are computed. Let us see the sensitivity report Problem: Objective: obj = 22500 (MAXimum) No. Row name St Activity Slack Lower bound Activity Obj coef Obj value at Limiting Marginal Upper bound range range break point variable -- -- - - - - - - 1 r.7 NU5000.0. -Inf . -4.5. x1 4.55000.0 1.0 +Inf 45000.0 r.8 2 r.8 BS 1.0 1.0 -Inf 6000.0 -.62500 16250.0 x2 .2.0 1.0 +Inf +Inf GLPK 4.55 - SENSITIVITY ANALYSIS REPORT Page 2 Problem: Objective: obj = 22500 (MAXimum) No. Column name St Activity Obj coef Lower bound Activity Obj coef Obj value at Limiting Marginal Upper bound range range break point variable -- -- - - - - - - 1 x1 BS2500.0 9.0. -Inf 8.0 2.0 x2 . +Inf 2500.0 +Inf +Inf 2 x2 NL. 20.0. -2500.0 -Inf 28750.0 r.8 -2.5 +Inf 1000.0 22.5 2.0 x1 3 x3 NL. 45.0. -454.54545 -Inf 32727.27273 r.8 -22.5 +Inf 333.3 67.5 15000.0 x1 End of report The glpk documentation says: The sensitivity analysis of active bounds is performed only for rows, which are active constraints, and only for non-basic columns, because inactive constraints and basic columns have no active bounds. OK, it is quite logical. But, the second constraint (r.8) is not active constraint, we have 1 slack. According to the previous sentence, the sensitivity analysis would not be performed. But what does 6000;1 Activity range means? This corresponds to sensitivity analysis of objective coefficients, not to analysis of active bounds. Please read more carefully Subsection 3.4 Post-optimal analysis routines in the glpk reference manual. [...] PS: If you include glpk output in your e-mail, please use a fixed-pitch font/formatting. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk [NC]
If a row is non-active, changing its bounds does not affect the basic solution. This is only true for small change but not true for large change. No, this is true for any change, assuming that a new lower bound remains not greater than and a new upper bound remains not less than the current optimal value of a variable. If a constraint is non-active, this is the same as that constraint would be omitted at all. Please note that the post-optimal analysis is an analysis of the neighborhood of the optimal point where the basis is not changed. Most probably you need a parametric analysis, which is not implemented in glpk. For example: if you change the rhs of the r row below 200. You will get new solution. You can also check this with Excel. Is there any way to get correct range of non-active row? ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk [NC]
The information in sensitivity analysis table in glpk seems to be incorrect. For example: for the problem in sample.c file and in the manual section 1.3.1 (page 14). [...] However the correct range of the row r would be 200- +inf not (120- 520). Do I miss something here? The row r is non-active in the optimal solution reported (i.e. corresponding auxiliary variable is basic); in this case 'Activity range' is related to the objective function, not to the row itself. For example, 120 means that that r would take on the value 120 when its objective coefficient (which is normally zero) would go on its lower limit -1.7 reported in the field 'Obj coef range'. For detailed explanations of the report structure please see Section 3.4 Post-optimal analysis routines in the glpk reference manual, pp.107-114. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk [NC]
For detailed explanations of the report structure please see Section 3.4 Post-optimal analysis routines in the glpk reference manual, pp.107-114. You need reading the paragraph Sensitivity analysis of objective coefficients at basic variables on pp.112-113. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
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
Re: [Help-glpk] sensitivity analysis table in glpk
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); Thank you for the suggestion. Undoubtely, there must be some api routines for range analysis. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
I tried it on my mac os x and /dev/stdout also corresponds to the standard output (since it is a unix variant). The problem is, of course, the out-dated LPX_OPT. Even after glpsol found the optimal solution, I still got the output saying: ... Size of triangular part = 1 0: obj = 1.825236167e+05 infeas = 2.463e+05 (0) * 1: obj = 2.70500e+03 infeas = 0.000e+00 (0) *28: obj = 2.243054181e+05 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND Time used: 0.0 secs ... No range information since solution is not optimal. End of output This is a scaling/tolerance issue, i.e. glp_simplex reports that the status is optimal, but glp_warm_up does not agree with that. Please replace line 70, file glplpx03.c: lpx_warm_up(lp); by the following line: glp_factorize(lp); This must help. (I will try to re-implement lpx_print_sens_bnds using new api routines.) ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
This is a scaling/tolerance issue, i.e. glp_simplex reports that the status is optimal, but glp_warm_up does not agree with that. Please replace line 70, file glplpx03.c: lpx_warm_up(lp); by the following line: glp_factorize(lp); This must help. (I will try to re-implement lpx_print_sens_bnds using new api routines.) Another way is just disable the lp presolver (--nopresol). ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
Saturday, December 26, 2009, 11:02:20 AM, you wrote: I tried it on my mac os x and /dev/stdout also corresponds to the standard output (since it is a unix variant). The problem is, of course, the out-dated LPX_OPT. Even after glpsol found the optimal solution, I still got the output saying: ... Size of triangular part = 1 0: obj = 1.825236167e+05 infeas = 2.463e+05 (0) * 1: obj = 2.70500e+03 infeas = 0.000e+00 (0) *28: obj = 2.243054181e+05 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND Time used: 0.0 secs ... No range information since solution is not optimal. End of output This is a scaling/tolerance issue, i.e. glp_simplex reports that the status is optimal, but glp_warm_up does not agree with that. Please replace line 70, file glplpx03.c: lpx_warm_up(lp); by the following line: glp_factorize(lp); This must help. (I will try to re-implement lpx_print_sens_bnds using new api routines.) Another way is just disable the lp presolver (--nopresol). ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
Another way is just disable the lp presolver (--nopresol). I tried the --nopresol switch, and still got the same result. My glpsol version is 4.39. I think I will look forward to the new release. 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. Sensitivity report is almost a must-have for teaching purposes, so it is probably desirable to include this feature in GMPL as well. I don't know, maybe it is helpful (pedantically) to rename the two sections of the report as the primal sensitivity info (on the objective coefficients) and the dual sensitivity info (on the right-hand-sides). ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
I was wondering about if LPX_OPT == GLP_OPT when checking the solution status? No, LPX_OPT != GLP_OPT. (LPX_OPT macro is deprecated and should not be used.) It seems pyglpk used GLP_OPT while the routine lpx_print_sens_bnds(...) used LPX_OPT, and I got wrong outputs. lpx_print_sens_bnds uses deprecated api routines prefixed with lpx_. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
Thanks for that information. I checked the source code, and wonder if there is a way to have the output go to the standard output. Currently I only saw a possibility that requires a little change to the source code: The prototype is: int lpx_print_sens_bnds(LPX *lp, const char *fname) There is a line like this: fp = xfopen(fname, w); If it is changed to something like this: fp = fname? xfopen(fname, w): stdout; where 'stdout' stands for the standard output (not sure if I got this right), then we can have things printed to standard output as well. Writing to stdout should be supported by xfopen in the same way as it supports, for example, .gz files, i.e. something like this: fp = xfopen(/dev/stdout, w); where /dev/stdout is a special filename recognized within xfopen (may be using - would be even better). This would allow writing to stdout everywhere the filename is specified (for example, in glpsol). However, this feature is not implemented yet, though it is quite easy to implement it. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
BTW, glpsol --bounds /dev/stdout must work under Linux while glpsol --bounds CON must work under Windows. Great! This answers my previous question (please disregard that one). Thanks a lot! ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
BTW, glpsol --bounds /dev/stdout must work under Linux while glpsol --bounds CON must work under Windows. I tried it on my mac os x and /dev/stdout also corresponds to the standard output (since it is a unix variant). The problem is, of course, the out-dated LPX_OPT. Even after glpsol found the optimal solution, I still got the output saying: ... Size of triangular part = 1 0: obj = 1.825236167e+05 infeas = 2.463e+05 (0) * 1: obj = 2.70500e+03 infeas = 0.000e+00 (0) *28: obj = 2.243054181e+05 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND Time used: 0.0 secs ... No range information since solution is not optimal. End of output ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
I wonder if there is a simply way to print a sensitivity analysis table below with an LP in glpk? Look at the routine lpx_print_sens_bnds (file glpk/src/glplpx03.c). It implements the glpsol option --bounds. Thanks for that information. I checked the source code, and wonder if there is a way to have the output go to the standard output. Currently I only saw a possibility that requires a little change to the source code: The prototype is: int lpx_print_sens_bnds(LPX *lp, const char *fname) There is a line like this: fp = xfopen(fname, w); If it is changed to something like this: fp = fname? xfopen(fname, w): stdout; where 'stdout' stands for the standard output (not sure if I got this right), then we can have things printed to standard output as well. Yingjie ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
Look at the routine lpx_print_sens_bnds (file glpk/src/glplpx03.c). It implements the glpsol option --bounds. I was wondering about if LPX_OPT == GLP_OPT when checking the solution status? It seems pyglpk used GLP_OPT while the routine lpx_print_sens_bnds(...) used LPX_OPT, and I got wrong outputs. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] sensitivity analysis table in glpk
I wonder if there is a simply way to print a sensitivity analysis table below with an LP in glpk? Look at the routine lpx_print_sens_bnds (file glpk/src/glplpx03.c). It implements the glpsol option --bounds. ___ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk
