Hi Folks, This is not an R question as such, though it may well have an R answer. (And, in any case, this community probably knows more about most things than most others ... indeed, has probably pondered this very question). I: Given a "catalogue" of hundreds of books, where each "entry" has author and title (or equivalent ID), and also Ia) The dimensions (thickness, height, depth) of the book Ib) A sort of classification of its subject/type/genre II: Given also a specification of available and possibly potential bookshelf space (numbers of book-cases, the width, height and shelf-spacing of each, and the dimensions of any free wall-space where further book-cases may be placed), where some book-cases have fixed shelves and some have shelves with (discretely) adjustable position, and additional book-cases can be designed to measure (probably with adjustable shelves). Question: Is there a resource to approach the solution of the problem of optimising the placement of adjustable shelves, the design of additional bookcases, and the placement of the books in the resulting shelf-space so as to 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). Awaiting comments and suggestions with interest! With thanks, Ted. -------------------------------------------------------------------- E-Mail: (Ted Harding) <ted.harding at nessie.mcc.ac.uk> Fax-to-email: +44 (0)870 094 0861 Date: 09-May-07 Time: 18:23:53 ------------------------------ XFMail ------------------------------
I don't know if there's an R solution, but this sounds to me like some variation of the knapsack problem... http://en.wikipedia.org/wiki/Knapsack_problem Andy From: ted.harding at nessie.mcc.ac.uk> > Hi Folks, > > This is not an R question as such, though it may well have > an R answer. (And, in any case, this community probably > knows more about most things than most others ... indeed, > has probably pondered this very question). > > I: Given a "catalogue" of hundreds of books, where each > "entry" has author and title (or equivalent ID), and also > > Ia) The dimensions (thickness, height, depth) of the book > Ib) A sort of classification of its subject/type/genre > > II: Given also a specification of available and possibly > potential bookshelf space (numbers of book-cases, the width, > height and shelf-spacing of each, and the dimensions of any > free wall-space where further book-cases may be placed), > where some book-cases have fixed shelves and some have shelves > with (discretely) adjustable position, and additional book-cases > can be designed to measure (probably with adjustable shelves). > > Question: Is there a resource to approach the solution of the > problem of optimising the placement of adjustable shelves, > the design of additional bookcases, and the placement of the > books in the resulting shelf-space so as to > > 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). > > Awaiting comments and suggestions with interest! > With thanks, > Ted. > > -------------------------------------------------------------------- > E-Mail: (Ted Harding) <ted.harding at nessie.mcc.ac.uk> > Fax-to-email: +44 (0)870 094 0861 > Date: 09-May-07 Time: 18:23:53 > ------------------------------ XFMail ------------------------------ > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide > http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. > > >------------------------------------------------------------------------------ Notice: This e-mail message, together with any attachments,...{{dropped}}
> 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
Isn't this rather closely related to the (more or less classic) bin packing and knapsack problems? The 'hardness' of the problem is combinatoric (NP) and that is statistical, but the answers aren't particularly statistical. Both have been studied quite a lot for pragmatic reasons (packing products with minimal packaging etc), so there is quite a large literature out there somewhere http://en.wikipedia.org/wiki/Bin_packing_problem is one possible starting point. S>>> ted.harding at nessie.mcc.ac.uk 09/05/2007 18:23:56 >>>Hi Folks, This is not an R question as such, though it may well have an R answer. (And, in any case, this community probably knows more about most things than most others ... indeed, has probably pondered this very question). I: Given a "catalogue" of hundreds of books, where each "entry" has author and title (or equivalent ID), and also Ia) The dimensions (thickness, height, depth) of the book Ib) A sort of classification of its subject/type/genre II: Given also a specification of available and possibly potential bookshelf space (numbers of book-cases, the width, height and shelf-spacing of each, and the dimensions of any free wall-space where further book-cases may be placed), where some book-cases have fixed shelves and some have shelves with (discretely) adjustable position, and additional book-cases can be designed to measure (probably with adjustable shelves). Question: Is there a resource to approach the solution of the problem of optimising the placement of adjustable shelves, the design of additional bookcases, and the placement of the books in the resulting shelf-space so as to 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). Awaiting comments and suggestions with interest! With thanks, Ted. -------------------------------------------------------------------- E-Mail: (Ted Harding) <ted.harding at nessie.mcc.ac.uk> Fax-to-email: +44 (0)870 094 0861 Date: 09-May-07 Time: 18:23:53 ------------------------------ XFMail ------------------------------ ______________________________________________ R-help at stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. ******************************************************************* This email and any attachments are confidential. Any use, co...{{dropped}}