Optmizing areas covered by bricks

1 view (last 30 days)
JFz
JFz on 2 Nov 2017
Commented: JFz on 3 Nov 2017
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?
  2 Comments
Walter Roberson
Walter Roberson on 2 Nov 2017
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
JFz on 2 Nov 2017
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.

Sign in to comment.

Answers (2)

John D'Errico
John D'Errico on 2 Nov 2017
Edited: John D'Errico on 2 Nov 2017
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.
  3 Comments
John D'Errico
John D'Errico on 2 Nov 2017
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
JFz on 2 Nov 2017
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.

Sign in to comment.


Walter Roberson
Walter Roberson on 2 Nov 2017
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.
  1 Comment
JFz
JFz on 3 Nov 2017
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.

Sign in to comment.

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!