FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Backing up files: scheduling with cumulative resource constraints

Binpacking problem modeled as cumulative scheduling problem.
  • First formulation with 'cumulative' constraints, defining a search strategy for variables (d4backup2_ka.mos).
  • Alternative formulation using task and resource objects; implementing a variable-based search strategy (d4backup3a_ka.mos and d4backup3b_ka.mos)
  • or using the default scheduling search (d4backup3_ka.mos).
  • Model version d4backup3c_ka.mos shows how to change the propagation algorithm for resource constraints.
Further explanation of this example: 'Xpress Kalis Mosel User Guide', Section 5.4 Cumulative scheduling: discrete resources[download all files]

Source Files

Data Files


   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)

  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
 initializations from 'Data/d4backup.dat'

! Provide a sufficiently large number of disks
 ND:= ceil((sum(f in FILES) SIZE(f))/CAP)
 DISKS:= 1..ND

! 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

! 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))}) 

! Minimize the total number of disks used
 if not cp_minimize(diskuse) then
  writeln("Problem infeasible")
! 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))

Back to examples browserPrevious exampleNext example