Re: [eclipse-clp-users] Bin Packing implementation issues

From: Kish Shen <kisshen_at_cisco.com>
Date: Mon, 18 Jul 2011 21:28:25 +0100
Hi,

I am probably not the best person to answer your question, but as there 
have not been any other reply to your message, I will try...

On 12/07/2011 19:31, Naman Agarwal wrote:
> Its a huge mail and a compliccated query so I request the reader to please
> read on with patience.
>

I have not looked at your code in any detail, so I don't really 
understand it -- this is one reason I delayed my answer until now.

> Also there is a strange error that I face which is the following.
> ....
> Now, observing when the backtrack happens i see the following - that lets
> say i give as input 50 objects to be placed on 50 vms over 90 time intervals
>
>
> now it goes fine till the first 40 objects and since these essentially
> placed in a first fit format, 7 objects are observed to be used til now
>
> however while placing the 41st object, it shows the first backtrack, which
> is strange as it says it is not able top place object 41
> on bin 7 but the constraints dissatisfy and a backtrack happens. Now such a
> backtrack is not expected because if it cannot be placed on this bin
> then by domain reduction placing should anyways not happen. Even if it was
> to happen i would have observed the first backtrack before the 41st object
> when the 2nd bin was going to be used.
>

I don't understand your explanation of why you think there should not be 
any backtracks.

By "if it cannot be placed on this bin then by domain reduction placing 
should anyways not happen.", do you mean you think that any inconsistent 
values (inconsistent with all the constraints you have posted) in the 
variables you are lablling (placing object 41, I guess) will be removed 
by "domain reduction", before you label it with a value?

This is in general not the case, both because

1) ic does local consistency reasoning (i.e. consistency reasoning is 
done per constrain),

2) for the consistency reasoning for each constraint, the only 
requirement is that consistent values should not be removed. Removing 
all inconsistent values is often too expensive to achieve, so this is
often not done.

Cheers,

Kish


> Now I believe that it is either a malfunctioning of the domain reduction
> because i have really huge equations with reified constraints or there is
> something missing in my understanding. Could you help me out with this. I
> hope i could convey the problem ..
>
> thanks a lot in advance !!!
>
>
>
>
> ------------------------------------------------------------------------------
> AppSumo Presents a FREE Video for the SourceForge Community by Eric
> Ries, the creator of the Lean Startup Methodology on "Lean Startup
> Secrets Revealed." This video shows you how to validate your ideas,
> optimize your ideas and identify your business strategy.
> http://p.sf.net/sfu/appsumosfdev2dev
>
>
>
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users


-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.
Received on Mon Jul 18 2011 - 20:28:37 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET