Packing Files onto Disks

Problem Specification

Suppose, you want to copy a set of files from your hard-disk onto as few as possible diskettes of a given size, e. g. onto common 1.44 MB diskettes. In case your files do not fit on a single diskette, it might become quite tricky to figure out the minimal number of needed diskettes and how to partition the files.

Viewpoint and Constraints

A diskette is modeled by a set disk_i. All sets disk_i form a partition of the set of all files sall$\_files$, i. e., all disk_i are pairwise disjoint and their union is sall$\_files$. The sizes of all files contained in a set is summed up and compared with the fixed capacity of the diskette.

Branching Strategy

The branching over the sets representing the individual disks employs straightforwardly a naive strategy. To get the minimal number of needed disks, we have to write a procedure that searches for the first solution iterating over an integer variable nbDisks beginning with small values. It is not possible to use a two dimensional branching strategy because the value of nbDisks would have to be reflected during search.

Script

val diskCap = 1440

type filev = {name : string, size : int} vector

val files = #[{name= "a",size = 360},{name= "b",size = 850},
              {name= "c",size = 630},{name= "d",size = 70},
              {name= "e",size = 700},{name= "f",size = 210}]
    

fun spreadFiles (files:filev) diskCap nbDisks space =
    let
       val size = Vector.length files
       val disks = Vector.tabulate(nbDisks,fn x => 
                      FS.upperBound(space,#[(1,size)]))
       val disks' = Vector.tabulate(nbDisks,fn x => 
                      FD.boolvarVec(space,size))
       val all_files = FS.Value.make(space,#[(1,size)])          
       fun sumFiles vec =  
           Vector.appi(fn(i,x) => 
             let 
                val list = List.tabulate(size,fn x => x+1)
             in      
                List.app(fn y => FS.domR(space,x,FS.SUP,#[(y,y)],
                           Vector.sub(Vector.sub(disks',i),y-1)))
                        list;
                FD.linear(space,VectorPair.zip(
                           Vector.tabulate(size,fn z => 
                                      #size(Vector.sub(files,z))),
                            Vector.map(fn z => FD.boolvar2intvar z)
                                 (Vector.sub(disks',i))),
                          FD.LQ,diskCap,FD.DOM)
             end)vec
   in 
       FS.relN(space,disks,FS.DUNION,all_files);
       sumFiles(disks);
       FS.setvarbranch(space,disks,FS.FSB_NONE,FS.FSB_MIN); 
       disks
   end

The function spreadfiles gets the formal arguments files, diskCap and nbDisks. The script returns the problem variable disks that contains the set of diskettes of size diskCap needed to store all files in files. and specifies what files have to be stored on which diskette.

The argument files is a vector of individual files, where each file is represented by a record with labels name and size. The argument diskCap and nbDisks are integers.

Because we want the number of disks we need to store the files to be minimal, we have to write an additional function that checks the result of a hardcoded value for nbDisks and tries to find - if possible - a smaller one.

The procedure sum_files ensures that every file is stored in a disk without exceeding capacity.

In listing 30 is given a function test that gets as formal argument an integer x. Given this integer, it computes the result of

Search.searchOne(spreadFiles files diskCap x).

If the function finds a solution it stops, otherwise it continues computation with the successor of x.

fun test x =                        
  let 
     val b = (Search.searchOne(spreadFiles files diskCap x))
             handle Space.InvalidSpace => NONE
     fun name l = List.map(fn z =>List.map(fn y => 
                  (#name)(Vector.sub(files,y-1)))z)l
  in
     case b of NONE => test(x+1)
             | SOME (s,r) =>
               (x,name(List.map(fn z => domainToList z)
                  (Vector.toList(Vector.map(fn x =>
                     FS.Reflect.upperBound(s,x))r))))
     
  end

Given the test function the argument 0, it computes

(2,[['a','b','f'],['c','d','e']])

where 2 is the minimal number of disks you need and the second argument is a list with the name of the files stored on the specific disks.