Practice example: Bookshelf

An example on the level of a test after the end of semester

The problem

We have recently moved into a new apartment, and we are in trouble of putting our books on the shelves in an organized way. The shelf system that we have is an adjustable one. There are 7 shelf plates, whose height we can decide. For the sake of this example, we can assume, that not only fixed positions are available, but anything above 50 cm. The plates are 120 cm wide, 20 cm deep and 2 cm thick.

Our books are organized into booksets, like math books, IT books, Tolkien novels, Harry Potter series, diplomas of formerly supervised students, etc. For each bookset we know the total width of the books in that bookset, and the height of the tallest among them.

Our gool is to put the sets on the shelves in such a way, that the highest we must reach for anything is minimal. To keep order, we don't want to split up any sets, and we also want to have a 7cm gap between the highest book on a shelf and the shelf above. We are, however, not forced to use all of the plates, if it is not necessary.

Problem data

The raw data for the problem is given below: 

set BookSets := Math IT Sport Music Novel Tolkien Feist HarryPotter Diplom;

param :          width      height:=
    Math           100          20
    IT              80          25
    Sport           30          30
    Music           50          30
    Novel           40          20
    Tolkien         30          25
    Feist           50          20
    HarryPotter     90          25
    Diplom          70          40
;

param shelfCount := 7;

param shelfWidth := 120;
param shelfHeight := 2;

param minDistance := 7;
param minPosition := 50;

(One) optimal solution

To be able to validate your model, here is an optimal arrangement of books. Obviously, many permutations will have the same result. It is easy to see, that if shelves below the top one are exchanged, than the objective will not change.

NovelFeistMathITSportTolkienHarryPotterMusicDiplom

The model

Try to figure out the model yourself. A tip: use redundant variables for the positioning of the shelves, and for the height of the tallest book on a shelf. Reveal solution 

# Input data declaration

set BookSets;
param width{BookSets};
param height{BookSets};

param shelfCount;
set Shelves:=1..shelfCount;

param shelfWidth;
param shelfHeight;

param minDistance;
param minPosition;

param M:=500;


# Variables
var use{Shelves} binary; 
var position{Shelves} >= minPosition;
var put{BookSets,Shelves} binary;

var maxbookheight{Shelves}>=0;
var maxusedshelf;



# Constraints

# If a shelf is used all the shelves below it are used
s.t. ShelfUsage {s in Shelves : s!=1}:
  use[s] <= use[s-1];


# If a shelf is used, it should be higher then the one below it (maxbook + 7cm)

s.t. MaxBookHeightSetter{b in BookSets, s in Shelves}:
  maxbookheight[s] >= height[b] * put[b,s];
  
s.t. ShelfPositioning{s in Shelves: s!=1}:
  position[s] >= position[s-1]+maxbookheight[s-1]+shelfHeight+minDistance;


# Only put booksets on used shelves
# Only put as many booksets on shelves as they can hold

s.t. ShelfCapacity{s in Shelves}:
  sum{b in BookSets} put[b,s] * width[b] <= shelfWidth * use[s];

# Each booksets must be put on exactly one shelf
s.t. BookSetAssignment{b in BookSets}:
  sum{s in Shelves} put[b,s] = 1;

# Set max used shelf
s.t. MaxUsedShelf{s in Shelves}:
  maxusedshelf >= position[s] - M *(1 - use[s]);

# Objective function

minimize topShelfHeight: maxusedshelf;

# Display statements
solve;


printf "<svg width='%d' height='%d'>",shelfWidth+20,(sum{ss in Shelves: (ss==shelfCount && use[ss]==1) || (use[ss]==1 && use[ss+1]==0)} (position[ss] + maxbookheight[ss]+shelfHeight)-position[1])+20; # <-- s/500/totalheight
for {s in Shelves : use[s]==1}
{

printf "<rect x='%d' y='%d' width='%d' height='%d' style='fill:rgb(214, 119, 36)' />",10,10+sum{ss in Shelves: (ss==shelfCount && use[ss]==1) || (use[ss]==1 && use[ss+1]==0)} (position[ss] + maxbookheight[ss]+shelfHeight)-position[s]-shelfHeight,shelfWidth,shelfHeight; # <-- s/500/totalheight
 for {b in BookSets : put[b,s]==1}
 {
    
    printf "<rect  x='%d' y='%d' width='%d' height='%d'"
    ,10+sum{b2 in BookSets : b2<b && put[b2,s]}width[b2]
    ,10+sum{ss in Shelves: (ss==shelfCount && use[ss]==1) || (use[ss]==1 && use[ss+1]==0)} (position[ss] + maxbookheight[ss]+shelfHeight)-(position[s]+shelfHeight)-height[b] # <-- s/500/totalheight
    ,width[b]
    ,height[b]
    ;
    printf " style='fill:rgb(%d,%d,80);stroke:black;stroke-width:1' />"
    ,(1-height[b]/maxbookheight[s])*100+155
    ,50+200*width[b]/shelfWidth
    ;

    printf "<text x='%d' y='%d' font-family='Verdana' font-size='6' fill='white'>%s</text>"    
    ,15+sum{b2 in BookSets : b2<b && put[b2,s]}width[b2]
    ,23+sum{ss in Shelves: (ss==shelfCount && use[ss]==1) || (use[ss]==1 && use[ss+1]==0)} (position[ss] + maxbookheight[ss]+shelfHeight)-(position[s]+shelfHeight)-height[b] # <-- s/500/totalheight
    ,b
    ;
 }
 

}
printf "</svg>";

Observe the display statements at the end of the code, they generate the svg figure shown above.

Bonus exercise

Imagine, that we have a given frequency for all of the booksets, that means, how often we get one of the books from it let's say in a year. The most comfortable height for us to fetch something is 120 cm, anything below or above that requires extra "effort", that is linear to the difference from 120 cm. Organize the books in such a way, that our overall effort over the year is minimal.