How to solve an arrangement problem at the Archive Nationale of France using graph theory? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-10-17T02:41:38Z https://cs.stackexchange.com/feeds/question/48511 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/48511 9 How to solve an arrangement problem at the Archive Nationale of France using graph theory? IggyPass https://cs.stackexchange.com/users/30481 2015-10-20T22:47:43Z 2018-08-15T22:49:21Z <p>Good evening! I'm actually doing an internship at the Archives Nationales of France and I encountered a situation I wanted to solve using graphs...</p> <h1>I. The dusty situation</h1> <p>We want to optimize the arrangement of books of my library according to their height in order to minimize their archive cost. The height and thickness of the books are known. We already arranged the books in ascending order of height $H_1,H_2,\dots,H_n$ (I don't know if it was the best thing but... that's the way we did it). Knowing each book's thickness, we can determine for each $H_i$ class the necessary thickness for their arrangement, call it $L_i$ (for example, the books that are $H_i = 23\,\mathrm{cm}$ tall might have total thickness $L_i = 300\,\mathrm{cm}$).</p> <p>The library can custom manufacture shelves, indicating the wished length and height (no problem with depth). A shelf of height $H_i$ and length $x_i$ costs $F_i+C_ix_i$, where $F_i$ is a fixed cost and and $C_i$ is the cost of the shelf per length unit.</p> <p>Note that a shelf of height $H_i$ can be used to store books of height $H_j$ with $j\leq i$. We want to minimize the cost.</p> <p>My tutor suggested I model this problem as a path-finding problem. The model might involve $n+1$ vertices indexed form $0$ to $n$. My mentor suggested I work out the existing conditions, each edge signification and how to work out the valuation $v(i,j)$ associated to the edge $(i,j)$. I would also be OK with other solutions as well as insights.</p> <p>For instance we have for the <em>Convention</em> (a dark period of the French History) such an array:</p> <p>\begin{array}{|c|rr} i &amp; 1 &amp; 2 &amp; 3 &amp; 4\\ \hline H_i &amp; 12\,\mathrm{cm} &amp; 15\,\mathrm{cm} &amp; 18\,\mathrm{cm} &amp; 23\,\mathrm{cm}\\ L_i &amp; 100\,\mathrm{cm} &amp; 300\,\mathrm{cm} &amp; 200\,\mathrm{cm} &amp; 300\,\mathrm{cm} \\ \hline F_i &amp; 1000€ &amp; 1200€ &amp; 1100€ &amp; 1600€ \\ C_i &amp; 5€/\mathrm{cm} &amp; 6€/\mathrm{cm} &amp; 7€/\mathrm{cm} &amp; 9€/\mathrm{cm}\\ \end{array} </p> <h1>II. The assumptions of a trainee bookworm</h1> <p>I think I have to compute an algorithm between Djikstra, Bellman or Bellman-Kalaba... I'm trying to find out which one in the following subsections.</p> <h2>1.Conditions</h2> <p>We are here with a problem of pathfinding between a vertice $0$ and a vertice $n$, $n$ must be outgoing from $0$ (that is to say, a path (or a walk) must exists between $0$ and $n$</p> <h2>2.What to compute (updated (25/10/2015))</h2> <p>// <em>Work still under process as far as I don't know which vertices to and which edges to model...</em></p> <h3>My best guess</h3> <p>I think we get rid of at least one type of shelves every time we find a shortest path from the array, but that's only my assumption... ;).</p> <p>I think the best way to model how to buy shelves and store our books must look like the following graph, <em>(but, please, feel free to criticize my method! ;))</em></p> <p><a href="https://i.stack.imgur.com/HYcQC.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HYcQC.png" alt="from 0 graph"></a></p> <p>vertices:</p> <ul> <li>$i\in[1,4]$ are shelves we can use to store our books.</li> <li>$0$ is the state where no book is stored. Using this vertice allows me to use each cost formulas (edges).</li> </ul> <p>edges: $F_i+C_ix_i,i\in[1,4]$ are the cost using a type of shelve. for instance: $F_1+C_1x_1$ fom 0 is the cost using only type 1 shelves to store our parchments, manuscripts...</p> <p>Yet, from here I don't know how to create my shortest path problem.</p> <p>Indeed, I would not know where would I have stowed all my books.</p> <p>This leads me to another idea...</p> <h3>another idea...</h3> <p><a href="https://i.stack.imgur.com/Uax0A.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Uax0A.png" alt="to 0 graph"></a></p> <p>Here, I am searching for the shortest path from a given vertice to the 0 state, that is to say, knowing that the highest document is $type \ i$ tall, I am searching for the cheapest way to arrange my documents.</p> <p>vertices:</p> <ul> <li>$i\in[1,4]$ are shelves we can use to store our books.</li> <li>$0$ is the state where all books are stored. Using this vertice allows me to use each cost formulas (edges).</li> </ul> <p>edges: $F_i+C_ix_i,i\in[1,4]$ are the cost using a type of shelve. for instance: $F_1+C_1x_1$ from 3 is the cost using $type \ 1$ shelves after using $type \ 3$ shelves to store our parchments, manuscripts...</p> <p>Yet, I don't know where to put $F_4+C_4x_4$.</p> <h2>3.How to compute</h2> <p>I think that we have to start with the higher shelves as far as we can then store the smaller books...</p> <p>Do</p> <p>We take $L_n$ cm of with the $H_{i=n}$ height in a shelve of their height + $z$ cm of an $H_{i=n-1}$ height until it becomes more expensive than taking the $H_{i=n-1}$ shelve. then $i=i-1$</p> <p>While i>&lt;0</p> <p>Finally, I don't know how to make x varying...</p> <p>That is to say how to choose to put $x_i$ documents in $4$ or $3$ for instance.</p> https://cs.stackexchange.com/questions/48511/-/48541#48541 7 Answer by jjohn for How to solve an arrangement problem at the Archive Nationale of France using graph theory? jjohn https://cs.stackexchange.com/users/19943 2015-10-21T17:48:03Z 2015-10-21T21:43:06Z <hr> <p>I think I have a solution to your problem. Hopefully I haven't misunderstood something in the definition of your problem. Here it goes:</p> <p>I'm going to describe a Dynamic Programming approach. It's an $O(n^{2})$ algorithm, which means that since the number of books is huge it's not going to help you a lot. (you need to modify it a bit!). With some work, you can turn said Dynamic Programming approach into an instance of finding the shortest path on a Directed Acyclic Graph. (Which itself is a dynamic programming algorithm :P)</p> <p>Suppose there are $n$ books all of different height.</p> <p>Suppose also that the optimal cost is achieved by assigning the books to $i$ shelfs of height $h_{1},h_{2},...,h_{i}$ where $h_{1}&lt;h_{2}&lt;...&lt;h_{i}$.</p> <p>Let's prove the following two things:</p> <p>A. $C_{a}&gt;C_{a-1}$</p> <p>Suppose the contrary. Let $B_{a-1}$ be the set of books assigned to shelf $a-1$ Then $cost = other,stuff + C_{a-1}*thickness(B_{a-1})$</p> <p>Since, we assumed, $C_{a}&lt;C_{a-1}$, let's transfer all books of shelf $a-1$ to $a$ (which is possible since $h_{a-1}&lt;h_{a}$.</p> <p>So,now, $cost =other,stuff + C_{a}*thickness(B_{a})$ which is lower than before. Hence, we have a contradiction due to the Optimality we assumed.</p> <p>So $C_{a}&gt;C_{a-1}$ for all shelfs created</p> <p>B. Let $j$ be a book that is assigned to shelf $a$. Let's prove that $height(j)&gt;h_{a-1}$ </p> <p>This is fairly easy. If $height(j)$ was smaller than $h_{a-1}$ we could put the book into shelf $a-1$ for a better cost (due to A).</p> <p>Of the two things we've proven, B is the significant one.</p> <p>Let $dp[a]$= the optimal cost for shelving books $1...a$ so that there is a shelf of $height(a)$. You have to find a way to define $dp[a]$ by the values $dp,dp,....dp[a-1]$</p> <p>I'm going to stop here. If you are familiar with Dynamic Programming, using fact B, you will easily come up with the recurrence. Otherwise, ask :). As I said, this can be turned into a DAG problem. Knowing the relation above, it's easy to realize what the edge $(a,b)$ stands for and define its cost. </p> <p>Last but not least, like I said above,as books are large, you cannot use the algorithm for each and every book. I think that representing its height by the sum of its thickness should do the trick. (I think it's already like that from your statement)</p> <p>(I'm guessing number of different heights is much much less than number of books)</p> <hr> https://cs.stackexchange.com/questions/48511/-/48550#48550 0 Answer by vzn for How to solve an arrangement problem at the Archive Nationale of France using graph theory? vzn https://cs.stackexchange.com/users/699 2015-10-21T23:34:43Z 2015-10-25T00:24:27Z <p>Sometimes just "zooming in" on the "nearest problem" in the literature can help understand the theory and background behind the problem, build an abstraction, and eliminate spurious details. The nearest problem in the literature to yours seems to be what is known as "variable size bin packing problem". Sample papers are included below. This problem is highly theoretically studied and some off-the-shelf software exists, it shows up in optimizing packing boxes in eg trucks shipping containers. There are also versions where one can adjust container size. There are many algorithmic approaches. eg, from 1<sup>st</sup> paper:</p> <blockquote> <p>The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into a minimum number of three-dimensional rectangular bins.</p> </blockquote> <ul> <li><p><a href="http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf" rel="nofollow noreferrer">OPTIMIZING THREE-DIMENSIONAL BIN PACKING THROUGH SIMULATION</a> / Dube, Kanavathy</p></li> <li><p><a href="http://orsc.edu.cn/online/120601.pdf" rel="nofollow noreferrer">Bin Packing Problem with Uncertain Volumes and Capacities</a> / Peng, Zhang</p></li> <li><p><a href="https://stackoverflow.com/questions/2192087/3-dimensional-bin-packing-algorithms">3d bin packing algorithms</a>, stackoverflow</p></li> </ul> https://cs.stackexchange.com/questions/48511/-/48715#48715 5 Answer by CR Drost for How to solve an arrangement problem at the Archive Nationale of France using graph theory? CR Drost https://cs.stackexchange.com/users/558 2015-10-25T22:18:15Z 2015-10-25T22:18:15Z <p>I see you as asking, "I want to solve this with Dijkstra's algorithm but I can't set up a good graph to run on," therefore I will present you with such a graph.</p> <h1>A digraph where vertices are sets of shelved books.</h1> <p>Okay, we have books with heights $H_n,$ $1 \le n \le N$ and widths $W_n,$ with heights in ascending order for each book, and we want to group them into shelves.</p> <p>Reuse these numbers for solution nodes $n,$ where that node represents a solution state "all books $i \le n$ have been shelved." We will therefore start at node $0$ and seek to get to node $N$ by the shortest path with Dijkstra's algorithm. These nodes are the vertices of our graph.</p> <p>We then draw from node $i$ to any node $j \gt i$ a directed edge which assumes that all of those intermediary books will be shelved with one shelf, i.e. the length of this edge is $$L_{ij} = F_j + C_j~\sum_{n=i+1}^j W_n,$$where I have assumed that when you were saying the cost of the sum was $F_i + C_i x_i$ the subscript $i$ on the $x_i$ was totally meaningless.</p> <p>Dijkstra's algorithm will then give us a shortest-length path to node $N.$ </p>