Constraint Programming

(!******************************************************
   Mosel Example Problems
   ======================

   file d4backup_ka.mos
   ````````````````````
   Bin packing: backup of files onto floppy disks

   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

   (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