Partition techniques optimization

[laaziz]

Hello guys,

I work on a final project study discussed the use of optimization methods.
The project in question consists in partitioning a grid dimensions NXM grids in dimensions 3 X 3 (which share no box) to the extent possible, otherwise find grids of dimensions 3 x 3 which are dependent grids ie 3 X 3 shares of cells.
The dimensions N and M are known and can be multiple of 3!

I managed to make the algorithm but it is not optimal, I would like to know if there are technical mathematical partitioning has on these problems for better optimization.

The goal is to be elected in each grid box center.

Thank you.

 

[laaziz]

I would like to find the whole sub grids

 

[chiro]

Hey laaziz and welcome to the forums.

Just for your interest, the area that this kind of thing is study for the general situation is known as the bin-packing problem (for this case it's in 2D), but for this situation, the scenario is a lot simpler than the algorithms you would have to use for this.

Since you only have one object and since every object is a square, and since your packing area is a rectangle, the problem is greatly simplified.

The only thing left though is to specify the constraints for partitioning: for example can you only use single chopped up areas (i.e. you can't take say two chopped areas and "stick them together") or can you stick things together?

Basically you will have to maximize the number of boxes given that you have a constraint on the width and height of the area where you have a constraint on your box (3X3) and you want to maximize the number of boxes and add any other constraints you wish.

So basically, the simplest version (which is probably not complete is)

Maximize B for Boxes:

Box_width = 3, Box_Height = 3, Grid_Width = N, Grid_Height = M, where:

Number of Boxes can be found using a 2D "Modulus" of the area.

From number theory we know that N = PQ + R where if we want to divide P into N, we get a quotient of Q and a remainder of R.

So we want to maximize Q which means minimizing R.

This is where it gets interesting: if we look at it with absolutely no constraints (where we can just glue individual squares together), we simply calculute Q = (N*M) \ (3*3) = whatever and the remainder will be (N*M) MOD 9.

Now if we add more constraints then this changes. For higher constraints we need to consider the requirements of the grid. What we can do first is partition the entire region into "regions mod a particular volume".

So for 3x3 this means basically doing a MOD problem in two dimensions. So if we want say 3x3 units, we do a simultaneous N \ 3 (Integer divide) and M \ 3 to get the biggest partition. The integer divide basically does the division and removes the remainder (i.e. anything after the decimal point).

This divides the area into blocks but remember this is easy because you have only one object to pack (i.e. 3X3 squares), and the region is a simple one (a rectangle).

Now you can decide whether you want to be able to combine strips or not: if you can't then you're done but if you can you just add up all the unit squares and calculute the area \ 9.

This problem though seems a little too straightforward: are you just packing the boxes in any order as separate boxes or are they connected?

If you want to look into some theory you should check out Bin-Packing in Operations Research and also think about the idea of how you can create a "Modulus" in n-dimensions for an actual "shape" instead of a number (picture the normal modulus we do in number theory as the special case when the dimension of the region is 1 (i.e. we are packing lots of 1-D sticks into stick bins).

 

[laaziz]

So, Thank you very much chiro for your analysis in depth and for pertinent suggestions.

I want just to add one thing is that i have just one object of 3X3 dimensions to pack, so it is easily.
I will check out Bin-Packing in Operational Research and i will inspire from.

Best regards.