1
$\begingroup$

Say I have a library that looks like that:

   123cm
<-------->     

|________|
|________|
|________|
|________|
|________|
|________|
|________|
|________|
|        |

Its width is (here) 123cm, its height is 231.9cm, the number of book shelves (horizontal lines) is 8. I can put books on the floor so there are effectively 8+1=9 compartments where I can store the books vertically. I have a list of books with title, height and thickness. For example, a pandas dataframe df storing the information would look like:

    height_cm   thickness_cm    title
0   33.0000 2.5000  title1
1   27.4066 5.7912  title2
2   26.2890 4.0894  title3
3   26.1874 3.6068  title4

I can "adjust" the distance between one book shelf and the other and I want to find an "optimal" solution, given my list of books (every book is stored vertically and there is minimal waste of space).

So far I have implemented a really dumb python algorithm that is initialized with average book shelf spacing and tries to insert books sequentially. I pick the shelf whose spacing is the closest to the book's height. If the spacing is not enough I modify it to book's height + some minimum clearance. I also redistribute the modification for this particular spacing across other spacings. I insert the book and I do that for the next book. It gave some results...

EDIT:

Following @RcnSc comment, I tried to cast the problem as a linear programming one.

let :

  • $S_k$ the height of shelf $k \in \{0, ..., 8\}$
  • $W$ the max capacity of each shelf, $H$ the library's height. In my problem $W=123$, $H=231.9$
  • $x_{ik} = \left\{ \begin{array}{ll} 1 & \mbox{if book } i \in \mbox{shelf } k\\ 0 & \mbox{otherwise} \end{array} \right. $
  • $N$ the number of books, $t_{i}$ thickness of book $i$, $z_{i}$ height of book $i$.

then I want to optimize:

$$ \begin{equation} \begin{aligned} \max \min_{k \in \{0, ..., 8\}} \sum_{i=1}^{N} t_i x_{ik} \\ \text{s.t. } \sum_{i=1}^{N} t_i x_{ij}&\leq W,\ j\in \{0, \dots, 8\} \\ \sum_{k=0}^{8} x_{ik} &= 1, i \in \{1, \dots, N\} \\ \sum_{k=0}^{8} S_k &\leq H \\ x_{ik}z_i &\leq S_k, i \in \{1, \dots, N\}, k \in \{0, \dots, 8\} \end{aligned} \tag{P} \end{equation} $$

basically I want to put a maximum number of books on each shelf. I want to find $S_k$ and the assignments $x_{ij}$. Do you think the formulation makes sense? How to solve it in practice?

$\endgroup$
  • $\begingroup$ This looks like a linear programming problem. $\endgroup$ – RcnSc Jan 2 at 15:07
  • $\begingroup$ Your objective function looks a bit unusual to me -- this will maximise the width of the narrowest shelf, but is that really what you want to do? I suspect that all you really want is simply to fit as many books as possible, in which case you should just maximise $\sum_{i=1}^Nx_i$, and change the equality in constraint #2 to a $\le$. How to solve it in practice? Use an (I)LP solver. $\endgroup$ – j_random_hacker Jan 3 at 13:00
  • $\begingroup$ I just noticed that your last equation multiplies two variables together, so this isn't LP after all (even though one of those variables is binary). One approximation strategy would be to specify a predefined set of shelf heights, of which at most 8 must be chosen (using decision variables $s_1, \dots, s_r$, say). This way, the shelf heights become constants -- but you introduce a factor $r$ more constraints. BTW, a good heuristic would be simply to sort the books by height, then place as many books as will fit in a shelf, letting the tallest determine the shelf's height, etc. $\endgroup$ – j_random_hacker Jan 3 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.