Optmizing areas covered by bricks

2 次查看（过去 30 天）
JFz
JFz 2017-11-2
评论： JFz 2017-11-3
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 个评论
Walter Roberson
Walter Roberson 2017-11-2
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 2017-11-2
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

John D'Errico
John D'Errico 2017-11-2
编辑：John D'Errico 2017-11-2
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 个评论
显示 1更早的评论
John D'Errico
John D'Errico 2017-11-2
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 2017-11-2
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.

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2017-11-2
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
  1 个评论
JFz
JFz 2017-11-3
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Particle Swarm 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by