[gecode-users] Fwd: Problem with splitting Problem
Christian Schulte
cschulte at kth.se
Wed Mar 27 10:19:17 CET 2013
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/f9af2960/attachment-0001.html>
More information about the users
mailing list