From: Joachim Schimpf <joachim.schimpf_at_monash.edu>

Date: Thu, 02 Sep 2010 01:11:48 +1000

Date: Thu, 02 Sep 2010 01:11:48 +1000

Jacky wrote: > Hi there, > > I am new to ECLiPSe, but trying to learn it recently. I got a weird > question when executing my own ecl program. The code is to find the list > "Rounds" that gives the smallest "Cost". > > If I keep the time constraint "E #< D" there, and let eclipse to find > the best solution from the domain [18..80], it seems to be working well. > But if I assign value to each variable in the list (like the assignments > in the code), then the program seems to be stuck somewhere. But some > assignment combinations will work, e.g. 18, 18, 18, 18. This is really > strange to me, so I'm wondering whether anyone could tell me where the > code is wrong, or why it happens for some combinations. > > Thanks in advance. I've attached the code with this email. Sorry for > disturbing. > > Regards, > Jacky Hi Jacky, You only have a solution when ALL variables are instantiated. Variables are sometimes instantiated implicitly by the constraints, but in general you have to guarantee instantiation by passing ALL your variables to a search routine. Your code only searches the 'Round' variables. As I said in an earlier mail, it is always a good idea to start your experiments without using bb_min/3 or minimize/2. Remove it from your code, and see whether the resulting search program generates reasonable solutions. I modified your code as follows (I also added some printing of the result tasks): ... search(Rounds, 0, first_fail, indomain, complete, []), ( foreach(task{start:S,duration:D},Tasks) do writeln(task(S,D)) ), ... When you run this, you get the following result: ?- solve(X). task(_396{0 .. 6}, 0) task(_450{0 .. 6}, 22) task(_1085{95 .. 101}, 16) ... task(_774{202 .. 208}, 36) task(_1409{239 .. 245}, 36) _558{294 .. 300} -12.6__-12.6 [18, 18, 18, 18] X = -12.6__-12.599999999999996 There are 47 delayed goals. Do you want to see them? (y/n) As you can see, the Start-variables of the tasks are not instantiated, and there are lots of "delayed goals", which means constraints that are not yet decidable. So you have to add a search over the Start-variables: ... search(Rounds, 0, first_fail, indomain, complete, []), search(Starts, 0, smallest, indomain_split, complete, []), ... Often it may be better to put all variables into a single list, and use a single search/6 call. In this case I have simply added a second call to search/6, which isn't bad because that allows me to use a different search strategy for the start-time variables (label the early start times first, which is usually a good idea). With this change we get: [eclipse 62]: solve(X). task(0, 0) task(0, 22) task(95, 16) ... task(202, 36) task(239, 36) 294 -12.6__-12.6 [18, 18, 18, 18] X = -12.6__-12.599999999999996 Delayed goals: This is a real solution, and the system will generate alternative ones on backtracking. [There are still some "delayed goals", but they do not contain variables, and are result from floating point uncertainties which you can ignore here]. Now you can add back the minimization: bb_min( ( search(Rounds, 0, first_fail, indomain, complete, []), search(Starts, 0, smallest, indomain_split, complete, []) ), Cost, bb_options{strategy: continue, delta: 0.01}), which now gives the following solution: [eclipse 64]: solve(X). Found a solution with cost -12.6__-12.599999999999996 Found a solution with cost -12.690192378864669__-12.690192378864666 Found a solution with cost -12.780384757729339__-12.780384757729335 Found a solution with cost -12.870577136594006__-12.870577136594003 Found a solution with cost -12.960769515458674__-12.96076951545867 Found a solution with cost -13.050961894323343__-13.050961894323338 Found a solution with cost -13.141154273188011__-13.141154273188008 Found a solution with cost -13.231346652052681__-13.231346652052677 Found a solution with cost -13.321539030917348__-13.321539030917345 Found a solution with cost -13.411731409782016__-13.411731409782012 Found a solution with cost -13.501923788646687__-13.50192378864668 Found a solution with cost -13.592116167511353__-13.592116167511348 Found a solution with cost -13.682308546376023__-13.682308546376017 Found a solution with cost -13.772500925240694__-13.772500925240687 Found no solution with cost -18.2 .. -13.782500925240686 task(0, 0) task(0, 22) task(95, 16) task(235, 7) task(184, 18) task(278, 19) task(297, 0) task(0, 0) task(58, 1) task(146, 1) task(147, 1) task(238, 1) task(242, 0) task(297, 0) task(22, 36) task(59, 36) task(58, 88) task(147, 88) task(111, 36) task(148, 36) task(202, 36) task(242, 36) 297 -13.7725009252407__-13.7725009252407 [18, 44, 18, 18] X = -13.772500925240694__-13.772500925240687 -- JoachimReceived on Wed Sep 01 2010 - 15:11:54 CEST

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*