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

   file d4backup2_ka.mos
   `````````````````````
   Bin packing: backup of files onto floppy disks
   - Alternative formulation using 'cumulative' -
   
   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2006, rev. Apr. 2022       
*******************************************************!)

model "D-4 Bin packing (CP)"
 uses "kalis", "mmsystem"

 setparam("kalis_default_lb", 0)

 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

  save: array(FILES) of cpvar       ! Disk a file is saved on
  use: array(FILES) of cpvar        ! Space used by file on disk
  dur,e,s: array(FILES) of cpvar    ! Auxiliary arrays for 'cumulative'
  diskuse: cpvar                    ! Number of disks used

  Strategy: array(FILES) of cpbranching ! Enumeration
  FSORT: array(FILES) of integer
 end-declarations
 
 initializations from 'Data/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)

! Limit the number of disks used
 diskuse = maximum(save)

 forall(f in FILES) do
  setdomain(save(f), DISKS)         ! Every file onto a single disk
  use(f) = SIZE(f)
  dur(f) = 1
 end-do 

! Capacity limit of disks
 cumulative(save, dur, e, use, s, CAP)

! Definition of search (place largest files first)
 qsort(SYS_DOWN, SIZE, FSORT)       ! Sort files in decreasing order of size
 forall(f in FILES)
  Strategy(f):= assign_var(KALIS_SMALLEST_MIN, KALIS_MIN_TO_MAX, {save(FSORT(f))}) 
 cp_set_branching(Strategy)

! 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 | getsol(save(f))=d) write(" ",SIZE(f))
  writeln("  space used: ", sum(f in FILES | getsol(save(f))=d) SIZE(f))
 end-do
 
end-model