Re: Constraint solver generates invalid solutions

[Daniel Diaz]

Markus,

I have tried to reproduce this bug but I can't (except maybe waiting 2 weeks). I'd suspect a counter overflows after such a long period.
I use such 2 counters (called STAMP and DATE). On STAMP I only test equality (== or !=) so I suspect much more the DATE counter.
Both are really used in src/EngineFD/fd_inst.c.

I propose you to try the following: get the last version at:

http://gprolog.univ-paris1.fr/unstable/gprolog-20101130.tgz

It remains compatible with your code (you only have to comment nth0/3 predicate which is now provided as built-in).
You can keep your current version (1.3.0) installed.

Uncompress it and go to src/EngineFD
Then modify fd_inst:c: 786 by adding this a test after DATE++ (this gives you):

  DATE++;
  if (DATE < 0)
    DATE = 1;

then in the src directory:

   ./configure
   make

You don't need to do a 'make install'. You can simply type (under bash):

   . SETVARS

(NB don't forget the leading dot . before SETVARS)

Then you can cd in the directory where your fd_decompose.pl resides and type:

   gplc fd_decompose.pl

it should be compiled with the modified version.

Execute it to see if it is better (you will have to wait 2 more weeks I suppose).


If this does not work, please try, in addition, to deselect an optim at fd_inst:1102
there is a #if 1, please change it by #if 0. You code should look like:

#if 0   <---- 0 HERE !!!
        /* optim #2 */
        pdate = (unsigned long *) Optim_Pointer(CF);
        if (*pdate < date)
          continue;
#endif

After this modification, go to the src directory and:

  make clean
  make

To test it:
  . SETVARS
 
and as before to re-do the gplc.

Please keep me informed about the results of these tests.

Sorry to not be able to help you much more Markus.

Daniel




Le 18/02/2011 19:38, Markus Triska a écrit :

On a 2009 iMac (2.66 Intel Core 2 Duo, 4 GB RAM) with OSX 10.5.8,
gprolog 1.3.1 produces invalid solutions (that is, they do not satisfy
all posted constraints) to a finite domain constraint problem, as you
can verify with the attached programs.

The first program, fd_decompose.pl, solves a certain combinatorial
problem (it enumerates all supersimple 16-4-2 designs that are
decomposable, that is, each of them is the union of two 16-4-1 designs;
"supersimple" means that every two blocks share at most two points). The
second program, fd_decompose_verify.pl, is almost identical to the first
program, except that it does not generate solutions, but rea

them from
standard input and uses the exact same constraint formulation to check
whether the solution (is ground and) satisfies all constraints; a simple
counter displays how many solutions were already read and checked.

Compile both programs as usual with "gplc fd_decompose.pl" and "gplc
fd_decompose_verify.pl", and then use them together with:

   $ ./fd_decompose | ./fd_decompose_verify

The first few generated solutions are all valid:

   0 1 2 3 4  ...

but, after about 2 weeks of computation time, I get an invalid one:

   ... 22218 22219 wrong - ([[0, 1, 5, 14], [0, 2, 8, 13], [0, 3, 7,
   11], [0, 4, 9, 12], [0, 6, 10, 15], [1, 2, 4, 6], [1, 3, 8, 9], [1,
   7, 10, 12], [1, 11, 13, 15], [2, 3, 5, 12], [2, 7, 9, 15], [2, 10,
   11, 14], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3,
   4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6]] - [[0, 1, 7, 9],
   [0, 2, 12, 14], [0, 3, 5, 15], [0, 4, 6, 8], [0, 10, 11, 13], [1, 2,
   10, 15], [1, 3, 4, 13], [1, 5, 8, 12], [1, 6, 11, 14], [2, 3, 7, 8],
   [2, 4, 9, 11], [2, 5, 6, 13], [3, 6, 10, 12], [3, 5, 7, 10], [3, 5,
   7, 10], [3, 5, 7, 10], [3, 5, 7, 10], [3, 5, 7, 10], [3, 5, 7, 10],
   [3, 5, 7, 14]]).

Please let me know if you need any further information.

Thank you and all the best,
Markus

_______________________________________________
Bug-prolog mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/bug-prolog

--
Ce message a été vérifié par MailScanner pour des virus ou des polluriels et rien de suspect n'a été trouvé.