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.

 

[LudusRex]

Hello,

Partition techniques optimization is a complex problem that has been extensively studied in the field of mathematics and computer science. There are several techniques that can be used to optimize partitioning, such as graph partitioning algorithms, heuristic methods, and mathematical optimization techniques.

In your project, it seems like you are looking for a partitioning method that can efficiently divide a grid of dimensions NXM into smaller grids of dimensions 3x3. This type of problem falls under the category of graph partitioning, where the grid can be represented as a graph and the goal is to partition it into smaller subgraphs with minimal interconnections.

One approach that you can consider is the Kernighan-Lin algorithm, which is a widely used graph partitioning algorithm that aims to minimize the number of interconnections between partitions. Another approach is to use mathematical optimization techniques, such as linear programming or integer programming, to find an optimal partitioning solution. These methods may require a more complex implementation, but they can provide the best possible solution for your problem.

I would also recommend exploring heuristic methods, which are algorithms that may not guarantee an optimal solution but can provide a good approximation in a reasonable amount of time. One example is the simulated annealing algorithm, which is inspired by the process of cooling metal to form crystals and can be applied to partitioning problems.

In conclusion, there are various techniques that you can explore to optimize your partitioning problem. It would be helpful to further research and compare different methods to find the most suitable approach for your project. Good luck!