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

[Benjamin Poirier]

Andrew Makhorin wrote:
>> I am currently using glpk. Thank you for the good documentation, the
>> "Brief example" in section 1.3.1 really helped me to start using the
>> library quickly. I have a question however. I would like to find both
>> the minimum and the maximum objective value for the same objective
>> function, constraints and bounds. I have tried:
> 
>> [...]
>> glp_set_obj_dir(lp, GLP_MIN);
>> glp_simplex(lp, NULL);
>> min= glp_get_obj_val(lp);
>> glp_set_obj_dir(lp, GLP_MAX);
>> glp_simplex(lp, NULL);
>> max= glp_get_obj_val(lp);
> 
>> but then max == min. Is there something that I have to clear/reset after
>> changing obj_dir before solving again?
> 
> You need to check the solution status after a call to glp_simplex.
> The solution is optimal if glp_get_status returns GLP_OPT. Or print
> the solution to a file with glp_print_sol. Most likely in the second
> case your lp is unbounded, i.e. has no finite maximum.

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?

-Ben

min-max.c
Description: Text Data