Yes, please understand how branch and bound search works: there is no guarantee that the decompositions need the same amount of search!
C -- Christian Schulte, Professor of Computer Science, KTH, www.ict.kth.se/~cschulte/ From: Mohamed Rezgui [mailto:kyo.al...@gmail.com] Sent: Wednesday, March 27, 2013 9:06 AM To: cschu...@kth.se Cc: users@gecode.org Subject: Re: [gecode-users] Fwd: Problem with splitting Problem Thank you four your answer, I correct it with choosing only first variable for decomposition . But when I decomposed the problem into either 80 or 400, or 1000 or 2000 sub problems and I resolve them (one after another and best solution is applied when it is found for the next subproblem) I got 3 times more nodes and 3 times more failures with the same code in my previous message !!! Can you help me about this problem please. Best Regards, Mohammed REZGUI 2013/3/22 Christian Schulte <cschu...@kth.se> You might want to look at how much search is needed, just check the statistics. The decomposition does not guarantee that you will use less search. Christian -- Christian Schulte, www.ict.kth.se/~cschulte/ From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Mohamed Rezgui Sent: Friday, March 22, 2013 5:30 PM To: users@gecode.org Subject: [gecode-users] Fwd: Problem with splitting Problem Dear everybody, I have a problem with Gecode 4.0.0 (see the code below) I can exhibit the issue on the following example I solve an optimization problem in the format flatzinc "sugiyama2_g5_7_7_7_7_2.fzn" (it is attached). It takes 370s. Then I cut the problem in two disjoint sub-problems P1 and P2 (Two Spaces) P1 is P with (x3=1, x5=2, x30=30, x31=29) and P2 is P with (x3=1, x5=2, x30=29, x31=30) First, I solve P1. This found a solution with a cost C1. Then I solve P2 and add the cost constraint cost <C1 (ie constraint(c1) in gecode)) The issue is that P1 is solved in 355 seconds and P2 in 329 seconds ! The sum is 685s where the initial resolution takes 370s I expected to have something close to 370s It seems that I have no problem if I add constraint on the first variables (x0, x1,.) and that it does not work if I use any variables (like here x3,x5,x30.) Thanks in advance for any remark Best Regards, Mohammed REZGUI Here is my code: <code> //Init fg with sugiyama2_g5_7_7_7_7_2.fzn instance FlatZincSpace* fg = FlatZinc::parse(...) fg->createBranchers(...) fg->shrinkArray(...) //vars_index[3, 5, 30, 31, ] => variables have the minimum doman size in this problem // it is fine If I use 4 first variables but it is not interesting for me // //best solution used for P2 after Space* best = NULL; { FlatZincSpace* p1 = static_cast<MyFlatZincSpace*>(fg->clone(false)); //vars_index[3, 5, 30, 31, ] //tuple_val[1, 2, 29, 30, ] Gecode::rel(*p1, p1->iv[3], Gecode::IRT_EQ, 1); Gecode::rel(*p1, p1->iv[5], Gecode::IRT_EQ, 2); Gecode::rel(*p1, p1->iv[30], Gecode::IRT_EQ, 29); Gecode::rel(*p1, p1->iv[31], Gecode::IRT_EQ, 30); Gecode::Search::Options opt; opt.threads = 1.0; Gecode::Search::Sequential::BAB bab(p1, sizeof(MyFlatZincSpace), opt); Gecode::Space* s = bab.next(); while(s) { delete best; best = s; engine().solution(this); s = bab.next(); } } { FlatZincSpace* p2 = static_cast<MyFlatZincSpace*>(fg->clone(false)); //vars_index[3, 5, 30, 31, ] //tuple_val[1, 2, 30, 29, ] Gecode::rel(*p2, p2->iv[3], Gecode::IRT_EQ, 1); Gecode::rel(*p2, p2->iv[5], Gecode::IRT_EQ, 2); Gecode::rel(*p2, p2->iv[30], Gecode::IRT_EQ, 30); Gecode::rel(*p2, p2->iv[31], Gecode::IRT_EQ, 29); if (best) { p2->constrain(*best); } Gecode::Search::Options opt; opt.threads = 1.0; Gecode::Search::Sequential::BAB bab(p2, sizeof(MyFlatZincSpace), opt); Gecode::Space* s = bab.next(); while(s) { delete best; best = s; engine().solution(this); s = bab.next(); } } </code> -- Cordialement, Mohamed REZGUI
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
