| 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
|
|
| 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 -
(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) write( if(getsol(getstart(file(f)))=d , " "+SIZE(f), ""))
writeln(" space used: ",
sum(f in FILES | getsol(getstart(file(f)))=d) SIZE(f))
end-do
cp_show_stats
end-model
|
|
| d4backup3a_ka.mos |
(!******************************************************
Mosel Example Problems
======================
file d4backup3a_ka.mos
``````````````````````
Bin packing: backup of files onto floppy disks
- Alternative formulation using tasks,
user branching strategy -
(c) 2008 Artelys S.A. and Fair Isaac Corporation
*******************************************************!)
model "D-4 Bin packing (CP)"
uses "kalis", "mmsystem"
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,LS: cpvarlist
diskuse: cpvar ! Number of disks used
Strategy: array(range) of cpbranching
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
! 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)
! Define a branching strategy (place largest files first)
qsort(SYS_DOWN, SIZE, FSORT) ! Sort files in decreasing order of size
forall(f in FILES)
LS+=getstart(file(FSORT(f)))
Strategy(1):=assign_var(KALIS_INPUT_ORDER, KALIS_MIN_TO_MAX, LS)
(! Equivalent definition of the search strategy:
forall(f in FILES)
Strategy(f):=assign_var(KALIS_INPUT_ORDER, KALIS_MIN_TO_MAX,
{getstart(file(FSORT(f)))})
!)
(! Task-based search strategy formulation:
forall(f in FILES)
Strategy(f):=task_serialize(KALIS_SMALLEST_ECT, KALIS_MIN_TO_MAX,
KALIS_MIN_TO_MAX, {file(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(getstart(file(f)))=d , " "+SIZE(f), ""))
writeln(" space used: ",
sum(f in FILES | getsol(getstart(file(f)))=d) SIZE(f))
end-do
cp_show_stats
end-model
|
|
| d4backup3b_ka.mos |
(!******************************************************
Mosel Example Problems
======================
file d4backup3b_ka.mos
``````````````````````
Bin packing: backup of files onto floppy disks
- Alternative formulation using tasks,
scheduling search with user branching strategy -
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2006, rev. Mar. 2013
*******************************************************!)
model "D-4 Bin packing (CP)"
uses "kalis", "mmsystem"
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,LS: cpvarlist
diskuse: cpvar ! Number of disks used
Strategy: array(range) of cpbranching
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
! 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)
! Define a branching strategy (place largest files first)
qsort(SYS_DOWN, SIZE, FSORT) ! Sort files in decreasing order of size
forall(f in FILES)
LS+=getstart(file(FSORT(f)))
Strategy(1):= assign_var(KALIS_INPUT_ORDER, KALIS_MIN_TO_MAX, LS)
(! Alternatively: task-based branching strategy definition
forall(f in FILES)
Strategy(f):=task_serialize(KALIS_SMALLEST_ECT, KALIS_MIN_TO_MAX,
KALIS_MIN_TO_MAX, {file(FSORT(f))})
!)
cp_set_schedule_strategy(KALIS_INITIAL_SOLUTION, Strategy)
setparam("KALIS_VERBOSE_LEVEL", 2) ! Enable solver output printing
! 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) write( if(getsol(getstart(file(f)))=d , " "+SIZE(f), ""))
writeln(" space used: ",
sum(f in FILES | getsol(getstart(file(f)))=d) SIZE(f))
end-do
cp_show_stats
end-model
|
|
| d4backup3c_ka.mos |
(!******************************************************
Mosel Example Problems
======================
file d4backup3c_ka.mos
``````````````````````
Bin packing: backup of files onto floppy disks
- Alternative formulation using tasks,
selecting the propagation algorithm -
(c) 2008 Artelys S.A. and Fair Isaac Corporation
*******************************************************!)
model "D-4 Bin packing (CP)"
uses "kalis", "mmsystem"
parameters
ALG = KALIS_TASK_INTERVALS ! or: KALIS_TIMETABLING
end-parameters
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, ALG)
! 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
starttime:=gettime
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) write( if(getsol(getstart(file(f)))=d , " "+SIZE(f), ""))
writeln(" space used: ",
sum(f in FILES | getsol(getstart(file(f)))=d) SIZE(f))
end-do
writeln("Total time: ", gettime-starttime, "sec")
end-model
|
|
