[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Constraint solver generates invalid solutions
|
From: |
Markus Triska |
|
Subject: |
Re: Constraint solver generates invalid solutions |
|
Date: |
Wed, 02 Mar 2011 22:49:47 +0100 |
Hi Daniel,
thank you! I can shorten the time it takes to produce a wrong solution
to a few minutes if I change the
DATE++;
to
DATE += 10000;
I hope this works for you as well and helps you to fix possible
overflows in both cases.
Thank you and all the best,
Markus
Daniel Diaz <address@hidden> writes:
> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
> <html>
> <head>
> <meta content="text/html; charset=ISO-8859-1"
> http-equiv="Content-Type">
> </head>
> <body text="#000000" bgcolor="#ffffff">
> Markus,<br>
> <br>
> 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.<br>
> I use such 2 counters (called STAMP and DATE). On STAMP I only test
> equality (== or !=) so I suspect much more the DATE counter.<br>
> Both are really used in src/EngineFD/fd_inst.c.<br>
> <br>
> I propose you to try the following: get the last version at:<br>
> <br>
> <a
>
> href="http://gprolog.univ-paris1.fr/unstable/gprolog-20101130.tgz";>http://gprolog.univ-paris1.fr/unstable/gprolog-20101130.tgz</a><br>
> <br>
> It remains compatible with your code (you only have to comment
> nth0/3 predicate which is now provided as built-in).<br>
> You can keep your current version (1.3.0) installed.<br>
> <br>
> Uncompress it and go to src/EngineFD<br>
> Then modify fd_inst:c: 786 by adding this a test after DATE++ (this
> gives you):<br>
> <br>
> <tt> DATE++;<br>
> if (DATE < 0)<br>
> DATE = 1;<br>
> </tt><br>
> then in the src directory:<br>
> <br>
> ./configure<br>
> make<br>
> <br>
> You don't need to do a 'make install'. You can simply type (under
> bash):<br>
> <br>
> . SETVARS<br>
> <br>
> (NB don't forget the leading dot . before SETVARS)<br>
> <br>
> Then you can cd in the directory where your fd_decompose.pl resides
> and type:<br>
> <br>
> gplc fd_decompose.pl<br>
> <br>
> it should be compiled with the modified version.<br>
> <br>
> Execute it to see if it is better (you will have to wait 2 more
> weeks I suppose).<br>
> <br>
> <br>
> If this does not work, please try, in addition, to deselect an optim
> at fd_inst:1102<br>
> there is a #if 1, please change it by #if 0. You code should look
> like:<br>
> <br>
> <tt>#if 0 <---- 0 HERE !!!<br>
> /* optim #2 */<br>
> pdate = (unsigned long *)
> Optim_Pointer(CF);<br>
> if (*pdate < date)<br>
> continue;<br>
> #endif<br>
> </tt><br>
> After this modification, go to the src directory and:<br>
> <br>
> make clean<br>
> make<br>
> <br>
> To test it:<br>
> . SETVARS<br>
> <br>
> and as before to re-do the gplc.<br>
> <br>
> Please keep me informed about the results of these tests.<br>
> <br>
> Sorry to not be able to help you much more Markus.<br>
> <br>
> Daniel<br>
> <br>
> <br>
> <br>
> <br>
> Le 18/02/2011 19:38, Markus Triska a écrit :
> <blockquote cite="mid:address@hidden" type="cite">
> <pre wrap="">
> 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</pre>
> </blockquote>
> <br>
> <blockquote cite="mid:address@hidden" type="cite">
> <pre wrap="">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
>
>
> </pre>
> <pre wrap="">
> <fieldset class="mimeAttachmentHeader"></fieldset>
> _______________________________________________
> Bug-prolog mailing list
> <a class="moz-txt-link-abbreviated"
> href="mailto:address@hidden";>address@hidden</a>
> <a class="moz-txt-link-freetext"
> href="http://lists.gnu.org/mailman/listinfo/bug-prolog";>http://lists.gnu.org/mailman/listinfo/bug-prolog</a>
> </pre>
> </blockquote>
> <br>
> </body>
> <br>--
> <br>Ce message a été vérifié par
> <a href="http://www.mailscanner.info/";>MailScanner</a>
> pour des virus ou des polluriels et rien de
> suspect n'a été trouvé.
> </html>