From: Amine Marref <am189_at_york.ac.uk>

Date: Thu, 21 Feb 2008 14:08:25 +0000

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 432810Received 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
*