|
From: Marcin K. <mr...@gm...> - 2009-02-16 14:58:03
|
Hello everyone,
I'm totally new to ECLiPSe, and set out to solving rather silly problem
purely for sake of learning: find a minimum sum of 6 integers, all
different, with each integer belonging to a given range.
:- lib(ic).
:- lib(branch_and_bound).
minsum(X, Range) :-
X = [A,B,C,D,E,F],
X :: 1 .. Range,
integers(X),
alldifferent(X),
bb_min(sum(X,S),S),
labeling(X).
However, I get:
calling an undefined procedure bb_min(sum([_313, _331, _349, _367, _385,
_403], _612), _612) in module eclipse
How come? After all, I do use relevant branch_and_bound library?
Regards,
mk
|
|
From: Wit J. <wit...@gm...> - 2009-02-16 15:05:26
|
2009/2/16 Marcin Krol <mr...@gm...>:
>
> How come? After all, I do use relevant branch_and_bound
I am afraid but there is no bb_min/2 defined.
The min arity is 3. Try to run your code
with bb_min(sum(X,S), S, bb_options{strategy:continue}).
Best regards,
--
[ Wit Jakuczun w.j...@wl... ]
[ WLOG Solutions http://wlogsolutions.com ]
|
|
From: Marcin K. <mr...@gm...> - 2009-02-16 15:16:24
|
Wit Jakuczun wrote:
> I am afraid but there is no bb_min/2 defined.
> The min arity is 3. Try to run your code
> with bb_min(sum(X,S), S, bb_options{strategy:continue}).
Thanks for answer, I figured that out a moment after I sent that mail,
but now I have a different problem:
instantiation fault in +(0, _431{1 .. 9}, _839)
( bb_min(sum(X,S),S,bb_options{strategy:continue}), )
It seems that the list that is being summed is only partially
instantiated, the sum docs say so:
http://eclipse.crosscoreoptimization.com/doc/bips/kernel/arithmetic/sum-2.html
In coroutining mode, if the list is only partly instantiated, the
predicate delays until the list is complete.
According to User Manual I should use 'suspend' library, but it doesn't
help:
:- lib(ic).
:- lib(branch_and_bound).
:- lib(suspend).
minsum(X, Range) :-
X = [A,B,C,D,E,F],
X :: 1 .. Range,
integers(X),
alldifferent(X),
bb_min(sum(X,S),S,bb_options{strategy:continue}),
labeling(X).
I get again instantation fault, or if I specify suspend: directly I get
"calling an undefined procedure suspend":
bb_min(sum(X,S),S,bb_options{strategy:continue}),
Regards,
mk
|
|
From: Wit J. <wit...@gm...> - 2009-02-16 15:25:30
|
2009/2/16 Marcin Krol <mr...@gm...>:
> Wit Jakuczun wrote:
>> I am afraid but there is no bb_min/2 defined.
>> The min arity is 3. Try to run your code
>> with bb_min(sum(X,S), S, bb_options{strategy:continue}).
>
> Thanks for answer, I figured that out a moment after I sent that mail,
> but now I have a different problem:
>
Right! There have been 2 mistakes in your code :).
The correct code should have labeling(X) instead
of sum(X, S) in bb_min predicate and S should be
defined as: S #= sum(X) (this should be added before
bb_min).
Moreover you do not need to use suspend module.
In fact loading it generates an error in my eclipse.
Best regards
--
[ Wit Jakuczun w.j...@wl... ]
[ WLOG Solutions http://wlogsolutions.com ]
|
|
From: Marco G. <mar...@un...> - 2009-02-16 15:59:20
|
Wit Jakuczun wrote:
> 2009/2/16 Marcin Krol <mr...@gm...>:
>> Wit Jakuczun wrote:
>>> I am afraid but there is no bb_min/2 defined.
>>> The min arity is 3. Try to run your code
>>> with bb_min(sum(X,S), S, bb_options{strategy:continue}).
>> Thanks for answer, I figured that out a moment after I sent that mail,
>> but now I have a different problem:
>>
> Right! There have been 2 mistakes in your code :).
>
> The correct code should have labeling(X) instead
> of sum(X, S) in bb_min predicate and S should be
> defined as: S #= sum(X) (this should be added before
> bb_min).
>
> Moreover you do not need to use suspend module.
> In fact loading it generates an error in my eclipse.
I agree with Wit.
The last problem I see in your code is that bb_min requires as argument
a predicate that generates a search tree, such as labeling.
So, your predicate should end like the following:
...
S #= sum(X),
bb_min(labeling(X),S).
Cheers,
Marco
--
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Via Saragat 1 - 44100 Ferrara (Italy)
Tel +39-0532-97-4833
Fax +39-0532-97-4870
http://www.ing.unife.it/docenti/MarcoGavanelli/
|
|
From: Marcin K. <mr...@gm...> - 2009-02-16 16:13:47
|
Marco Gavanelli wrote: > I agree with Wit. > The last problem I see in your code is that bb_min requires as argument > a predicate that generates a search tree, such as labeling. Right... I read the docs example: ?- bb_min(member(X,[9,6,8,4,7,2,4,7]), X, O). Found a solution with cost 9 Found a solution with cost 6 Found a solution with cost 4 Found a solution with cost 2 Found no solution with cost -1.0Inf .. 1 X = 2 O = bb_options(continue, -1.0Inf, 1.0Inf, 1, 1, 0, 0, _, _) yes. ..and I was under impression that I could use any predicate as bb_min's Goal? How do I tell which predicate generates a search tree and which does not? http://eclipse.crosscoreoptimization.com/doc/bips/lib/lists/member-2.html I fail to see how member/2 is different from sum/2 in this regard.. At least the docs do not say so.. > > So, your predicate should end like the following: > > ... > S #= sum(X), > bb_min(labeling(X),S). 1st problem: Thanks to everyone for answers and explanations, but the above generates: calling an undefined procedure _730 #= sum([_431, _449, _467, _485, _503, _521]) in module eclipse This does work, though: :- lib(ic). :- lib(branch_and_bound). :- lib(ic_global). minsum(X, Range) :- X = [A,B,C,D,E,F], X :: 1 .. Range, integers(X), alldifferent(X), sumlist(X,S), bb_min(labeling(X),S,bb_options{strategy:continue}). Found a solution with cost 21 Found no solution with cost 6.0 .. 20.0 Though I'm not really sure why - why does it not work with a normal constraint like S #= sum(X) ? 2nd problem: I see that eclipse generated the first solution and then stopped, unlike typical predicate solving where a user can click "More" if there's another solution. Is there some way to make it look for more solutions? A different strategy, perhaps? The docs say: restart after finding a solution, restart the whole search with the newly found bound imposed on Cost But that doesn't seem to generate more solutions. Does it work like it can only search for another solution if another constraint in form of S < 21 is fulfilled, and since no such solution exists, it stops searching? The docs suggest that: A solution of the goal Goal is found that minimizes the value of Cost. Sorry for all those newbie questions, but I'm *totally* new to Prolog and declarative programming in general.. Regards, mk |
|
From: Kish S. <ki...@ci...> - 2009-02-16 17:54:51
|
Marcin Krol wrote: > ..and I was under impression that I could use any predicate as bb_min's > Goal? How do I tell which predicate generates a search tree and which > does not? > What bb_min/3 actually requires is that you bind Cost within Goal, and the search returns the best (minimal) value of Cost. sum(X,S) will only instantiate S (your cost variable) if X is a ground list of numbers, which it isn't in your program, as you don't have anything that will instantiate the variables in X. If you call bb_min with X as a ground list of numbers, then bb_min/3 will succeed, but it is not very interesting, as there is no real search at all (sum/2 returns only a single answer). What you need for a real search are goals which will produce choices (if you are unfamiliar with this, you should probably read any Prolog textbook), like labeling/1 (there is (normally) more than one way to label your variables) and member/2 (if you have more than one element in your list, then there is more than one member). Cheers, Kish -- This e-mail may contain confidential and privileged material for the sole use of the intended recipient. Any review, use, distribution or disclosure by others is strictly prohibited. If you are not the intended recipient (or authorized to receive for the recipient), please contact the sender by reply e-mail and delete all copies of this message. Cisco Systems Limited (Company Number: 02558939), is registered in England and Wales with its registered office at 1 Callaghan Square, Cardiff, South Glamorgan CF10 5BT. |
|
From: Marco G. <mar...@un...> - 2009-02-17 09:05:59
|
Marcin Krol wrote:
>> So, your predicate should end like the following:
>>
>> ...
>> S #= sum(X),
>> bb_min(labeling(X),S).
>
> 1st problem:
>
> Thanks to everyone for answers and explanations, but the above generates:
>
> calling an undefined procedure _730 #= sum([_431, _449, _467, _485,
> _503, _521]) in module eclipse
The complete program does work:
:- lib(ic).
:- lib(branch_and_bound).
minsum(X, Range) :-
X = [A,B,C,D,E,F],
X :: 1 .. Range,
integers(X),
alldifferent(X),
S #= sum(X),
bb_min(labeling(X),S,_).
[eclipse 2]: minsum(X,7).
lists.eco loaded traceable 0 bytes in 0.02 seconds
Found a solution with cost 21
Found no solution with cost 6.0 .. 20.0
X = [1, 2, 3, 4, 5, 6]
Yes (0.05s cpu)
Cheers,
Marco
--
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Via Saragat 1 - 44100 Ferrara (Italy)
Tel +39-0532-97-4833
Fax +39-0532-97-4870
http://www.ing.unife.it/docenti/MarcoGavanelli/
|
|
From: Thorsten W. <tho...@we...> - 2009-02-16 15:51:02
|
Marcin Krol schrieb:
> Wit Jakuczun wrote:
>
>> I am afraid but there is no bb_min/2 defined.
>> The min arity is 3. Try to run your code
>> with bb_min(sum(X,S), S, bb_options{strategy:continue}).
>>
>
> Thanks for answer, I figured that out a moment after I sent that mail,
> but now I have a different problem:
>
> instantiation fault in +(0, _431{1 .. 9}, _839)
>
>
> ( bb_min(sum(X,S),S,bb_options{strategy:continue}), )
>
sum/2 sums up the (ground) expressions in list X. What you want is the
*constraint* sumlist/2.
Also, bb_min searches for a minimal solution in a search tree, as
defined by a search goal.
sum(X,S) is not a search goal. Neither would be sumlist(X,S).
labeling(X) is a search goal.
So your code should read:
[...]
sumlist(X, S),
bb_min(labeling(X), S, bb_options{strategy:continue}).
Cf. bb_min/3 help:
bb_min(+Goal, ?Cost, ?Options)
Find a minimal solution using the branch-and-bound method
Arguments
Goal The (nondeterministic) search goal
Cost A (usually numeric domain) variable representing
the cost
Options A bb_options structure or variable
Cheers,
Thorsten
|