From: Joachim Schimpf <joachim.schimpf_at_monash.edu>

Date: Thu, 31 Mar 2011 16:26:10 +1100

Date: Thu, 31 Mar 2011 16:26:10 +1100

Mick Hallward wrote: > Hi Joachim, > > Many thanks for the detailed answer. > > Let me try to explain why I was thinking about using externals. > > There is a software system, call it S, that tries to > find "good" values for a number of parameters p_1,..,p_n > (mostly integers/reals). To do that, S calls a number > of algorithms A_1,...,A_k with concrete values for the > parameters p_i. It observes what outputs it gets from > each algorithm. Then it tries different values > for p_i, running again the algorithms on the new values; > and so on. It continues randomly "trying" different > values for p_i until the results obtained from the > algorithms are deemed good enough. I intuitively > thought (but might well have been wrong) that it > may be possible to explicitly encode the "logic" > (so to speak) of what constitutes good enough values > for the parameters via proper Eclipse constraints; > and then call in the algorithms dynamically (as > externals) to generate the needed output values. > > Whether or not this would at all speed up the search, > I don't know. There are two notions of cost here: the cost > of running the various algorithms A_j, and the > cost of trying different values for the parameters > by expanding the search tree. It's the latter part > that I thought might be improvable by constraint > search, b/c currently it's done in a willy-nilly > fashion. But maybe I was wrong. From your answer > it seems that using Eclipse+externals would probably > degenerate into a similarly inefficient generate+test > approach. I'll have to think a bit more about it > (any suggestions/feedback would be appreciated). > Thanks again! I haven't understood why you have several algorithms, so I'll assume for the moment that we have only one, and that it computes a function f_g(P1,...Pn)->Cost, and that we are looking for values for the Ps that minimize Cost. To start with, we consider the function as a black box. You can encapsulate this black box function into an ECLiPSe external with n+1 arguments, giving you a predicate g(P1,...,Pn,Cost), which only works if P1,..,Pn are given, and Cost is a result variable. You can then write a generate-and-test program that finds values for for P1,...,Pn that minimize Cost, as follows: :- lib(branch_and_bound). :- lib(ic). solve :- Ps = [P1,...,Pn], Ps :: 0..100, % possible values for the Ps bb_min( (labeling(Ps),g(P1,...,Pn,Cost)), % generate&test Cost, _), printf("An optimal solution with cost %w is %w%n", [Ps, Cost]). This amounts to a generate-and-test solution, since labeling/1 will enumerate all combinations of Ps, and each one will be evaluated by calling g (and have its cost computed). The bb_min wrapper makes sure you get an optimal solution in the end. But once you have this framework, you can start cutting down the search space by adding constraints in the way you were envisaging: you can add any constraints between the Ps and Cost that are _implied_ by the logic of the predicate g. If they are logically implied by g, they do not change the set of possible solutions, i.e. they are logically redundant. However, because they are implemented via active ECLiPSe constraints, they can help cutting down the search space by eliminating values of Pi a priori, which means that less combinations of Ps get enumerated, and consequently g is called less often. The resulting code would then look like: solve :- Ps = [P1,...,Pn], Ps :: 0..100, % possible values for the Ps redundant_g(P1,...,Pn,Cost), bb_min( (labeling(Ps),g(P1,...,Pn,Cost)), Cost, _), printf("An optimal solution with cost %w is %w%n", [Ps, Cost]). The redundant constraints are imposed _before_ search is started, and can consist of any combination of constraints on the variables, e.g. redundant_g(P1,...,Pn,Cost) :- P3 #> P6, P1 #\= P2, Cost #=< sum([P1,...,Pn]), Cost #> 5, alldifferent([P5,P6,P7]). It would be important to include constraints between Ps and Cost, because the branch-and-bound search will look for cheaper and cheaper Costs by imposing an upper bound on Cost, and this upper bound can propagate and reduce the range of values for the Ps, e.g. ?- Ps = [P1, P2, P3], Ps :: 1 .. 10, Cost #= sum(Ps), Cost #< 10. Ps = [P1{1 .. 7}, P2{1 .. 7}, P3{1 .. 7}] Cost = Cost{3 .. 9} -- JoachimReceived on Thu Mar 31 2011 - 05:26:22 CEST

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