Drools Planner changing problem fact

[Ralph S.]

Hi all,
i am new to drools planner and try to model a 2dimensional rectangle packing problem.
I have some problems modelling the problem facts because one of them (the list of free spaces) is constantly
changing.

For example I have a list of rectangles (length,width) I try to pack on a fixed size layer (length, width). The list of rectangles is fixed.
But the list of free space is dynamic (first you have the whole layer as free space,
then you cut out the space occupied by the first rectangle which gives you 3 remaining free spaces, and so on)

All the examples in the drools-planner-examples seem to have a fixed list of problem facts (rooms, teachers, timeslots) which only should be combined optimally.

How can a dynamic number of one(or more) problem fact be modelled?

Greetings Ralph

[ge0ffrey]

Continuous value ranges aren't (fully) supported yet,
but you could use @ValueRange type=UNDEFINED
and implement a MoveFactory that creates a move to a random double value
from that continuous space.
But that probably won't work, as it would often leave space between items
and the search space would be too big (doubleSize² to the power itemSize).


Instead, you 'd just really just like to specify the order of the items
on a specific axis,
where the location is the sum of the width of the items with a lower order.
For example, if itemA.getXIndex() = 3 then itemA.getX() = items[xIndex
== 0].getX() + items[xIndex == 1].getX() + items[xIndex == 2].getX()
That works fine for 1 axis or independent axis, leaving no space between
2 items,
but how does one deal with multiple related axis?

I have a few theories for this, but I haven't worked out a good example yet.
They are all based on the idea that if you can translate item ordering
(xIndex, yIndex) into item location (x, y) in your score function,
then you can easily check the hard constraints (no overlapping items)
and soft constraints (leave 5 cm of space between 2 items) in the score
function too.

One way is to just specify after which item an item comes, for each axis.
itemA.getPreviousXItem() = null, itemA.getPreviouxYItem() = null (itemA
is in the lower left corner)
itemB.getPreviousXItem() = itemA, itemB.getPreviouxYItem() = null (itemB
is right of itemA)
itemC.getPreviousXItem() = null, itemC.getPreviouxYItem() = itemA (itemC
is on top of itemA)
itemD.getPreviousXItem() = itemA, itemD.getPreviouxYItem() = itemB
(itemD is on top of itemB, right of itemA)
itemE.getPreviousXItem() = itemB, itemE.getPreviouxYItem() = null (itemE
is is right of itemB)

Notice: no continuous variables here, a normal search space (itemSize ^
itemSize)


PS: here's a good 2D bin packing reference for additional construction
heuristics
if the traditional ones implemented in Planner don't suffice
which you could implement in a custom solver phase *SolutionInitializer:
    http://clb.demon.fi/files/RectangleBinPack.pdf
Note that you'd still want to apply metaheuristics on the result of
that, to improve it further.


Op 20-06-12 11:13, Ralph Schwitalla schreef:

> Hi all,
> i am new to drools planner and try to model a 2dimensional rectangle packing
> problem.
> I have some problems modelling the problem facts because one of them (the
> list of free spaces) is constantly
> changing.
>
> For example I have a list of rectangles I try to pack on a fixed size layer.
> This list is fixed.
> But the list of free space is dynamic (first you have the whole layer as
> free space,
> then you cut out the space occupied by the first rectangle which gives you 3
> remaining free spaces, and so on)
>
> All the examples in the drools-planner-examples seem to have a fixed list of
> problem facts (rooms, teachers, timeslots) which only should be combined
> optimally.
>
> How can a dynamic number of problem facts be modelled?
>
> Greetings Ralph
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-changing-problem-fact-tp4018087.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

--
With kind regards,
Geoffrey De Smet


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users

[Ralph S.]

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

[laune]

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. <[hidden email]> 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
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users

[ge0ffrey]

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.<[hidden email]>  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
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

--
With kind regards,
Geoffrey De Smet


_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users

[Ralph S.]

Hi Geoffrey, Wolfgang,
sure is the problem discretized (the layer on which it should be packed is fixed size say 100cm x100cm and the rectangles have sizes to the cm) , that was not the question.

I can build a planning value x/y with a list of 100 entries for every cm and combine them, but i think this is very inefficent.

>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.

I can´t imagine a solution where you can have multiple x-predecessors and y-predecessors
and try to find out the combinations.

If i can´t use drools planner for the guilliotine based solution it´s ok, then i will program it by hand in java.
But i found Drools very promising.

Greetings,
Ralph

[Garf]

last month, Ralph wrote: All the examples in the drools-planner-examples seem to have a fixed list of problem facts (rooms, teachers, timeslots) which only should be combined optimally.

Just to address this one unanswered point.
The Cloud Balancing example does support changing the problem facts, specifically by removing computers (bins).

The last section of the planner documentation (section 12.4) addresses realtime planning, through the Solver.addProblemFactChange() API. This works whether you are removing problem facts (as the example shows) or modifying their contents.

This generally restarts the Solver -- but, if you are relatively optimized, the adjustment is found relatively fast. (I'm curious, though -- does the Solver expressly prioritize doing moves associated with those problem facts that were just changed?)

[ge0ffrey]

Op 17-07-12 20:54, Garf schreef:

> last month, Ralph wrote: /All the examples in the drools-planner-examples
> seem to have a fixed list of problem facts (rooms, teachers, timeslots)
> which only should be combined optimally./
>
> Just to address this one unanswered point.
> The Cloud Balancing example does support changing the problem facts,
> specifically by removing computers (bins).
>
> The last section of the planner documentation (section 12.4) addresses
> realtime planning, through the Solver.addProblemFactChange() API. This works
> whether you are removing problem facts (as the example shows) or modifying
> their contents.
>
> This generally restarts the Solver -- but, if you are relatively optimized,
> the adjustment is found relatively fast.

Internally, it restarts the Solver, but not from scratch, it restarts
starting from the best solution of the last run.
As a Solver user, you don't even notice this in your code, you just call
addProblemFactChange().
And it only takes milliseconds to find a feasible solution, see the log
below this video:
http://blog.athico.com/2011/07/real-time-planning-with-drools-planner.html
>   (I'm curious, though -- does the
> Solver expressly prioritize doing moves associated with those problem facts
> that were just changed?)
Not really, unless you count this:
A construction heuristic will only assigning the unassigned entities,
so any entity that gets unassigned (because of the problem fact change)
gets changed first.
For example a machine (=problem fact) got killed, so all it's processes
(= entities) are unassigned and they get assigned first.
After that, normal localSearch kicks in.

But you could prioritize moves that affect those associated problem
facts if you wanted to.
In 5.4 that's very hard to do, but 5.5.0.Beta1 will introduce an
interface ProbabilitySelectionWeightFactory to make it easy to do such
stuff.
I fear it's still going to require domain-specific code though, even if
it's just a class implementing that interface.
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Drools-Planner-changing-problem-fact-tp4018087p4018742.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

--
With kind regards,
Geoffrey De Smet




_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users