optimization: transport balls in a box so that the surface of the box is as small as possible

Question

To transport $n$ balls with diameter $d>0$ a cuboid box should be constructed so that the surface of the box is as small as possible. Model this problem as an optimization problem. Is the admissible set convex?
My idea:
The surface of the box is $S=2(ab+bc+ac)$. Let $m_i=(x_i, y_i,z_i)\in\mathbb R^3$ be the middle point of ball $i$.
Then I have $\frac{d}{2}\leq x_i\leq a-\frac{d}{2}, \frac{d}{2}\leq y_i\leq b-\frac{d}{2}, \frac{d}{2}\leq z_i\leq c-\frac{d}{2}$ for every $i=1,...,n$ and $\|m_i-m_j\|_2\geq d$ for $1\leq i<j\leq n$. Is this correct? And how can I prove if the admissible set is convex?

Answer 1

This is very difficult. It’s hard enough for circles in a square or rectangle. If you try the maximum number of circles of radius 1 into a rectangle, the optimal solution will usually have no regular pattern. In three dimensions, the situation will just be worse.

Now you want the box with the smallest surface area containing n balls… that’s one level harder. For a fixed box size, build a box, fill it with balls and shake it. That will give you a somewhat reasonably good solution.