Optmizing areas covered by bricks

Hi, I am facing an optimization problems. It is like, not exactly, to optimize the areas covered by irregular shaped bricks, such that the overall area can be minimized. Can I use any of the optimization function such as fmincon? Thanks for any help?

[Walter Roberson]

When you say that "so that the overall area can be minimized", are you talking about the convex hull? Or about the bounding box? Or some kind of outer boundary such as might be found by alpha shapes and the boundary() function ?

[JFz]

Yes, I have several closed areas with boundaries. I cover the areas with the bricks. The objective is to minimize the sum of the areas or the sum of all the little areas of the bricks.

Answer 1

[John D'Errico]

Sorry, but this is not even remotely the kind of problem a tool like fmincon (or the other tools in those toolboxes) are designed to solve. Such a packing problem, with generally irregular objects, can be quite tricky to solve. Even relatively simple problems like circle packing are not at all trivial, especially given some general domain.

You don't say if the bricks can be placed at any general orientation or not. If they are completely general in orientation, or they are not all the same shape, then things will get worse yet.

Could you try to implement it using fmincon? Well, I suppose you could try to formulate an optimization based on the location of the center of each brick, AND the angular rotation for every brick. Sadly, that would fail. It would fail because you won't actually know for sure how many bricks will be needed. So you won't even know how many variables are in the problem.

Were I to try to solve the problem, I might use some variation of simulated annealing, perturbing the bricks to try to minimize the uncovered area, but still subject to constraints on overlap. It would be hell to solve, and at best all you will get is a sub-optimal solution, subject to the quality of the starting point.

Simpler yet would be a greedy algorithm. Place one brick at a time, starting in one corner. Then pack others, again, one at a time, so they are touching the last. You are done when there is no room for another brick. Completely a sub-optimal solution, but doable. Even that will take some time to write code to do.

[JFz]

Thank you so much! The brinks are rectangular but in different sizes. And they should be placed along x-axis. But there are certain boundaries in each area. after thinking about it over and over, I am thinking "dynamic programming". But I am not sure if matlab can help in that.

[John D'Errico]

The optimization TB tools would not be of much value here, I think. But dynamic programming is a phrase often applied to solve this class of problem.

[JFz]

Thanks. I am starting to look into dynamic programming optimal control at this moment. So Matlab does not have any tool for this type of problem, I guess.

Answer 2

[Walter Roberson]

I am not clear as to what is being minimized?

Also, I am not clear as to whether you have an indefinite supply of bricks at each size or if there is a limited number of each size?

For each area, are you trying to fill as much of the area as possible without going outside the area, with the aim of minimizing the unfilled space within each area? Or do you need to cover the entire area with no holes and want to minimize the total amount of brick sticking outside the area?

It sounds to me as if you have a Knapsack problem.

One advanced Knapsack contribution is https://www.mathworks.com/matlabcentral/fileexchange/20436-multi-knapsack-solver

A 1D solver is https://www.mathworks.com/matlabcentral/fileexchange/35753-knapsack-problem

A ga approach to one of the varieties of knapsack is https://github.com/5amron/solving-0-1-knapsack-problem-by-using-Genetic-Algorithm-matlab

A harmony search approach is described at http://www.matarka.hu/koz/ISSN_1789-2198/vol_7_no_1_2013_eng/ISSN_1789-2198_vol_7_no_1_2013_eng_013-020.pdf

[JFz]

Thank you so much! yes, my problem is very much like knapsack, but I have 10 different shape knapsacks, and 1000 bricks in different shapes. Thank you. I will look at the links above. Have a nice day.