[gecode-users] Cutting holes within a view optimally
Zaremby, David
david.zaremby at lmco.com
Wed Apr 14 23:09:43 CEST 2010
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:zayenz at gmail.com]
Sent: Wednesday, April 14, 2010 1:01 AM
To: Zaremby, David
Cc: cschulte at kth.se; users at gecode.org
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 <david.zaremby at lmco.com<mailto:david.zaremby at lmco.com>>
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:cschulte at kth.se<mailto:cschulte at kth.se>]
Sent: Tuesday, April 13, 2010 2:11 PM
To: Zaremby, David; users at gecode.org<mailto:users at gecode.org>
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: users-bounces at gecode.org<mailto:users-bounces at gecode.org> [mailto:users-bounces at gecode.org<mailto:users-bounces at gecode.org>] On Behalf Of Zaremby, David
Sent: Tuesday, April 13, 2010 7:34 PM
To: users at gecode.org<mailto:users at gecode.org> 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
users at gecode.org<mailto:users at gecode.org>
https://www.gecode.org/mailman/listinfo/gecode-users
--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100414/ebc524bc/attachment-0001.htm>
More information about the users
mailing list