[gecode-users] Fwd: Problem with splitting Problem

[Mohamed Rezgui]

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>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130322/ca0aafa5/attachment.html>