[R] Allocating shelf space

[Gad Abraham]

> 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,
Gad

-- 
Gad Abraham
Department of Mathematics and Statistics
The University of Melbourne
Parkville 3010, Victoria, Australia
email: g.abraham at ms.unimelb.edu.au
web: http://www.ms.unimelb.edu.au/~gabraham