(!******************************************************
Mosel Example Problems
======================
file d4backup_ka.mos
````````````````````
Bin packing: backup of files onto floppy disks
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Aug. 2005, rev. Mar. 2013
*******************************************************!)
model "D-4 Bin packing (CP)"
uses "kalis"
declarations
ND: integer ! Number of floppy disks
FILES = 1..16 ! Set of files
DISKS: range ! Set of disks
CAP: integer ! Floppy disk size
SIZE: array(FILES) of integer ! Size of files to be saved
end-declarations
initializations from 'd4backup.dat'
CAP SIZE
end-initializations
! Provide a sufficiently large number of disks
ND:= ceil((sum(f in FILES) SIZE(f))/CAP)
DISKS:= 1..ND
finalize(DISKS)
setparam("kalis_default_lb", 0)
declarations
save: array(FILES) of cpvar ! Disk a file is saved on
use: array(FILES,DISKS) of cpvar ! Space used by file on disk
diskuse: cpvar ! Number of disks used
end-declarations
! Set variable domains
forall(f in FILES) setdomain(save(f), DISKS)
forall(f in FILES, d in DISKS) setdomain(use(f,d), {0, SIZE(f)})
! Correspondence between disk choice and space used
forall(f in FILES, d in DISKS) equiv(save(f)=d, use(f,d)=SIZE(f))
! Limit the number of disks used
diskuse = maximum(save)
! Capacity limit of disks
forall(d in DISKS) sum(f in FILES) use(f,d) <= CAP
! Minimize the total number of disks used
if not cp_minimize(diskuse) then
writeln("Problem infeasible")
end-if
! Solution printing
writeln("Number of disks used: ", getsol(diskuse))
forall(d in 1..getsol(diskuse)) do
write(d, ":")
forall(f in FILES) write( if(getsol(save(f))=d , " "+SIZE(f), ""))
writeln(" space used: ", getsol(sum(f in FILES) use(f,d)))
end-do
end-model
|
