[gecode-users] Cutting holes within a view optimally
Mikael Zayenz Lagerkvist
zayenz at gmail.com
Thu Apr 15 06:17:19 CEST 2010
Hi,
I'm think you could do something even simpler, since the two cases could be
merged. Note that when x0 is assigned, x0.val() == x0.min() == x0.max().
Thus the two cases could be merged into something like
if (x0.max() - x0.min() < offset1) {
Iter::Ranges::Singleton r0(std::max(x0.max() - ofset1 + 1, 0),
x0.min()+offset1-1);
GECODE_ME_CHECK(x1.minus_r(home, r0, false));
}
and similarly for the reverse case. I assumed that x0.min()+offset1-1 is
never negative. I haven't tested the code, so it might be incorrect.
Also, note the in your code you don't use the special 0-absorbing logic for
the bounds-reasoning, which is probably wrong.
Returning ES_FIX is probably wrong now, since you might modify the bounds of
x0 in the second part, and need to re-run since x1 could be modified again.
I haven't thought about it in depth though.
Cheers,
Mikael
On Wed, Apr 14, 2010 at 11:09 PM, Zaremby, David <david.zaremby at lmco.com>wrote:
> 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>
>
> 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]
> *Sent:* Tuesday, April 13, 2010 2:11 PM
> *To:* Zaremby, David; 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/
>
>
>
> *From:* 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 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
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>
>
>
> --
> Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
>
--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100415/26ef37b5/attachment-0001.htm>
More information about the users
mailing list