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

[Geoffrey De Smet]

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
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>

-- 
With kind regards,
Geoffrey De Smet