[eclipse-users] Labeling Speed.

  Hi,

Can anybody shed light on this please?
This question relates to "bb_min/3", "search/6" in eclipse.

Background:
-----------

My objective function is the following:

bb_min(search(Vars,0,input_order,indomain_max,complete,[]),Cost,bb_options{timeout:43200}),

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.

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?


Amine.

-- 
Amine Marref
PhD Research Student
Real-Time Systems Group
Department of Computer Science
The University of York
Heslington
YO10 5DD
York
United Kingdom

+44 1904 432810