| 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)<CurWeight(w), v, w)
CurNum(v)+=1 ! Increase the counter of boxes on v
Load(v,CurNum(v)):=ORDERW(b) ! Add box to the wagon
CurWeight(v)+=WEIGHT(ORDERW(b)) ! Update current weight of the wagon
end-do
returned:= max(w in WAGONS) CurWeight(w) ! Return the solution value
! Solution printing
writeln("Heuristic solution:\n Max weight: ", returned)
forall(w in WAGONS) do
write(" ", w, ":")
forall(b in 1..CurNum(w)) write(" ", Load(w,b))
writeln(" (total weight: ", CurWeight(w), ")")
end-do
end-function
!-----------------------------------------------------------------
(! Sort an array in decreasing order using a Shell sort method:
* First sort, by straight insertion, small groups of numbers.
* Next, combine several small groups and sort them (possibly
repeat this step).
* Finally, sort the whole list of numbers.
The spacings between the numbers of groups sorted during each
pass through the data are called the increments. A good choice
is the sequence which can be generated by the recurrence
i(1)=1, i(k+1)=3i(k)+1, k=1,2,...
The implementation assumes that the indices of the array to sort
have the values 1,...,N. The array to be sorted (first argument)
remains unchanged, instead, we reorder the array of indices (second
argument).
!)
procedure shell_sort(A:array(range) of integer, I:array(range) of integer)
N:=getsize(I)
inc:=1 ! Determine the starting increment
repeat
inc:=3*inc+1
until (inc>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))<A(v)) do ! Inner loop of straight insertion
I(j):=I(j-inc)
j -= inc
if j<=inc then break; end-if
end-do
I(j):= v
end-do
until (inc<=1)
end-procedure
end-model
|
|
| 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)<CurWeight(w), v, w)
CurNum(v)+=1 ! Increase the counter of boxes on v
Load(v,CurNum(v)):=ORDERW(b) ! Add box to the wagon
CurWeight(v)+=WEIGHT(ORDERW(b)) ! Update current weight of the wagon
end-do
returned:= max(w in WAGONS) CurWeight(w) ! Return the solution value
! Solution printing
writeln("Heuristic solution:\n Max weight: ", returned)
forall(w in WAGONS) do
write(" ", w, ":")
forall(b in 1..CurNum(w)) write(" ", Load(w,b))
writeln(" (total weight: ", CurWeight(w), ")")
end-do
! Save the heuristic solution
forall(w in WAGONS,b in 1..CurNum(w)) HeurSol(Load(w,b)):= w
end-function
!-----------------------------------------------------------------
(! Optimizer callback function:
Report on the use of the user solution (optional logging function)
!)
public procedure solnotify(id:string, status:integer)
writeln("Optimiser loaded solution '", id, "' status=", status)
end-procedure
end-model
|
|
| 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
|
|
