Subsections

## 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 diski. All sets diski form a partition of the set of all files sall, i. e., all diski are pairwise disjoint and their union is sall. 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

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.

Andreas Rossberg 2006-08-28