 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Description
D‑1 D‑2 D‑3 D‑4 Problem name and type, features Difficulty Related examples 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 Barge loading: Knapsack problem ** burglar1.mos, knapsack_graph.mos incremental problem definition with 3 different objectives, procedure for solution printing Tank loading: Loading problem *** 2 objectives; data preprocessing, as, dynamic creation of variables, procedure for solution printing, if-then-else Backing up files: Bin-packing problem ** binpacking_graph.mos 2 versions of mathematical model, symmetry breaking; data preprocessing, ceil, range Cutting sheet metal: Covering problem * g6transmit.mos, j2bigbro.mos 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

d1wagon.mos

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

file d1wagon.mos


Sixteen boxes must be loaded on three railway wagons.
Each wagon has a weight limit of 100 quintals. Which wagon
should each box be assigned so that the heaviest wagon load
is minimized.

A heuristic solution can be found by distributing all boxes
to wagons by assigning the heaviest box to the least loaded
wagon. This requires the boxes to be in order of decreasing
weight. The sorting procedure introduces 'getsize', and nested
'repeat-until', 'forall-do', and 'while' loops with break
condition. The implementation of the heuristic also introduces
the subroutine type 'function' to return the highest wagon load
weight.

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Mar. 2002
*******************************************************!)

uses "mmxprs"

forward function solveheur:real
forward procedure shellsort(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

ifload: 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 solveheur<=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) ifload(b,w) = 1

! Limit the weight loaded into every wagon
forall(w in WAGONS) sum(b in BOXES) WEIGHT(b)*ifload(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) ifload(b,w) is_binary

! Alternative to lower bound on maxweight: adapt the optimizer cutoff value

! Uncomment the following line to see the optimizer log
setparam("XPRS_VERBOSE",true)

minimize(maxweight)                    ! Start optimization

! Solution printing
writeln("Optimal solution:\n Max weight: ", getobjval)
forall(w in WAGONS) do
write(" ", w, ":")
forall(b in BOXES | ifload(b,w).sol=1) write(" ", b)
writeln(" (total weight: ", getsol(sum(b in BOXES) WEIGHT(b)*ifload(b,w)), ")")
end-do

!-----------------------------------------------------------------

(! LPT (Longest processing time) heuristic:
One at a time place the heaviest unassigned box onto the wagon with
!)

function solveheur:real
declarations
ORDERW: array(BOXES) of integer      ! Box indices in decreasing weight order
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
shellsort(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
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 shellsort(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   