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

d4backup2ka.zip[download all files]

Source Files

Data Files





d4backup3_ka.mos

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

   file d4backup3_ka.mos
   `````````````````````
   Bin packing: backup of files onto floppy disks
   - Alternative formulation using tasks,
     default branching strategy -
   
   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       
*******************************************************!)

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

  file: array(FILES) of cptask       ! Tasks (= files to be saved)
  disks: cpresource                  ! Resource representing disks
  L: cpvarlist
  diskuse: cpvar                     ! Number of disks used
 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

! Setting up the resource (capacity limit of disks)
 set_resource_attributes(disks, KALIS_DISCRETE_RESOURCE, CAP)
 
! Setting up the tasks
 forall(f in FILES) do
  setdomain(getstart(file(f)), DISKS)           ! Start time (= choice of disk)
  set_task_attributes(file(f), disks, SIZE(f))  ! Resource (disk space) req.
  set_task_attributes(file(f), 1)    ! Duration (= number of disks used)
 end-do

! Limit the number of disks used
 forall(f in FILES) L += getstart(file(f))
 diskuse = maximum(L)

! Minimize the total number of disks used
 if cp_schedule(diskuse) = 0 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(file(f).start)=d) write(" ",SIZE(f))
  writeln("  space used: ",
          sum(f in FILES | getsol(file(f).start)=d) SIZE(f))
 end-do
 cp_show_stats

end-model

Back to examples browserPrevious exampleNext example