Optimal coverage of a $D$-dimensional grid with small blocks I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, m_D)$ such that:


$\prod_{i=1}^D m_i = M$,
$R = \prod_{i=1}^D f(N_i, m_i) m_i - \prod_{i=1}^D N_i$ is as low as possible. Here $f(N,m)$ is the minimal number of blocks of length $m$ necessary to cover a 1D grid with size $N$ (or, formally, $f(N, m) = N / m$ if $N$ is a multiple of $m$, and $f(N,m) = N\,\mathrm{div}\,m + 1$ otherwise).
The number of $m_i$ equal to 1 is as high as possible (but this is low priority, the condition 2 is more important).


How should I approach this? Is there some standard algorithm this can be reduced to?

In my case $M$ is not very big (of the order of 1000). Also, an absolute minimum in all cases is not strictly required; if there is an approximate algorithm, it will do to.

(In case anyone is interested in the application, I want to use it to find work group dimensions for an OpenCL kernel with a known global size and total number of work items).
One unsophisticated approach is to factor $M$, then exhaustively explore all possible decompositions of $M$ into a product of $D$ integers, and see which is best according to your criteria.  I suspect this will prove to be an entirely reasonable solution for your example parameter ranges.

The number of possible decompositions is exponentially large, in general.
If $M=\prod_i p_i^{e_i}$, then there are $\prod_i {D+e_i-1 \choose e_i}$ possible decompositions, which (depending upon $M$) could be rather a lot.

However, for your particular parameter values, the number of possible decompositions will probably still be manageable, so the unsophisticated algorithm should work fine.  If $D=3$ and $M$ is 32 times a random number from 1 to 32, then the number of possible decompositions will range from a minimum of 21 possibilities (for $M=32\times 1$) to a maximum of 252 possibilities (for $M=32\times 30$).  That's small enough that you can easily enumerate all possibilities and see which is best.

If you increase $D$ to $D=7$, then the number of possible decompositions will vary from a minimum of 462 (for $M=32\times 1$) to a maximum of 45276 possibilties (for $M=32\times 30$).  That's still small enough that you can enumerate all possibilities and use the unsophisticated algorithm I mention above.

If you run into some other parameter choices where there are too many decompositions, a simple variant would be to randomly pick a bunch of different decompositions and see which of those is the best.  It's not the fanciest algorithm around, but it's a reasonable thing to try.

Anyway, this should solve your problem for the parameter sizes you mention.