[rules-users] Drools Planner changing problem fact (2D bin packing with related dimension and continuous values)

[Geoffrey De Smet]

Good point Wolfgang,
If the use case allows (or even demands) for discretizing the locations 
and putting in on a grid, that should definitely be done.

For example, putting cargo on an airplane is also a bin packing problem,
but because the cargo items need to be attached to the airplane,
so there's a grid on the airplane floor with specific points where the 
cargo item can be attached too.


But even if the use case doesn't allow for discretizing the locations,
it is still not as continuous as it looks:
since every item always leans against another item or the side,
it's far more efficient to look for order of the items.
> I like the idea with the getPrevious(X/Y)Item from a combinatorial point of
> view, but practially it doesn´t work because you can have more than one
> previous item (bigger one has 2 smaller ones to the left/above) and vice
> versa, which will let the combinations also explode.
Yes, but I still believe in this approach.
The number of combinations is far less then any n^n formula where n is 
the size of max double, float, long or integer.
Basically, this approach discretizes it, but not as handy.

Op 20-06-12 16:48, Wolfgang Laun schreef:
> I don't know anything about Planner, so pardon me if this isn't helping any.
>
> Allocating rectangles into a bigger rectangle could be discretised,
> provided the dimensions have a certain granularity. This means that
> you have a gridded "arena", from which you allocate certain grid
> subsets for the "cuts".
>
> There are some well known techniques for representing gridded areas,
> and the corresponding geospatial functions are quite efficient.
>
> I surmise that Planner constraints can be formulated based on a
> gridded approach, but (see 1st sentence) I wouldn't know how.
>
> -W
>
> PS: From some research done ~30 years ago I have a vague recollection
> that the 2D cutting stock problem is a well trodden area. Google
> produces some newer results as well.
>
>
>
> On 20/06/2012, Ralph S.<ralphschwitalla at me.com>  wrote:
>> Hi Geoffrey,
>> thanks for the answer.
>> I like the idea with the getPrevious(X/Y)Item from a combinatorial point of
>> view, but practially it doesn´t work because you can have more than one
>> previous item (bigger one has 2 smaller ones to the left/above) and vice
>> versa, which will let the combinations also explode.
>>
>> I still like to implement an online Guillotine algorithm (cut the remaining
>> space and do an heuristic search on the possible results) in drools if it´s
>> possible.  Therefore i still have no idea how to handle the dynamically
>> changing list of free spaces.
>>
>> Greetings
>> Ralph
>>
>> --
>> View this message in context:
>> http://drools.46999.n3.nabble.com/Drools-Planner-changing-problem-fact-tp4018087p4018101.html
>> Sent from the Drools: User forum mailing list archive at Nabble.com.
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>

-- 
With kind regards,
Geoffrey De Smet