| d1wagon.mos |
(!******************************************************
Mosel Example Problems
======================
file d1wagon.mos
````````````````
Load balancing of train wagons
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "D-1 Wagon load balancing"
uses "mmxprs"
forward function solve_heur:real
forward procedure shell_sort(A:array(range) of integer,
I:array(range) of integer)
declarations
BOXES = 1..16 ! Set of boxes
WAGONS = 1..3 ! Set of wagons
WEIGHT: array(BOXES) of integer ! Box weights
WMAX: integer ! Weight limit per wagon
load: array(BOXES,WAGONS) of mpvar ! 1 if box loaded on wagon, 0 otherwise
maxweight: mpvar ! Weight of the heaviest wagon load
end-declarations
initializations from 'd1wagon.dat'
WEIGHT WMAX
end-initializations
! Solve the problem heuristically and terminate the program if the
! heuristic solution is good enough
if solve_heur<=WMAX then
writeln("Heuristic solution fits capacity limits")
exit(0)
end-if
! Every box into one wagon
forall(b in BOXES) sum(w in WAGONS) load(b,w) = 1
! Limit the weight loaded into every wagon
forall(w in WAGONS) sum(b in BOXES) WEIGHT(b)*load(b,w) <= maxweight
! Bounds on maximum weight
maxweight <= WMAX
maxweight >= ceil((sum(b in BOXES) WEIGHT(b))/3)
forall(b in BOXES,w in WAGONS) load(b,w) is_binary
! Alternative to lower bound on maxweight: adapt the optimizer cutoff value
! setparam("XPRS_MIPADDCUTOFF",-0.99999)
! Uncomment the following line to see the optimizer log
setparam("XPRS_VERBOSE",true)
! Minimize the heaviest load
minimize(maxweight) ! Start optimization
! Solution printing
writeln("Optimal solution:\n Max weight: ", getobjval)
forall(w in WAGONS) do
write(" ", w, ":")
forall(b in BOXES) write(if(getsol(load(b,w))=1, " "+b, ""))
writeln(" (total weight: ", getsol(sum(b in BOXES) WEIGHT(b)*load(b,w)), ")")
end-do
!-----------------------------------------------------------------
(! LPT (Longest processing time) heuristic:
One at a time place the heaviest unassigned box onto the wagon with
the least load
!)
function solve_heur:real
declarations
ORDERW: array(BOXES) of integer ! Box indices in decreasing weight order
Load: array(WAGONS,range) of integer ! Boxes loaded onto the wagons
CurWeight: array(WAGONS) of integer ! Current weight of wagon loads
CurNum: array(WAGONS) of integer ! Current number of boxes per wagon
end-declarations
! Copy the box indices into array ORDERW and sort them in decreasing
! order of box weights (the sorted indices are returned in array ORDERW)
forall(b in BOXES) ORDERW(b):=b
shell_sort(WEIGHT,ORDERW)
! Distribute the loads to the wagons using the LPT heuristic
forall(b in BOXES) do
v:=1 ! Find wagon with the smallest load
forall(w in WAGONS) v:=if(CurWeight(v)N)
repeat ! Loop over the partial sorts
inc:=inc div 3
forall(i in inc+1..N) do ! Outer loop of straight insertion
v:=I(i)
j:=i
while (A(I(j-inc)) |
|
| d1wagon2.mos |
(!******************************************************
Mosel Example Problems
======================
file d1wagon2.mos
`````````````````
Load balancing of train wagons
(second version, using heuristic solution as
start solution for MIP via 'addmipsol')
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Sep. 2007, rev. Feb. 2013
*******************************************************!)
model "D-1 Wagon load balancing (2)"
uses "mmxprs", "mmsystem"
forward function solve_heur:real
declarations
BOXES = 1..16 ! Set of boxes
WAGONS = 1..3 ! Set of wagons
WEIGHT: array(BOXES) of integer ! Box weights
WMAX: integer ! Weight limit per wagon
load: array(BOXES,WAGONS) of mpvar ! 1 if box loaded on wagon, 0 otherwise
maxweight: mpvar ! Weight of the heaviest wagon load
MaxWeight: linctr ! Objective function
HeurSol: array(BOXES) of integer ! Heuristic solution
AllSol: array(mpvar) of real ! Start solution for MIP
end-declarations
initializations from 'd1wagon.dat'
WEIGHT WMAX
end-initializations
! Solve the problem heuristically and terminate the program if the
! heuristic solution is good enough, otherwise, load heuristic solution
! as start solution into the Optimizer
if solve_heur<=WMAX then
writeln("Heuristic solution fits capacity limits")
exit(0)
end-if
! Every box into one wagon
forall(b in BOXES) sum(w in WAGONS) load(b,w) = 1
! Limit the weight loaded into every wagon
forall(w in WAGONS) sum(b in BOXES) WEIGHT(b)*load(b,w) <= maxweight
! Lower bound on maximum weight
maxweight >= ceil((sum(b in BOXES) WEIGHT(b))/3)
forall(b in BOXES,w in WAGONS) load(b,w) is_binary
! Alternative to lower bound on maxweight: adapt the optimizer cutoff value
! setparam("XPRS_MIPADDCUTOFF",-0.99999)
! Uncomment the following line to see the optimizer log
! setparam("XPRS_VERBOSE",true)
! Set the solution values for all discrete variables that are non-zero
forall(b in BOXES) AllSol(load(b,HeurSol(b))):= 1
! Minimize the heaviest load
MaxWeight:= maxweight ! Objective must be a constraint
! otherwise 'minimize' reloads problem
loadprob(MaxWeight) ! Load problem into the Optimizer
addmipsol("HeurSol", AllSol) ! Load the heuristic solution
setcallback(XPRS_CB_SOLNOTIFY,"solnotify") ! Reporting use of user solution
! Re-inforce use of user solution in local search heuristics
setparam("XPRS_USERSOLHEURISTIC",3)
minimize(MaxWeight) ! Start optimization
! Solution printing
writeln("Optimal solution:\n Max weight: ", getobjval)
forall(w in WAGONS) do
write(" ", w, ":")
forall(b in BOXES) write(if(getsol(load(b,w))=1, " "+b, ""))
writeln(" (total weight: ", getsol(sum(b in BOXES) WEIGHT(b)*load(b,w)), ")")
end-do
!-----------------------------------------------------------------
(! LPT (Longest processing time) heuristic:
One at a time place the heaviest unassigned box onto the wagon with
the least load
!)
function solve_heur:real
declarations
ORDERW: array(BOXES) of integer ! Box indices in decreasing weight order
Load: array(WAGONS,range) of integer ! Boxes loaded onto the wagons
CurWeight: array(WAGONS) of integer ! Current weight of wagon loads
CurNum: array(WAGONS) of integer ! Current number of boxes per wagon
end-declarations
! Copy the box indices into array ORDERW and sort them in decreasing
! order of box weights (the sorted indices are returned in array ORDERW)
forall(b in BOXES) ORDERW(b):=b
qsort(SYS_DOWN, WEIGHT,ORDERW)
! Distribute the loads to the wagons using the LPT heuristic
forall(b in BOXES) do
v:=1 ! Find wagon with the smallest load
forall(w in WAGONS) v:=if(CurWeight(v)
|
| d2ship.mos |
(!******************************************************
Mosel Example Problems
======================
file d2ship.mos
```````````````
Choice of wheat load for a ship
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "D-2 Ship loading"
uses "mmxprs"
forward procedure print_sol(num:integer)
declarations
CLIENTS = 1..7 ! Set of clients
AVAIL: array(CLIENTS) of integer ! Number of lots per client
SIZE: array(CLIENTS) of integer ! Lot sizes
PRICE: array(CLIENTS) of integer ! Prices charged to clients
COST: array(CLIENTS) of integer ! Cost per client
PROF: array(CLIENTS) of integer ! Profit per client
CAP: integer ! Capacity of the ship
load: array(CLIENTS) of mpvar ! Lots taken from clients
end-declarations
initializations from 'd2ship.dat'
AVAIL SIZE PRICE COST CAP
end-initializations
forall(c in CLIENTS) PROF(c):= PRICE(c) - COST(c)*SIZE(c)
Profit:= sum(c in CLIENTS) PROF(c)*load(c)
! Limit on the capacity of the ship
sum(c in CLIENTS) SIZE(c)*load(c) <= CAP
! Problem 1: unlimited availability of lots at clients
maximize(Profit)
print_sol(1)
! Problem 2: limits on availability of lots at clients
forall(c in CLIENTS) load(c) <= AVAIL(c)
maximize(Profit)
print_sol(2)
! Problem 3: lots must be integer
forall(c in CLIENTS) load(c) is_integer
maximize(Profit)
print_sol(3)
!-----------------------------------------------------------------
! Solution printing
procedure print_sol(num:integer)
writeln("Problem ", num, ": profit: ", getobjval)
forall(c in CLIENTS)
write( if(getsol(load(c))>0 , " " + c + ":" + getsol(load(c)), ""))
writeln
end-procedure
end-model
|
|
| d3tanks.mos |
(!******************************************************
Mosel Example Problems
======================
file d3tanks.mos
````````````````
Loading of liquid chemicals into tanks
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "D-3 Tank loading"
uses "mmxprs"
forward procedure print_sol
declarations
TANKS: range ! Set of tanks
LIQ: set of string ! Set of liquids
CAP: array(TANKS) of integer ! Tank capacities
TINIT: array(TANKS) of string ! Initial tank contents type
QINIT: array(TANKS) of integer ! Quantity of initial contents
ARR: array(LIQ) of integer ! Arriving quantities of chemicals
REST: array(LIQ) of integer ! Rest after filling part. filled tanks
load: dynamic array(LIQ,TANKS) of mpvar ! 1 if liquid loaded into tank,
! 0 otherwise
end-declarations
initializations from 'd3tanks.dat'
CAP ARR
[TINIT, QINIT] as 'FILLED'
end-initializations
finalize(LIQ)
forall(t in TANKS | QINIT(t)=0, l in LIQ) do
create(load(l,t))
load(l,t) is_binary
end-do
! Complete the initially partially filled tanks and calculate the remaining
! quantities of liquids
forall(l in LIQ)
REST(l):= ARR(l) - sum(t in TANKS | TINIT(t)=l) (CAP(t)-QINIT(t))
! Objective 1: total tank capacity used
TankUse:= sum(l in LIQ, t in TANKS) CAP(t)*load(l,t)
! Objective 2: number of tanks used
TankNum:= sum(l in LIQ, t in TANKS) load(l,t)
! Do not mix different liquids
forall(t in TANKS) sum(l in LIQ) load(l,t) <= 1
! Load the empty tanks within their capacity limits
forall(l in LIQ) sum(t in TANKS) CAP(t)*load(l,t) >= REST(l)
! Solve the problem with objective 1
minimize(TankUse)
! Solution printing
print_sol
! Solve the problem with objective 2
minimize(TankNum)
! Solution printing
print_sol
!-----------------------------------------------------------------
! Solution printing
procedure print_sol
writeln("Used capacity: ", getsol(TankUse) +
sum(t in TANKS | QINIT(t)>0) CAP(t),
" Capacity of empty tanks: ", sum(t in TANKS) CAP(t) -
getsol(TankUse) -
sum(t in TANKS | QINIT(t)>0) CAP(t))
writeln("Number of tanks used: ", getsol(TankNum) +
sum(t in TANKS | QINIT(t)>0) 1)
forall(t in TANKS)
if(QINIT(t)=0) then
write(t, ": ")
forall(l in LIQ) write( if(getsol(load(l,t))>0 , l, ""))
writeln
else
writeln(t, ": ", TINIT(t))
end-if
end-procedure
end-model
|
|
| d4backup.mos |
(!******************************************************
Mosel Example Problems
======================
file d4backup.mos
`````````````````
Bin packing: backup of files onto floppy disks
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "D-4 Bin packing"
uses "mmxprs"
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
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
declarations
save: 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*save(f,d)
! Every file onto a single disk
forall(f in FILES) sum(d in DISKS) save(f,d) = 1
! Capacity limit of disks
forall(d in DISKS) sum(f in FILES) SIZE(f)*save(f,d) <= CAP
forall(d in DISKS,f in FILES) save(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) write( if(getsol(save(f,d))>0 , " "+SIZE(f), ""))
writeln(" space used: ", getsol(sum(f in FILES) SIZE(f)*save(f,d)))
end-do
end-model
|
|
| d5cutsh.mos |
(!******************************************************
Mosel Example Problems
======================
file d5cutsh.mos
````````````````
Cutting of sheet metal
(2-dimensional cutting patterns)
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "D-5 Sheet metal cutting"
uses "mmxprs"
declarations
PATTERNS = 1..16 ! Set of cutting patterns
SIZES = 1..4 ! Set of sheet sizes
DEM: array(SIZES) of integer ! Demands for the different sizes
CUT: array(SIZES,PATTERNS) of integer ! Cutting patterns
use: array(PATTERNS) of mpvar ! Use of cutting patterns
end-declarations
initializations from 'd5cutsh.dat'
DEM CUT
end-initializations
! Objective: total number of sheets used
Sheets:= sum(p in PATTERNS) use(p)
! Satisfy demands
forall(s in SIZES) sum(p in PATTERNS) CUT(s,p)*use(p) >= DEM(s)
forall(p in PATTERNS) use(p) is_integer
! Solve the problem
minimize(Sheets)
! Solution printing
writeln("Total number of large sheets: ", getobjval)
write("Cutting patterns used: ")
forall(p in PATTERNS)
write( if(getsol(use(p)) > 0 , " " + p + ":" + getsol(use(p)), "") )
write("\nExemplaries of sheets sizes cut: ")
forall(s in SIZES)
write(s, ":", getsol(sum(p in PATTERNS) CUT(s,p)*use(p)), " ")
writeln
end-model
|
|
| d6cutbar.mos |
(!******************************************************
Mosel Example Problems
======================
file d6cutbar.mos
`````````````````
Cutting of steel bars into school desk legs
(1-dimensional cutting patterns)
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)
model "D-6 Cutting steel bars"
uses "mmxprs"
declarations
PAT1 = 1..6; PAT2 = 7..12 ! Sets of cutting patterns
PATTERNS = PAT1 + PAT2 ! Set of all cutting patterns
SIZES: set of integer ! Desk heights
DEM: array(SIZES) of integer ! Demands for the different heights
CUT: array(PATTERNS,SIZES) of integer ! Cutting patterns
LEN: array(range) of integer ! Lengths of original steel bars
use: array(PATTERNS) of mpvar ! Use of cutting patterns
end-declarations
initializations from 'd6cutbar.dat'
DEM CUT LEN
end-initializations
! Objective: total loss
Loss:= sum(p in PAT1) LEN(1)*use(p) + sum(p in PAT2) LEN(2)*use(p) -
sum(s in SIZES) 4*DEM(s)*s
! Satisfy demands
forall(s in SIZES) sum(p in PATTERNS) CUT(p,s)*use(p) >= 4*DEM(s)
forall(p in PATTERNS) use(p) is_integer
! Solve the problem
minimize(Loss)
! Solution printing
writeln("Loss: ", getobjval, "cm")
write("Short bars: ", getsol(sum(p in PAT1) use(p)))
writeln(", long bars: ", getsol(sum(p in PAT2) use(p)))
write("Cutting patterns used:")
forall(p in PATTERNS)
write( if(getsol(use(p)) > 0 , " " + p + ":" + getsol(use(p)), "") )
write("\nNumbers of legs cut: ")
forall(s in SIZES)
write(s, ":", getsol(sum(p in PATTERNS) CUT(p,s)*use(p)), " ")
writeln
end-model
|
|
