Re: [Help-glpk] Row duals, unexpected values

[Andrew Makhorin]

> I think this question is likely rooted in a lack of understanding
> on my part, so any explanation is appreciated.  The question has to
> do with row dual values.

> Here is a small LP in CPLEX format:


> Minimize
>  obj: + y_1 + y_2

> Subject To
>  Con1: - y_1 + 1 lambda_2_0 + 24 lambda_0_0 + 43 lambda_1_0 = 64
>  Con2: + y_2 + 3 lambda_2_0 + 26 lambda_0_0 + 30 lambda_1_0 = 63
>  sub1_convexity: + lambda_0_0 = 1
>  sub2_convexity: + lambda_1_0 = 1
>  sub3_convexity: + lambda_2_0 = 1

> Bounds
>  0 <= lambda_1_0 <= 1
>  0 <= lambda_0_0 <= 1
>  0 <= lambda_2_0 <= 1

> End


> Now, there are five vars and five constraints (all linearly
> independent), so the basis matrix is the entire constraint matrix,
> correct?

No. Due to degeneracy some equality constraints may be inactive in the
optimal basis. See the solver output below.

> Assuming I am right about that, if I calculate the row dual values by the 
> formula:

> c'*inv(B) or inv(B)'*c

> I get (-1 1 -2 13 -2) for the row dual vector.

> When I run this code:

> int main() {
>     
>     int i;
>     glp_prob* lp = lpx_read_cpxlp(MY_CPLEX_PROB);
>     glp_smcp* simplex_control_params = (glp_smcp*) malloc(sizeof(glp_smcp));
>     glp_init_smcp(simplex_control_params);
>     simplex_control_params->presolve = GLP_OFF;
>     glp_simplex(lp, simplex_control_params);
>     
>     for( i = 1; i <= glp_get_num_cols(lp); i++ ) {
>         printf("Col %d (%s) has primal value %3.4f\n", i,
> glp_get_col_name(lp, i), glp_get_col_prim(lp, i));
>     }
>     
>     for( i = 1; i <= glp_get_num_rows(lp); i++ ) {
>         printf("Row %d has dual value %3.1f\n", i, glp_get_row_dual(lp, i));
>     }
>     
>     return 0;
> }

> I get the following output:

> lpx_read_cpxlp: reading problem data from `pre_master.cpxlp'...
> lpx_read_cpxlp: 5 rows, 5 columns, 11 non-zeros
> lpx_read_cpxlp: 18 lines were read
>       0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
>       6:   objval =   8.000000000e+00   infeas =   0.000000000e+00 (3)
> *     6:   objval =   8.000000000e+00   infeas =   0.000000000e+00 (3)
> *     7:   objval =   8.000000000e+00   infeas =   0.000000000e+00 (2)
> OPTIMAL SOLUTION FOUND
> Col 1 (y_1) has primal value 4.0000
> Col 2 (y_2) has primal value 4.0000
> Col 3 (lambda_2_0) has primal value 1.0000
> Col 4 (lambda_0_0) has primal value 1.0000
> Col 5 (lambda_1_0) has primal value 1.0000
> Row 1 has dual value -1.0
> Row 2 has dual value 1.0
> Row 3 has dual value 0.0
> Row 4 has dual value 13.0
> Row 5 has dual value 0.0


> So with all of the ugly details out of the way, why am I getting
> a discrepancy in the Row 3 and Row 5 dual values?  I understand that
> one can get different dual values in general if a different basis is
> used, but there is only one choice of basis here, right?

> I'd be happy to provide any additional information if it is
> helpful.  I am using a slightly modified GLPK 4.28 (I had to replace
> the memory management).

Your lp instance has multiple optimal bases. In your case the solver
found an optimal basis where some equality constraints are inactive
due to degeneracy. I could not obtain the same basic solution, however,
I found another, where constraint sub3_convexity is inactive:

Problem:
Rows:       5
Columns:    5
Non-zeros:  11
Status:     OPTIMAL
Objective:  obj = 8 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 Con1         NS            64            64             =            -1
     2 Con2         NS            63            63             =             1
     3 sub1_convexity
                    NS             1             1             =            -2
     4 sub2_convexity
                    NS             1             1             =            13
     5 sub3_convexity
                    B              1             1             = 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 y_1          B              4             0               
     2 y_2          B              4             0               
     3 lambda_2_0   NU             1             0             1            -2
     4 lambda_0_0   B              1             0             1 
     5 lambda_1_0   B              1             0             1 

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 2.81e-16 on row 4
        max.rel.err. = 5.06e-17 on row 4
        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. = 2.71e-15 on column 1
        max.rel.err. = 1.27e-15 on column 5
        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