Re: [Help-glpk] Finding minimum and maximum objective value

[Andrew Makhorin]

> Thank you for your quick reply. I've added status checks as you
> suggested but they don't seem to identify that there's something
> wrong, ie. solving in both directions returns GLP_OPT. Exporting the
> problem to cplex-lp format and solving it with glpsol correctly
> identifies distinct min and max. I've found out that applying
> glp_scale_prob() beforehand solves my issues. Perhaps my troubles are
> related to the large scale of the numbers involved in my problem
> definitions?

> I've attached the program I used to circumscribe my issues. Sample output is:
>       0: obj =   0.000000000e+00  infeas =  2.179e+12 (0)
> *     4: obj =   7.262668033e+11  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> ======= Min is: 726266803270.283203, status is GOOD
> *     4: obj =   7.262668033e+11  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> ======= Max is: 726266803270.283203, status is GOOD
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  6.470e+11  ratio =  6.470e+11
> GM: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
> EQ: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
> *     4: obj =   7.262668033e+11  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> ======= Min is: 726266803270.283081, status is GOOD
> *     4: obj =   7.262668033e+11  infeas =  0.000e+00 (0)
> *     6: obj =   7.262672503e+11  infeas =  0.000e+00 (0)
> OPTIMAL SOLUTION FOUND
> ======= Max is: 726267250317.839966, status is GOOD

> As you can see, glp_get_status() always reports the solution to be
> optimal even though this is clearly not the case for the first Max
> value. Is this expected behavior?

Glp_get_status just returns the status provided by the simplex solver;
it checks nothing.

Below here the output produced by glp_print_sol for both minimization
and maximization cases:

Problem:
Rows:       7
Columns:    2
Non-zeros:  14
Status:     OPTIMAL
Objective:  7.262668033e+11 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1              B    7.26267e+11                 7.26267e+11 
     2              B    7.26267e+11                 7.26268e+11 
     3              B    7.26268e+11                 7.26268e+11 
     4              NU   7.26278e+11                 7.26278e+11     -0.145096 
     5              B    7.26267e+11   7.26267e+11               
     6              NL   7.26268e+11   7.26268e+11                      1.1451 
     7              B    7.26278e+11   7.26277e+11               

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 a0           B    5.38673e+10                             
     2 a1           B        1.03921             0               

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 1.22e-04 on column 2
        max.rel.err = 8.24e-17 on column 2
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output

Problem:
Rows:       7
Columns:    2
Non-zeros:  14
Status:     OPTIMAL
Objective:  7.262668033e+11 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1              B    7.26267e+11                 7.26267e+11 
     2              B    7.26267e+11                 7.26268e+11 
     3              B    7.26268e+11                 7.26268e+11 
     4              NU   7.26278e+11                 7.26278e+11     -0.145096 
     5              B    7.26267e+11   7.26267e+11               
     6              NL   7.26268e+11   7.26268e+11                      1.1451 
     7              B    7.26278e+11   7.26277e+11               

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 a0           B    5.38673e+10                             
     2 a1           B        1.03921             0               

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 1.22e-04 on column 2
        max.rel.err = 8.24e-17 on column 2
        High quality

KKT.DB: max.abs.err = 1.15e+00 on row 6
        max.rel.err = 1.15e+00 on row 6
        DUAL SOLUTION IS INFEASIBLE

End of output

You can see that in maximization case solution found by the solver is
dual infeasible due to reduced cost of row 6, which is 1.1451; it is
positive while at the optimum it must be non-negative. However, this
reduced cost is relatively very small, because the largest objective
coefficient is of order 1e+10, thus, the relative error in the dual
solution is about 1.1451/1e+10 ~= 1e-10 that can be considered as
a good accuracy which the solver does. May note that in the scaled case
minimal and maximal objective values differ only in 6th decimal place.

Your original lp is badly scaled that causes numerical difficulties,
and scaling helps to resolve this problem.