Sorry, I forget about it. I choose the same search (lexicographic order) for all subproblems and for the entire problem. I used it for optimality proof. and I have the same thing. I verify all subproblems are distinct.
That's my result with the optimality proof (obj = 11 so I set at obj-1): ENTIRE_PROBLEM : =====UNSATISFIABLE===== %% instance: sugiyama2_g5_7_7_7_7_2.fzn %% search: Gecode::INT_VAR_NONE(), Gecode::INT_VAL_MIN() %% add ub: 10 %% runtime: 330.538 (330538 ms) %% solvetime: 330.507 (330507 ms) %% status: UNSAT %% objective: -1 %% decision variables: 32 %% variables: 791 %% propagators: 837 %% propagations: 1610969243 %% nodes: 12386891 %% failures: 6193446 DECOMPOSITION_PROBLEM AND SOLVE ALL SUBPROBLEMS GENERATED: =====UNSATISFIABLE===== %% instance: sugiyama2_g5_7_7_7_7_2.fzn %% search: Gecode::INT_VAR_NONE(), Gecode::INT_VAL_MIN() %% add ub: 10 %% runtime: 833.92 (833920 ms) %% status: UNSAT %% objective: -1 %% decision variables: 32 %% variables: 791 %% propagators: 837 %% propagations: 3715375322 %% nodes: 31124812 %% failures: 15563406 %% time decomposition: 0.471 (471 ms) %% nodes decomposition: 0 %% failures decomposition: 0 %% sum time problems: 833.404 (833404 ms) %% min time problems: 0 (0 ms) %% max time problems: 2.611 (2611 ms) %% problems decomposition: 2000 Best Regards, Mohammed REZGUI 2013/3/27 Christian Schulte <cschu...@kth.se> > 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
