FICO
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

Description
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 User Guide', Section 5.4 Cumulative scheduling: discrete resources

d4backup2ka.zip[download all files]

Source Files

Data Files





d4backup2_ka.mos

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

   file d4backup2_ka.mos
   `````````````````````
   Bin packing: backup of files onto floppy disks
   - Alternative formulation using 'cumulative' -
   
   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2006, rev. Mar. 2013       
*******************************************************!)

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

Back to examples browserPrevious exampleNext example