[gecode-users] Problem with splitting Problem
Guido Tack
tack at gecode.org
Wed Mar 27 10:57:13 CET 2013
I couldn't find the attachment in the original mail so I can't verify this, but could you explain the difference between "decision variables" and "variables"? Are "decision variables" the ones you mention in the int_search annotation, and "variables" all variables in the model?
If that is the case, then the problem could be that the search strategy on the 791-32=759 remaining variables is dynamic (it uses AFC-based search). The search tree of a smaller problem is therefore not necessarily smaller. You could try to add more int_search annotations with static strategies to the FlatZinc so that all variables are covered and see if that changes the behaviour.
Cheers,
Guido
On 27/03/2013, at 20:39 , Mohamed Rezgui <kyo.alone at gmail.com> wrote:
> 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 <cschulte at 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.alone at gmail.com]
> Sent: Wednesday, March 27, 2013 9:06 AM
> To: cschulte at kth.se
> Cc: users at 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 <cschulte at 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-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Mohamed Rezgui
> Sent: Friday, March 22, 2013 5:30 PM
> To: users at 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 at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
--
Guido Tack,
http://www.csse.monash.edu/~guidot/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130327/f6121d17/attachment-0001.html>
More information about the users
mailing list