[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Finding minimum and maximum objective value
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Finding minimum and maximum objective value |
Date: |
Mon, 23 Nov 2009 20:40:03 +0300 |
> 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.