[gecode-users] Fwd: Problem with splitting Problem

[Mohamed Rezgui]

2013/3/27 Mohamed Rezgui <kyo.alone at 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 <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
>>
>


-- 
Cordialement,
Mohamed REZGUI
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130327/8f982b14/attachment-0001.html>