Re: [eclipse-clp-users] External procedure constraints

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}



-- Joachim