Re:Algorithmic fitting of Japanese candy
by aabajian on Wednesday November 16, 2016 @11:19PM
(#12974230)
Correct me if I'm wrong, but this seems like a convex optimization problem, assuming you know the sizes of the boxes and volume to pack them in. I think you could define a set of equality/inequality constraints and solve the problem efficiently. For further reading: http://www.stanford.edu/class/ee364a/
[ Parent
| on HN ]
It's not. The intersection constraints are not convex. You could use sequential convex programming to find a local optimum.
edit: to back up my claim: the feasible set of a convex optimization problem must be convex. suppose you have two squares of side length 1 at positions x1 and x2. The following two solutions are feasible:
x1a = (-2, 0), x2a = ( 2, 0)
x1b = ( 2, 0), x2b = (-2, 0)
but their midpoint is not: x1c = (x1a + x1b)/2 = (0, 0)
x2c = (x2a + x2b)/2 = (0, 0)
therefore the feasible set is not convex.