# [R] Allocating shelf space

Thu May 10 08:03:20 CEST 2007

```> A: Make the efficient use of space
> B: Minimise the spatial disclocation of related books
>    (it is acceptable to separate large books from small books
>    on the same subject, for the sake of efficient packing).

Some comments, hope they make sense:

Let f(x) be a function that maps from a specific book arrangement to a
certain amount of space wastage.

You're also trying to minimise some function g() of the books' location.
You can't minimise two functions at once, unless you minimise some
function of both: h(f(x), g(x)). It up to you to determine what h() is.

For example, you could use a linear function, deciding that saving space
is 10 times more important than keeping books close together. Then your
objective function could be:
minimise:   h = f(x) + g(x)
subject to: f(x) = 10g(x)
f(x) >= 0, g(x) >= 0
(plus some nontrivial constraints on x)

(You should also set a lower bound on the solution values, otherwise f
will always be minimised at the expense of g, since f is "worth" more).

Although I've stated the problem in terms of Linear Programming, it's
really cheating. The much bigger issue is the combinatorial optimisation
problem underneath --- different arrangements of x result in different
values of h. This is much harder than LP, for anything but a small
number of objects to arrange. I'd be tempted to set up a toy version,
with small number of possible x values and simple constraints, and run
some heuristic-driven optimisation method such as simulated annealing,
Ant Colony Optimisation, Genetic Algorithms, etc.

Cheers,