Prolog - minimize

Author

minimize_maximum

jucabika

2007-02-02, 4:03 am

Hi to All,
I was trying to solve one job-shop scheduling problem writen in the If-
Prolog. I am using BProlog.
The problem is that BProlog doesn't have predicate
"minimize_maximum(+Goal, ?List)"
This predicate minimize the maximum value of the elements of
List which satisfies Goal. A successful proof of Goal must instantiate
the elements of List
with integers. IF/Prolog attempts to prove the Goal using the branch-
and-bound method
in such a way as to further minimize the maximum value for the list
elements. Once one
solution has been found, the Goal is reactivated with the additional
constraint that the next
solution must be better than the previous one. This process is
repeated until no better solution

Someone has an idea how to do the same in BProlog?

Thorsten Kiefer

2007-02-03, 7:05 pm

Hi,
can you give an example for the usage of minimize_maximum(+Goal, ?List) ?

Maye something like that :
minimize_maximum(Goal,_) :-
oldlist(OldList),
max(OldList,OldMax),
apply(Goal,[NewList]),
max(NewList,NewMax),
NewMax < OldMax,
retract(oldlist(OldList)),
assert(oldlist(NewList)),false.
minimize_maximum(Goal,List) :-
oldlist(List),
retract(oldlist(List)),
!.
minimize_maximum(Goal,List) :-
assert(oldlist([100000000])),!,
minimize_maximum(Goal,List),!.

I'm not sure !!

jucabika wrote:

> Hi to All,
> I was trying to solve one job-shop scheduling problem writen in the If-
> Prolog. I am using BProlog.
> The problem is that BProlog doesn't have predicate
> "minimize_maximum(+Goal, ?List)"
> This predicate minimize the maximum value of the elements of
> List which satisfies Goal. A successful proof of Goal must instantiate
> the elements of List
> with integers. IF/Prolog attempts to prove the Goal using the branch-
> and-bound method
> in such a way as to further minimize the maximum value for the list
> elements. Once one
> solution has been found, the Goal is reactivated with the additional
> constraint that the next
> solution must be better than the previous one. This process is
> repeated until no better solution
>
> Someone has an idea how to do the same in BProlog?

jucabika

2007-02-05, 8:03 am

On Feb 4, 2:01 am, Thorsten Kiefer <toki...@usenet.cnntp.org> wrote:[color=darkred]
> Hi,
> can you give an example for the usage of minimize_maximum(+Goal, ?List) ?
>
> Maye something like that :
> minimize_maximum(Goal,_) :-
> oldlist(OldList),
> max(OldList,OldMax),
> apply(Goal,[NewList]),
> max(NewList,NewMax),
> NewMax < OldMax,
> retract(oldlist(OldList)),
> assert(oldlist(NewList)),false.
> minimize_maximum(Goal,List) :-
> oldlist(List),
> retract(oldlist(List)),
> !.
> minimize_maximum(Goal,List) :-
> assert(oldlist([100000000])),!,
> minimize_maximum(Goal,List),!.
>
> I'm not sure !!
>
> jucabika wrote:
>

Many thanks Thorsten!
As I understand, what you have written is a branch-and-bound mechanism
Am I right?
Here is original example in If-Prolog which I want to adjust to
BProlog

program:-
Jobs=[Ja,Jb,Jc,Jd],
O1_Task=[Ta1,Tb2,Td1],
O2_Task=[Ta2,Tb1,Tb3,Tc,Td2],
O1_Dur=[Da1,Db2,Dd1],
O2_Dur=[Da2,Db1,Db3,Dc,Dd2],
O1_Dur=[2,3,5],
O2_Dur=[6,5,3,4,2],
R1=[1,1,1],
R2=[1,1,1,1,1],
append(O1_Task,O2_Task,Tasks),
append(O1_Dur,O2_Dur,Durations),
Tasks in 0..100,
Jobs in 0..100,
Ta2#>=Ta1 + Da1,
Tb2#>=Tb1 + Db1,
Td2#>=Td1 + Dd1,
Tb3#>=Tb2 + Db2,
Ja#=Ta2 + Da2,
Jb#=Tb3 + Db3,
Jc#=Tc + Dc,
Jd#=Td2 + Dd2,
cumulative(O1_Task,O1_Dur,R1,1),
cumulative(O2_Task,O2_Dur,R2,2),
minimize_maximum(labelingff(Tasks),Jobs)
,
print(Tasks,Durations,Jobs).

Regards

Thorsten Kiefer

2007-02-05, 7:04 pm

> Many thanks Thorsten!
No Problem.

> As I understand, what you have written is a branch-and-bound mechanism
> Am I right?
I don't know the exact term, but you are probably right.

> Here is original example in If-Prolog which I want to adjust to
> BProlog
>
> program:-
> Jobs=[Ja,Jb,Jc,Jd],
> O1_Task=[Ta1,Tb2,Td1],
> O2_Task=[Ta2,Tb1,Tb3,Tc,Td2],
> O1_Dur=[Da1,Db2,Dd1],
> O2_Dur=[Da2,Db1,Db3,Dc,Dd2],
> O1_Dur=[2,3,5],
> O2_Dur=[6,5,3,4,2],
> R1=[1,1,1],
> R2=[1,1,1,1,1],
> append(O1_Task,O2_Task,Tasks),
> append(O1_Dur,O2_Dur,Durations),
> Tasks in 0..100,
> Jobs in 0..100,
> Ta2#>=Ta1 + Da1,
> Tb2#>=Tb1 + Db1,
> Td2#>=Td1 + Dd1,
> Tb3#>=Tb2 + Db2,
> Ja#=Ta2 + Da2,
> Jb#=Tb3 + Db3,
> Jc#=Tc + Dc,
> Jd#=Td2 + Dd2,
> cumulative(O1_Task,O1_Dur,R1,1),
> cumulative(O2_Task,O2_Dur,R2,2),
> minimize_maximum(labelingff(Tasks),Jobs)
,
> print(Tasks,Durations,Jobs).
>
> Regards
It seems like you want to do "task-scheduling" in Prolog, right?
Be aware that this problem is NP-complete.
And my "solver" is the "worst-case" method of solving an NP-complete problem,
as it really tries out every possible combination.
You should find an algorithm which is specialized for your problem, or which finds
a "suboptimal" solution.
Such approximation algorithms are normally polynomial.
If you should find a general form of minimize_maximum, which is polynomial,
then DON'T TELL ANYONE, because you could make an assfull of money !!!!!!!

Regrads
Thorsten

Marco Gavanelli

2007-02-07, 8:04 am

jucabika wrote:
> Hi to All,
> I was trying to solve one job-shop scheduling problem writen in the If-
> Prolog. I am using BProlog.
> The problem is that BProlog doesn't have predicate
> "minimize_maximum(+Goal, ?List)"
> This predicate minimize the maximum value of the elements of
> List which satisfies Goal. A successful proof of Goal must instantiate
> the elements of List
> with integers. IF/Prolog attempts to prove the Goal using the branch-
> and-bound method
> in such a way as to further minimize the maximum value for the list
> elements. Once one
> solution has been found, the Goal is reactivated with the additional
> constraint that the next
> solution must be better than the previous one. This process is
> repeated until no better solution
>
> Someone has an idea how to do the same in BProlog?
>

I am not familiar with B-Prolog, but from the manual I see that they
have a B&B already implemented:

http://www.cad.mse.kyutech.ac.jp/pe...ual/node55.html

In CLP(FD) languages you often have a maxlist constraint. So, you could
implement minimize_maximum as follows:

minimize_maximum(Goal,List):-
maxlist(List,Max),
minof(Goal,Max).

So, if maxlist is not available in B-Prolog you can implement it. A very
simple implementation could be the following:

maxlist([],_).
maxlist([H|T],Max):-
H #=< Max,
maxlist(T,Max).

Note that this implementation does not impose that Max is actually the
maximum of the list, but simply constrains all elements of the list to
be smaller than Max, which should suffice for your needs.

Cheers,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Neng-Fa Zhou

2007-02-07, 7:05 pm

>> Marco wrote:
> minimize_maximum(Goal,List):-
> maxlist(List,Max),
> minof(Goal,Max).
>
> So, if maxlist is not available in B-Prolog you can implement it. A very
> simple implementation could be the following:
>
> maxlist([],_).
> maxlist([H|T],Max):-
> H #=< Max,
> maxlist(T,Max).
>
> Note that this implementation does not impose that Max is actually the
> maximum of the list, but simply constrains all elements of the list to be
> smaller than Max, which should suffice for your needs.

As max(L), where L is a list of variables or integers, is allowed in
expressions in B-Prolog, you could implement minimize_maximum/2 simply as:

minimize_maximum(Goal,List):-
Max #= max(List),
minof(Goal,Max).

BTW, your implementation is incomplete; Max must be equal to at least one of
the elements in the list.

Cheers,
Neng-Fa

jucabika

2007-02-07, 7:05 pm

On 7 feb, 17:02, "Neng-Fa Zhou" <n...@acm.org> wrote:
>
>
>
>
> As max(L), where L is a list of variables or integers, is allowed in
> expressions in B-Prolog, you could implement minimize_maximum/2 simply as:
>
> minimize_maximum(Goal,List):-
> Max #= max(List),
> minof(Goal,Max).
>
> BTW, your implementation is incomplete; Max must be equal to at least one of
> the elements in the list.
>
> Cheers,
> Neng-Fa- Ocultar texto de la cita -
>
> - Mostrar texto de la cita -

Thak you all for the valuable advices. Finaly it works!!!

Marco Gavanelli

2007-02-15, 4:14 am

Neng-Fa Zhou wrote:
> As max(L), where L is a list of variables or integers, is allowed in
> expressions in B-Prolog, you could implement minimize_maximum/2 simply as:
>
> minimize_maximum(Goal,List):-
> Max #= max(List),
> minof(Goal,Max).

That's a very nice syntax for the maximum constraint!

> BTW, your implementation is incomplete; Max must be equal to at least one of
> the elements in the list.

Indeed, that's what I was meaning with:
[color=darkred]
to be[color=darkred]

Cheers,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Sponsored Links