From: Amine Marref <am189_at_york.ac.uk>

Date: Tue, 19 Feb 2008 14:13:11 +0000

Date: Tue, 19 Feb 2008 14:13:11 +0000

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 432810Received on Tue Feb 19 2008 - 14:13:52 CET

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