Mikael,
Nice insight. Thank you for taking the time to analyze the issue beyond the
stated question. Originally I didn't think that I needed this case, but it
turned out I did because it sometimes allowed domains to be available that were
actually forbidden and resulted in a larger search tree when branching and even
worse, when assigning, it incorrectly resulted in a dead tree. I would have
struggled without this nugget of knowledge. I think an improved version is
provided below. Let me know if I misinterpreted your use case.
virtual ExecStatus propagate(Space& home, const ModEventDelta& med)
{
if (Int::IntView::me(med) == Int::ME_INT_BND)
{
if (x1.max() - x0.min() < offset1)
{
Iter::Ranges::Singleton r0(x0.min(), x1.min() + offset1
- 1);
GECODE_ME_CHECK(x0.minus_r(home, r0, false));
}
if (x0.max() - x1.min() < offset0)
{
Iter::Ranges::Singleton r1(x1.min(), x0.min() + offset0
- 1);
GECODE_ME_CHECK(x1.minus_r(home, r1, false));
}
}
else if (Int::IntView::me(med) == Int::ME_INT_VAL)
{
if (x0.assigned())
{
Iter::Ranges::Singleton r0(x0.val() - offset1 + 1 >= 0
? x0.val() - offset1 + 1 : 0, x0.val() + offset0 - 1);
GECODE_ME_CHECK(x1.minus_r(home, r0, false));
}
else if (x1.assigned())
{
Iter::Ranges::Singleton r1(x1.val() - offset0 + 1 >= 0
? x1.val() - offset0 + 1 : 0, x1.val() + offset1 - 1);
GECODE_ME_CHECK(x0.minus_r(home, r1, false));
}
}
if (x0.max() + offset0 <= x1.min() || x1.max() + offset1 <=
x0.min())
return home.ES_SUBSUMED(*this);
else
return ES_FIX;
}
Thanks,
David Zaremby
Senior Software Engineer
LSS / Strategic Products
Lockheed Martin Simulation, Training & Support
12506 Lake Underhill Road, MP-823
Orlando, FL 32825
From: Mikael Zayenz Lagerkvist [mailto:[email protected]]
Sent: Wednesday, April 14, 2010 1:01 AM
To: Zaremby, David
Cc: [email protected]; [email protected]
Subject: Re: [gecode-users] Cutting holes within a view optimally
Just as a side-note, you can do propagation earlier than when a variable is
fixed for this constraint. In the ground case, an offset1 of 5 and a value v of
x0 gives a forbidden region
[-----v-----]
for the variable x1. If the difference between min (a) and max (b) of a
non-ground x0 is less than offset1, then all potential forbidden regions will
overlap. Consider the case where b-a=3
[-----a---[==]---b-----]
The doubly marked values are forbidden for x1 regardless of the final value of
x0.
Whether modifying the propagation helps for solving your problem is another
issue of course.
Cheers,
Mikael
2010/4/13 Zaremby, David <[email protected]<mailto:[email protected]>>
Thanks. That did the trick. I knew it was easy. I just couldn't seem to find
it...
virtual ExecStatus propagate(Space& home, const ModEventDelta&) {
if (x0.assigned())
{
Iter::Ranges::Singleton r0(x0.val() - offset1 > 0 ? x0.val()
- offset1 : 0, x0.val() + offset0);
GECODE_ME_CHECK(x1.minus_r(home, r0, false));
}
else if (x1.assigned())
{
Iter::Ranges::Singleton r1(x1.val() - offset0 > 0 ? x1.val()
- offset0 : 0, x1.val() + offset1);
GECODE_ME_CHECK(x0.minus_r(home, r1, false));
}
if (x0.max() + offset0 < x1.min() || x1.max() + offset1 < x0.min())
return home.ES_SUBSUMED(*this);
else
return ES_FIX;
}
David Zaremby
Senior Software Engineer
LSS / Strategic Products
Lockheed Martin Simulation, Training & Support
12506 Lake Underhill Road, MP-823
Orlando, FL 32825
From: Christian Schulte [mailto:[email protected]<mailto:[email protected]>]
Sent: Tuesday, April 13, 2010 2:11 PM
To: Zaremby, David; [email protected]<mailto:[email protected]>
Subject: RE: [gecode-users] Cutting holes within a view optimally
Check the minus_r member function and the range iterator
Iter::Ranges::Singleton
The latter allows to specify a single range.
That should do the trick!
Cheers
Christian
--
Christian Schulte, web.ict.kth.se/~cschulte/<http://web.ict.kth.se/~cschulte/>
From: [email protected]<mailto:[email protected]>
[mailto:[email protected]<mailto:[email protected]>] On Behalf Of
Zaremby, David
Sent: Tuesday, April 13, 2010 7:34 PM
To: [email protected]<mailto:[email protected]> gecode
Subject: [gecode-users] Cutting holes within a view optimally
Gecoders,
I am struggling with finding the best way to cut a hole in a view during
propegation without doing a simple for loop. I originally thought I should use
a Range and Iterator and execute the minus_v method, but I can't find an easy
way to construct one easily using specific values other than using a value
array of ints but I would still need a loop to initialize the array. What is
the best way to do this with the least computation?
The end goal of this propagator is to put a gap between two domains however
there is no guarantee that x0 < x1 so you really can't reduce much on the
domain until one is assigned a start. Additionally you can't use an offset view
because you only want the offset to apply if the task is the earlier one one.
virtual ExecStatus propagate(Space& home, const ModEventDelta&) {
if (x0.assigned())
{
//create a range that x1 cant equal over (x0.val - offset1,
x0.val + offset0)
for (int i = x0.val() - offset1; i < x0.val() + offset0; ++i)
{
GECODE_ME_CHECK(x1.nq(home, i));
}
}
else if (x1.assigned())
{
//create a range that x0 cant equal over (x1.val - offset0,
x1.val + offset1)
for (int i = x1.val() - offset0; i < x1.val() + offset1; ++i)
{
GECODE_ME_CHECK(x0.nq(home, i));
}
}
if (x0.max() + offset0 <= x1.min() || x1.max() + offset1 <=
x0.min())
return home.ES_SUBSUMED(*this);
else
return ES_FIX;
}
David Zaremby
Senior Software Engineer
LSS / Strategic Products
Lockheed Martin Simulation, Training & Support
12506 Lake Underhill Road, MP-823
Orlando, FL 32825
_______________________________________________
Gecode users mailing list
[email protected]<mailto:[email protected]>
https://www.gecode.org/mailman/listinfo/gecode-users
--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
