Re: [eclipse-users] Labeling Speed.

From: Amine Marref <am189_at_york.ac.uk>
Date: Thu, 21 Feb 2008 14:08:25 +0000
Amine Marref wrote:
>   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.
>
>   
Anybody? :'(

-- 
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 
Received on Thu Feb 21 2008 - 14:08:54 CET

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