Re: [Bug-glpk] Difference, 32bit build - 64bit build

[Christoph Cullmann]

On Wednesday 24 September 2008 21:34:40 Andrew Makhorin wrote:
> > I have a difference with solving a larger problem on 32bit and 64bit
>> ...
> > Any ideas, what this might cause?
> > Interesting sidenote: the debian shipped glpsol, version 4.16 works on
> > both 32bit and 64bit linux systems with same sane result.
> >
> > The input LP is attached, CPLEX format. Any advice welcome :)
>
> Thank you for your report.
>
> The glpk mip solver indicates that the problem has no integer feasible
> solution because lp relaxation of the root subproblem is almost primal
> infeasible; more precisely, the dual simplex which is used to solve
> lp relaxations cannot choose non-basic variable to keep the current
> basis dual feasible within a tolerance, so it concludes that there
> is no primal feasible solution to the lp relaxation. This, of course,
> happens because the glpk dual simplex is still not as sufficiently
> robust as the primal simplex.
>
> On the other hand, I should say that your problem is badly formulated:
> there are used unbounded integer variables, and most of them have large
> values in the optimal solution to lp relaxation. When I introduced upper
> bound 1e8 for all integer variables in your instance:
>
> \ Lower Bounds
> Bounds
> xe49 <= 1e8
> xf8e <= 1e8
> x1d67 <= 1e8
> x1be4 <= 1e8
> x155b <= 1e8
> . . .
>
> I could solve it with 32-bit glpsol 4.31:
Hmm, interesting. Will take a look into our generator for the ILPs, if we can 
create such upper bounds. Thank you a lot for the fast 
feedback :)
Will forward your answer to my co-developers.

>
> glp_read_lp: reading problem data from `value_15318949093.lp'...
> glp_read_lp: 1015 rows, 1577 columns, 3513 non-zeros
> glp_read_lp: 1577 integer columns, none of which are binary
> glp_read_lp: 2949 lines were read
> glp_simplex: original LP has 1015 rows, 1577 columns, 3513 non-zeros
> glp_simplex: presolved LP has 942 rows, 1320 columns, 3072 non-zeros
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  6.000e+00  ratio =  6.000e+00
> Problem data seem to be well scaled
> Crashing...
> Size of triangular part = 896
>       0: obj =   1.877000000e+03  infeas =  2.400e+01 (46)
> *     3: obj =   1.877000000e+03  infeas =  0.000e+00 (46)
> *   200: obj =   1.399802172e+10  infeas =  0.000e+00 (0)
> *   400: obj =   1.525441700e+10  infeas =  0.000e+00 (0)
> *   478: obj =   1.531894909e+10  infeas =  1.552e-10 (0)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> +   478: mip =     not found yet <=              +inf        (1; 0)
> +   478: >>>>>   1.531894909e+10 <=   1.531894909e+10   0.0% (1; 0)
> +   478: mip =   1.531894909e+10 <=     tree is empty   0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used:   0.7 secs
> Memory used: 1.3 Mb (1357527 bytes)
>
> As to 64-bit version and glpsol 4.16, it was just a happy chance due
> to small differences caused by round-off errors, and insignificant
> changes in the problem data mought cause the same error.
Ok, sounds reasonable, thought so myself already, but wanted some feedback,
thanks for confirming my guess.

Btw., just tried using lpx_intopt instead of lpx_simplex + lpx_integer,
I get optimal results on both platforms again.

Therefor question, after reading the glpk docu bit more, changed our glpk 
driver a bit:

Is this code safe to solve a MIP (sorry, perhaps that is already out of scope 
for bug-glpk, just
didn't want to open new thread on help-glpk):
(to understand code, eprintf just printf alike)

    // read lp...
    LPX *lp = lpx_read_cpxlp (in_filename);
    if (!lp)
        eprintf (C_TAG_FATAL, 0, "cannot open '%s', CPLEX LP file processing 
error", in_filename);

   /**
     * this is a integer problem...
     */
    switch (lpx_intopt (lp))
    {
        // OK
        case LPX_E_OK:
            break;

        // infeasible
        case LPX_E_NOFEAS:
        case LPX_E_NOPFS:
        case LPX_E_NODFS:
            eprintf (C_TAG_ERROR, 0, "this problem is infeasible or unbounded");
            writeEmptyOutput();
            exit (EXIT_SUCCESS);
            break;

        // uh oh...
        default:
            eprintf (C_TAG_FATAL, 0, "no optimal solution found, solving 
failed");
            break;
    }

    /**
     * status.....
     */
    switch (glp_mip_status (lp))
    {
        // optimal
        case GLP_OPT:
            deprintf (C_TAG_INFO, 0, "optimal solution found");
            break;

        // infeasible
        case GLP_INFEAS:
            eprintf (C_TAG_ERROR, 0, "this problem is infeasible");
            writeEmptyOutput();
            exit (EXIT_SUCCESS);
            break;

        // no feasible
        case GLP_NOFEAS:
            eprintf (C_TAG_ERROR, 0, "this problem has no feasible solution");
            writeEmptyOutput();
            exit (EXIT_SUCCESS);
            break;

        // unbounded
        case GLP_UNBND:
            eprintf (C_TAG_ERROR, 0, "this problem is unbounded");
            writeEmptyOutput();
            exit (EXIT_SUCCESS);
            break;

        // uh oh...
        default:
            eprintf (C_TAG_FATAL, 0, "no optimal solution found, solving 
failed");
            break;
    }

    // try to open output filename
    FILE *output = fopen (out_filename, "wt");
    if (!output)
        eprintf (C_TAG_FATAL, 0, "cannot open output file '%s'", out_filename);

    /**
     * objective function
     */
    double objVal = glp_mip_obj_val (lp);
    deprintf (C_TAG_INFO, 0, "value of objective function: "REALFORMAT, objVal);
    fprintf (output, "Value of objective function: " REALFORMAT "\n", objVal);

    /* var values... */
    for (int col = 1; col <= glp_get_num_cols (lp); ++col)
    {
        const char *colName = glp_get_col_name (lp, col);
        double vx = glp_mip_col_val (lp, col);

        if (!colName)
        {
            fclose (output);
            eprintf (C_TAG_FATAL, 0, "column %d without name in result", col);
        }

        fprintf (output, "%-20s " REALFORMAT "\n", colName, vx);
    }

    // close file...
    fclose (output);

cu
Christoph

-- 
-------------------------------------- Christoph Cullmann ---------
AbsInt Angewandte Informatik GmbH      Email: address@hidden
Science Park 1                         Tel:   +49-681-38360-22
66123 Saarbrücken                      Fax:   +49-681-38360-20
GERMANY                                WWW:   http://www.AbsInt.com
--------------------------------------------------------------------
Geschäftsführung: Dr.-Ing. Christian Ferdinand
Eingetragen im Handelsregister des Amtsgerichts Saarbrücken, HRB 11234