A computer operating system stores files on a hard disk. Five large files of sizes 18, 23, 12, 125, and 45 MB are to be stored. Contiguous blocks of storage are available with size 25, 73, 38, 156 MB, and each file must be stored in one contiguous block. In this problem we will explore an integer programming algorithm to assign files to storage blocks.

(a) In order to reserve large contiguous blocks of storage for future use, we want to store each file in the smallest available block large enough to hold the file. Define the cost of storing file i in block j to be the size of block j, and determine the assignment of files to blocks that minimizes the total cost. Use the five-step method, and model as an integer programming problem.

(b) Suppose that the 12 MB file expands to 19 MB. How does this effect the optimal solution found in part (a)? How much can this 12 MB file expand before the optimal solution changes?

(c) Suppose that the 18 MB file and the 23 MB file are to be stored in the same block, since they are used by the same program. How does this affect the optimal solution found in part (a)?

(d) One "greedy" algorithm for allocating blocks to files is to place each file in the first available block that is large enough to hold it. Apply this algorithm (by hand) and compare to the results of part (a). Is the IP solution found in part (a) significantly better than the results of the greedy algorithm?

(e) Why not just maximize the size of the largest remaining contiguous block of storage? Can this optimization problem be solved as an IP?