How to use Eplex correctly and efficiently in this case.

From: Huy <huy_n_pham_at_yahoo.com>
Date: Wed 16 Feb 2005 04:56:48 PM GMT
Message-ID: <20050216165648.90379.qmail@web20221.mail.yahoo.com>
Hi Everyone,

I would like to ask for your advice on a more specific
problem I am having:

I am writing a program that searchs a decision tree
and makes decision at every choice point by comparing
the the expected reward of each branch. This reward
value is a linear function of several time variables,
and must be optimized (by grounding these time
variables at optimum values).

I include here a small program that resembles what I
did. The problem with this naive program is that it
will choke the linear solver if the tree is large,
because (in my understanding) it keep adding
constraints to the constraint pool without ever remove
them. 

In my specific problem, once the reward values for the
two branches have been compared and the decision has
been made, the rejected branch, along with ALL the
constraints collected during its evaluation, will
never be needed again, and they should be somehow
removed from the pool.

I have been reading the Eplex manual and tutorial, and
kink of understand. But I can not come up with an
efficient solution to this problem Please kindly give
me some advices. I really appreciate.

Thank you very much.

Huy

------Sample query -------------

?- maxValue(Tree, Val, Route).
Tree = tree(1, tree(2, tree(1, void, void), tree(10,
void, void)), tree(5, tree(2, void, void), tree(4,
void, void)))
Val = 13.0
Route = take(1, then, take(2, then, take(10, then,
stop)))
Yes (0.00s cpu)

------ Program ------------------

:-lib(eplex).

% 
% I use the term "tree(Root, Left, Right)" to
represent a tree, with the
% leaf node written as "tree(Root, void, void)". For
example:                
%      
%        2    
%       / \    
%      1   3  
% <==>  tree(2, tree(1, void, void),
%               tree(3, void, void))
%        1
%       / \           tree(1, 
%     2     5	<==>      
tree(2,tree(1,void,void),tree(10,void,void)),
%    / \   / \  	  
tree(5,tree(2,void,void),tree(4,void,void)))
%   1  10 2   4
% 

maxValue(Tree, Value, Direction):-
	Tree = tree(1, 
		     tree(2,tree(1,void,void),tree(10,void,void)),
		     tree(5,tree(2,void,void),tree(4,void,void))),

	eplex: eplex_solver_setup(max(0)),

	bestValFromBestBranch(Tree, Val, Direction),

	eplex: eplex_probe(max(Val), Value),
	eplex: eplex_cleanup.


bestValFromBestBranch(void, Val, Direction):-
	% ...
	% many other linear constraints go here.
	% ...
	eplex: (Val $= 0.0),
	Direction = stop.
	
	
bestValFromBestBranch(tree(Root, Left, Right), Value,
Direction):-

	% find the max value of the left branch
	bestValFromBestBranch(Left, Val1, Direction1),
	eplex: eplex_probe(max(Val1), V1),
	
	% find the max value of the right branch
	bestValFromBestBranch(Right, Val2, Direction2),
	eplex: eplex_probe(max(Val2), V2),
	
	% compare and decide which branch to take
	(V1 >= V2 -> 
		(Value = V1 + Root, Direction = take(Root, then,
Direction1)); 
		(Value = V2 + Root, Direction = take(Root, then,
Direction2))).
	
	














	
		
__________________________________ 
Do you Yahoo!? 
Yahoo! Mail - You care about security. So do we. 
http://promotions.yahoo.com/new_mail
Received on Wed Feb 16 16:59:28 2005

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:34 PM GMT GMT