[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] OPB output file anomaly

From: Andrew Makhorin
Subject: Re: [Help-glpk] OPB output file anomaly
Date: Fri, 29 Feb 2008 23:10:13 +0300

> Using the --wpb flag to glpsol, I am getting an invalid OPB file as
> output.

Did you try specifying the option '--wnpb' to write the instance in
normalized opb format?

In the OPB instruction (see doc/opb.txt) Oscar Gustafsson, who is
the author of the glpk opb module, writes that:

    The routines in GLPK provides a normalized version, conformant
    with the files used in the PB evaluations (see as well as a straightforward
    version with (slightly) higher human readability. There are several
    variations of the OPB-format. Therefore, it is not expected that
    the straightforward output of this routine works with all
    PB-solvers, while the normalized output should work with most.

>   The original input to glpsol is written in mathprog and is
> solved correctly by glpsol, also, for the 0-1 problems in the GLPK
> examples directory all seem to come out fine as OPB files (the ones I
> tried at least--sudoku, todd, and something else) and are solved with
> a PB SAT solver just fine.  The OPB file that is output using my files
> has several lines that look like this:

> <= 15
> <= 15
> <= 12
> etc...

> It is expected that there would be a LHS to these inequalities if
> they are being printed at all.  I looked at glplpx19.c which handles
> the writing of this file.  I added a simple fprintf statement before
> line 136:

> if( k == 0 ) fprintf(fp, "k was zero");

> where k was defined earlier as

> k=glp_get_mat_row(lp, j, ndx, val);

> The result was as expected, for each of the anomalous inequalities
> above I now have lines like this:

> k was zero<=15

> So it looks like I have some rows where all coeff's are zero.  I am
> not sure how to interpret this.  When I manually remove all of these
> inequalities from the OPB file, my PB SAT solver (minisat+) is happy
> with the file, but produces the wrong solution (i.e. different from
> the correct/expected result from glpsol).  So these inequalities are
> probably necessary to obtain the correct solution.

An empty row, i.e. the row having all coefficients zero, can be
either redundant or infeasible only. In your instance all rows look
redundant, so removing them from the instance must not affect the

Probably the opb format does not allow empty rows, so such rows
should not be included in the output file.

> I'm just a little lost as to where to start looking or how to
> interpret what the problem is exactly.  Any insight appreciated.  I'm
> happy to provide more info if it would be helpful.

> Thanks,
> Joey

reply via email to

[Prev in Thread] Current Thread [Next in Thread]