[gecode-users] Fwd: Problem with splitting Problem

[Christian Schulte]

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>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130322/922f6771/attachment.html>