Re: [rules-users] Drools Planner changing problem fact (2D bin packing with related dimension and continuous values)
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(a)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-tp...
> Sent from the Drools: User forum mailing list archive at Nabble.com.
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet