Re: [Help-glpk] Incorrect solution via library interface

[Uday Reddy]

I now notice that this could be due to a floating-point rounding /
tolerance issue. The constraint being violated is:

-c_4 -1001c_5             +1002001c_9     >= 1

and thus c_9 being close to zero might satisfy the constraint although
rounding c_9 off to zero will lead to an incorrect solution. It looks
like glpsol by default sets the precision/tolerance to something
different and obtains the solution that works for me here - I have to
just set it the same way in my library code.

~ Uday





On Sat, Jan 17, 2015 at 8:43 PM, Uday Reddy <address@hidden> wrote:
> I have glpk-4.52.1-2.fc20.x86_64. For the attached ILP, when using
> glpk as a library with a simple interfacing code (also attached), I
> get an incorrect all zero solution (2nd and 4th constraints from the
> bottom are violated).
>
> ----------------------------------------------------------------------------------------------------
> $ gcc unit_test_glpk.c -lglpk -lm
> $ ./a.out
> Reading problem data from 'test.cplex'...
> 32 rows, 11 columns, 62 non-zeros
> 11 integer variables, 2 of which are binary
> 62 lines were read
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  1.002e+06  ratio =  1.002e+06
> GM: min|aij| =  1.778e-01  max|aij| =  5.625e+00  ratio =  3.164e+01
> EQ: min|aij| =  3.161e-02  max|aij| =  1.000e+00  ratio =  3.164e+01
> Constructing initial basis...
> Size of triangular part is 32
> GLPK Simplex Optimizer, v4.52
> 32 rows, 11 columns, 62 non-zeros
> Preprocessing...
> 14 rows, 8 columns, 44 non-zeros
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  1.002e+06  ratio =  1.002e+06
> GM: min|aij| =  1.778e-01  max|aij| =  5.625e+00  ratio =  3.164e+01
> EQ: min|aij| =  3.161e-02  max|aij| =  1.000e+00  ratio =  3.164e+01
> Constructing initial basis...
> Size of triangular part is 14
>       0: obj =  -3.000000000e+03  infeas =  5.602e+03 (0)
> *     6: obj =   1.502550000e+04  infeas =  0.000e+00 (0)
> *    11: obj =  -1.110482799e-32  infeas =  5.136e-34 (0)
> OPTIMAL LP SOLUTION FOUND
> GLPK Integer Optimizer, v4.52
> 32 rows, 11 columns, 62 non-zeros
> 11 integer variables, 2 of which are binary
> Integer optimization begins...
> +    11: mip =     not found yet >=              -inf        (1; 0)
> +    11: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
> +    11: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> z = 0.000000
> c0 = 0, c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0, c7 = 0, c8 =
> 0, c9 = 0, c10 = 0,
> --------------------------------------------------------------------------------------------------
>
> However, with the standalone tool, I get the right one.
>
> glpsol --lp test.cplex -o sol
>
> cat sol
> [...]
>    No. Column name       Activity     Lower bound   Upper bound
> ------ ------------    ------------- ------------- -------------
>      1 c_0          *              1             0
>      2 c_1          *              0             0
>      3 c_2          *              0             0
>      4 c_3          *              1             0             3
>      5 c_4          *             -1         -1000          1000
>      6 c_5          *              0         -1000          1000
>      7 c_6          *              0             0          1000
>      8 c_7          *              0             0          1000
>      9 c_8          *              0             0
>     10 c_9          *              0             0             1
>     11 c_10         *              0             0             1
>
> Anything wrong with this simple library interface?
>
> Thanks.
>
>
>     glp_prob *lp = glp_create_prob();
>
>     glp_read_lp(lp, NULL, "test.cplex");
>
>     glp_smcp parm;
>     glp_init_smcp(&parm);
>     parm.presolve = GLP_ON;
>
>     glp_scale_prob(lp, GLP_SF_AUTO);
>     glp_adv_basis(lp, 0);
>     glp_simplex(lp, &parm);
>
>     int lp_status = glp_get_status(lp);
>
>     if (lp_status == GLP_NOFEAS) {
>         glp_delete_prob(lp);
>         return 1;
>     }
>
>     glp_intopt(lp, NULL);
>
>     int ilp_status = glp_mip_status(lp);
>
>     if (ilp_status == GLP_NOFEAS) {
>         glp_delete_prob(lp);
>         return 1;
>     }
>
>     double z = glp_mip_obj_val(lp);
>     printf("z = %lf\n", z);
>
>     for (j=0; j<glp_get_num_cols(lp); j++) {
>         double x = glp_mip_col_val(lp, j+1);
>         printf("c%d = %lld, ", j, (int64) round(x));
>     }
>     printf("\n");;
>     glp_delete_prob(lp);