2013/3/27 Mohamed Rezgui <kyo.al...@gmail.com> > 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 >> >
-- Cordialement, Mohamed REZGUI
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
