Re: [eclipse-users] Labeling Speed.

Amine Marref wrote:
>   Hi,
> 
> Can anybody shed light on this please?
> This question relates to "bb_min/3", "search/6" in eclipse.

You have not explained how your abstract problem relates to this.


> 
> Background:
> -----------
> 
> My objective function is the following:
> 
> bb_min(search(Vars,0,input_order,indomain_max,complete,[]),Cost,bb_options{timeout:43200}),

This is your search code, not an objective function.
An objdective function would be something like
Cost #= ......


> 
> where Vars are the variables I want to label (integers) and Cost is the 
> cost I try to minimize.
> 
> Let CP be the constraint pool in the model (the set of all constraints).
> 
> CP = (c_1 /\ c_2 /\ ... /\ c_k) /\ (c_k+1 /\ c_k+2 /\ ... /\ c_n) (k <= n)
> 
> There are n constraints.
> The first k constraints c_1..c_k are expressed solely using =, <, =<, >=, >
> e.g. c_1 = (x > 7), i.e. c_1..c_k do not contain conjunction or 
> disjunction. I call these atomic constraints.

This subproblem can be solved without search, i.e. just by stating
the constraints, let them propagate, and then picking any values
from the remaining variable domains.


> 
> The constraints c_k+1..c_n are disjunctions
> e.g. c_54 = (x1 > 8) \/ (x2 < 9)
> for simplicity let's assume each of c_k+1..c_n is a binary-disjunction 
> of atomic constraints.
> 
> Thoughts:
> --------
> Let CP = C1  /\ C2 where
> C1 = (c_1 /\ c_2 /\ ... /\ c_k)
> C2 = (c_k+1 /\ c_k+2 /\ ... /\ c_n)
> each c_i with i in k+1..n is a binary disjunction as we assumed previously
> Consider the following example of C2:
> C2 = (c1 \/ c2) /\ (c3 \/ c4) /\ (c5 \/ c6)
> 
> Let's solve the current problem using the 8 combinations of disjuncts in C2:
> CP = C1 /\ (c1 /\ c3 /\ c5)
> CP = C1 /\ (c1 /\ c3 /\ c6)
> CP = C1 /\ (c1 /\ c4 /\ c5)
> CP = C1 /\ (c1 /\ c4 /\ c6)
> CP = C1 /\ (c2 /\ c3 /\ c5)
> CP = C1 /\ (c2 /\ c3 /\ c6)
> CP = C1 /\ (c2 /\ c4 /\ c5)
> CP = C1 /\ (c2 /\ c4 /\ c6)
> 
> We solve 8 different instances of the model, than take the minimal 
> solution of them, let it be S1.
> 
> Let's solve the model using CP = C1 /\ C2 (i.e. with disjunctions), let 
> the solution be S2.
> 
> I *think* S1 = S2.
> 
> Question:
> ---------
> If my thinking is right, will we find -in general- solution S2 faster 
> than S1 because C1 (assume C1 is huge) is satisfied 8 times in finding 
> S1? Or will they take similar time given S2 considers larger ranges of 
> variables in one go?

You have described your problem in an abstract, declarative way.
 From that, it is impossible to say anything about how efficiently
it solves.  It depends on how you exactly implement the constraints,
in particular, how you actually write the disjunctions in ECLiPSe,
and how you write the search goal.  You haven't shown us.

There are different ways of doing the disjunctions.  Let's look at
the two obvious ones: via search, or via reified constraints.
(Another options is lib(propia), but let's forget about that for now).

The first rule is that all code that has no search goes before the bb_min,
and the code that contains search goes inside the bb_min.  So if we
implement the disjunctions with search, it goes inside bb_min, i.e.

     solve :-
	setup_C1(Vars),
	bb_min((
		search_C2(Vars),
		search(Vars,...)
		), Cost, Options).

     search_C2(Vars) :-
	( c1(Vars) ; c2(Vars) ),
	( c3(Vars) ; c4(Vars) ),
	( c5(Vars) ; c6(Vars) ).

The disadvantage here is that the search strategy is inflexible: we
will always start with the choice between c1 and c2, then c3 and c4,
then c5 and c6, then chose between different values for the variables.

A usually better way to implement the disjunctions is with reified
constraints.  The setup then goes before the bb_min:

     solve :-
	setup_C1(Vars),
	setup_C2(Vars),
	bb_min((
		search(Vars,...)
		), Cost, Options).

     setup_C2(Vars) :-
	( c1(Vars) or c2(Vars) ),
	( c3(Vars) or c4(Vars) ),
	( c5(Vars) or c6(Vars) ).

The search is then again purely on variables, and the disjunctions
get decided when enough information is available.

If you need more control over searching the disjunctions, you can
associate Booleans with them, and decide by labeling the Boolean
which branch of the disjunctions gets chosen:

     solve :-
	setup_C1(Vars),
	setup_C2(Vars, Bools),
	append(Bools, Vars, AllVars),
	bb_min((
		search(AllVars,...)
		), Cost, Options).

     setup_C2(Vars, [B1,B2,B3]) :-
	or(c1(Vars), c2(Vars), B1),
	or(c3(Vars), c4(Vars), B2),
	or(c5(Vars), c6(Vars), B3).


Btw, none of these alternatives will need to solve the C1 constraints
more than once.

Hope this helps,
-- Joachim