Loading and cutting problems
Description
| Problem name and type, features | Difficulty | Related examples |
| D‑1 | Wagon load balancing: Nonpreemptive scheduling on parallel machines | **** | |
|---|
| heuristic solution requiring sorting algorithm, formulation of maximin objective; nested subroutines: function returning heuristic solution value and sorting procedure, ceil, getsize, if-then, break, exit, all loop types (forall-do, repeat-until, while-do), setparam, qsort, cutoff value, loading a MIP start solution |
| D‑2 | Barge loading: Knapsack problem | ** | burglar1.mos, knapsack_graph.mos |
|---|
| incremental problem definition with 3 different objectives, procedure for solution printing |
| D‑3 | Tank loading: Loading problem | *** | |
|---|
| 2 objectives; data preprocessing, as, dynamic creation of variables, procedure for solution printing, if-then-else |
| D‑4 | Backing up files: Bin-packing problem | ** | binpacking_graph.mos |
|---|
| 2 versions of mathematical model, symmetry breaking; data preprocessing, ceil, range |
| D‑5 | Cutting sheet metal: Covering problem | * | g6transmit.mos, j2bigbro.mos |
|---|
| |
| D‑6 | Cutting steel bars for desk legs: Cutting-stock problem | ** | cutstock_graph.mos |
|---|
| set operation(s) on range sets, set of integer (data as set contents) |
Further explanation of this example:
'Applications of optimization with Xpress-MP', Chapter 9: Loading and cutting stock problems
Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
Data Files
d4backup.mos
(!******************************************************
Mosel Example Problems
======================
file d4backup.mos
`````````````````
Bin packing: backup of files onto external storage units
You would like to backup your 16 files onto external storage
units ('disks') with 1.44Gb of capacity. How should the files
be distributed in order to minimize the number of disks used?
This is a simple bin-packing problem since each file can only
be saved to one disk.
(c) 2008-2022 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002, rev. Mar. 2022
*******************************************************!)
model "D-4 Bin packing"
uses "mmxprs"
declarations
ND: integer ! Number of disks
FILES = 1..16 ! Set of files
DISKS: range ! Set of disks
CAP: integer ! Disk size
SIZE: array(FILES) of integer ! Size of files to be saved
end-declarations
initializations from '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
writeln("Calculated upper bound: ", ND)
declarations
ifsave: array(FILES,DISKS) of mpvar ! 1 if file saved on disk, 0 otherwise
diskuse: mpvar ! Number of disks used
end-declarations
! Limit the number of disks used
forall(f in FILES) diskuse >= sum(d in DISKS) d*ifsave(f,d)
! Every file onto a single disk
forall(f in FILES) sum(d in DISKS) ifsave(f,d) = 1
! Capacity limit of disks
forall(d in DISKS) sum(f in FILES) SIZE(f)*ifsave(f,d) <= CAP
forall(d in DISKS,f in FILES) ifsave(f,d) is_binary
! Minimize the total number of disks used
minimize(diskuse)
! Solution printing
writeln("Number of disks used: ", getobjval)
forall(d in 1..integer(getobjval)) do
write(d, ":")
forall(f in FILES | getsol(ifsave(f,d))>0) write(" ",SIZE(f))
writeln(" space used: ", getsol(sum(f in FILES) SIZE(f)*ifsave(f,d)))
end-do
end-model
|
