[Help-glpk] Row duals, unexpected values

Hi all,

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?

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).

Thanks in advance.

From:	Joey Rios
Subject:	[Help-glpk] Row duals, unexpected values
Date:	Wed, 22 Oct 2008 19:37:37 -0700