[gecode-users] Fwd: Problem with splitting Problem
Mohamed Rezgui
kyo.alone at gmail.com
Wed Mar 27 10:39:45 CET 2013
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130327/2b9cc77b/attachment.html>
More information about the users
mailing list