Filling a box with cubes sized as powers of 2 with as few boxes as possible

Question

Say I have a box with integer dimensions and I need to fill it with cubes with side lengths of power of 2, how can I fully fill the box with as few cubes as possible? So say i have a $5 \times 5 \times 9$ box, how do I fill the space with as few cubes as possible (options would in this case include cubes with side length: 1,2,4). I'm looking for a general explanation, not just the answer to this example

Answer 1

You can solve this as a set partitioning problem via integer linear programming as follows. Let $\ell$, $w$, and $h$ be the dimensions of the box. Let $C$ be the set of all possible cubes that have a side length that is a power of $2$ and can fit in the box. Let $C_{i,j,k}\subset C$ be the set of cubes that contain cell $(i,j,k)\in [\ell] \times [w] \times [h]$. For $c\in C$, let binary decision variable $x_c$ indicate whether cube $c$ is used. The problem is to minimize $\sum_{c\in C} x_c$ subject to linear constraints $$\sum_{c\in C_{i,j,k}} x_c = 1 \quad \text{for all $(i,j,k) \in [\ell] \times [w] \times [h]$}$$ that force each unit cell in the box to be covered by exactly one cube in $C$.

For $(\ell,w,h)=(5,5,9)$, we have $|C|=377$, and the optimal objective value turns out to be $99$, attained by using two cubes of side length $4$ (for example, with corners $(2,2,1)$ and $(2,2,5)$, respectively) and $5\cdot5\cdot9 - 2\cdot 4^3 = 225 - 128 = 97$ unit cubes, as suggested by @ThomasAndrews.