[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Row duals, unexpected values
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Row duals, unexpected values |
Date: |
Thu, 23 Oct 2008 07:15:00 +0300 |
> 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