
APL Software 
APL Software for Operations Research
Author: Dennis Bricker
The software below was developed using APL+Win Version 3.5 (a
Rapid Application Development tool available from APL2000,
Inc.). For further information about the APL language,
see the SIGAPL web page
or Jim Weigand's web
page.
In order to use the APL workspaces below in your Windows environment,
you must first:
 install the APL runtime interpreter aplwr.exe
(Save as "application" in a directory of your choice.
If this is done corectly, the icon of the file should appear
as an inverted triangle.)
 copy the interpreter's configuration file aplwr.INI
to your Windows or WinNT directory.
 copy two files to your System folder (within
your Windows or WinNT directory): Olepro32.dll
and Msvcrt40.dll.
 If you wish to display any APL code (e.g., the dynamic programming
models in DPLIB) you should also install the APLHELP
font in your font file within your Windows directory.
Note: the four files above are compressed and must be unzipped.
To run the code in a workspace, simply doubleclick or open
the workspace. A window will be opened, offering a menu from which
you can choose items. Or select "Run..." from the Start
menu, and enter the pathname of the interpreter and workspace
in the dialogue box. For example, if you have put the files in
a directory named APLWIN35 on drive D:
Please notify me if you encounter difficulties, such as the program's
terminating without warning. (It would be very helpful if you
can describe what you were doing at the time if this should happen.)
You might find the graphical user interface a bit cumbersome at
times, as I had to rewrite some of the code for the runtime version.
Copy the APL runtime workspaces into the same directory containing
the interpreter (aplwr.exe):
 ASSIGN.w3
solves "classical" linear assignment (or maxweight)
problems as well as bipartite maximum cardinality matching problems,
using algorithms appearing in the book Integer Programming,
by L. Wolsey, Chapter 4, sections 3 and 2 (pp. 55ff), respectively.
(last modified: 22 October 2001)
The user can enter data or randomly generate
problem data.
 ASTP.w3 demonstrates several
heuristic algorithms and a branchandbound algorithm for the
asymmetric traveling salesman problem. (last modified: 12
October 2003) The user can enter data or
randomly generate data. Algorithms include nearest neighbor,
farthest & nearest insertion, exchange algorithms, simulated
annealing, vertex penalty, as well as branch&bound using
assignment problem for computation of lower bounds. (Cf. also
STSP.w3 for symmetric problems.)
 BATCHDP.w3 Specialpurpose
dynamic programming algorithm for computing optimal lot size
given rejection rate and setup costs. (last modified 4 March
2002)
 CPL_XD.w3
, demonstrating both Benders' decomposition and crossdecomposition
(of van Roy) algorithms applied to the capacitated plant location
problem. (last modified: 29 May 2002)
The user can enter data for the problem,
or can randomly generate problem data. See CPL_XD.pdf
and CPLXD_example.pdf
for discussion of the crossdecomposition algorithm.
 CPL.w3,
Benders' decomposition algorithm applied to the capacitated plant
location problem. Requires that student
direct each step (solving master problem & solving subproblem)
in every iteration. See CPL_XD for a more automated implementation (last modified: 3 November 2003)
The user can enter data for the problem,
or can randomly generate problem data.
 CPLGA.w3, Benders'
decomposition algorithm applied to the capacitated plant location
problem, but with the option of using a genetic algorithm to
solve the master problems.
 CTMC.w3 Analysis of continuoustime
Markov chains (last modified: 31 January 2001)
Assumes finite number of states. Computation
of steadystate distribution. User can enter problem data or randomly
generate a Markov chain.
 DEA.w3
performs Data Envelopment Analysis, providing a means of estimating
the relative efficiencies of production units.(last modified:
30 September 2001)
 DEBRUIJN.w3 computes
some (n,2) de
Bruijn sequences exhibiting some characteristics (uniformity
& balance) which may be desirable in the design of experiments.
(last modified: 15 August 2001)
 DETREP.w3 uses deterministic
dynamic programming to find the optimal replacement policy for
a machine, given cost of a new machine, tradein
value of used machine, based upon age, and the operating cost
of a used machine, also based upon age. All parameters are assumed
to be known with certainty!(last modified: 27 November 2001).
 DPLIB.w3
Generalpurpose dynamic programming algorithm (both deterministic
& stochastic, with finite number of states & stages).
(last modified: 28 March 2002 ) The accompanying file DPMODELS
contains several examples, most of which allow the user to specify
parameters:
 Powerplant capacity planning
 Deterministic & stochastic production
planning with one product
 Stochastic production planning with 2
products
 Political redistricting
 One & Twodimensional knapsack problems
 Optimal system reliability with redundant
components
 Casino problem
 Quiz show
 American option pricing
Using these predefined DP Models
requires that you also download DPMODELS.sf
into your directory.
 FLOWSHOP.w3 schedules
jobs in a flowshop with 2 or 3 machines (i.e., each job visits
the same sequence of machines) so as to minimize makespan. Algorithms include Johnson's algorithm and, for the
3machine case, a branchandbound algorithm (last modified: 7 December 2001).
 GAP1.w3
and GAP2.w3
demonstrate two common Lagrangian relaxations (weak and strong,
respectively) of the Generalized Assignment Problem
(last modified: 18 October 2001) The user can enter data
for the problem, or can randomly generate problem data.
 GRG.w3 demonstrates the Generalized
Reduced Gradient algorithm for nonlinear minimization problems
(last modified: 12 October 2003) Unfortunately,
the runtime version does not allow the capability to enter one's
own problem definition. The files GRGTANK.sf
and GRGDAT.sf can be downloaded
to load and optimize.
 KNAP1.w3 One dimensional
knapsack problem, solved by either dynamic programming or branchandbound.
(last modified 17 October 2003.) The user can
enter data or randomly generate data.
 KNAP2D.w3
Two dimensional knapsack problem, solved by dynamic programming
(with 2dimensional state space) as well as Lagrangian relaxation
and surrogate relaxation. (last modified: 22 April 2001) The user can enter data or randomly generate data.
 LCP.w3 Complementary pivoting
algorithm for solution of quadratic programming problems. (last
modified: 1 October 2003)
 LOTS.w3 Lotsizing algorithms
for deterministic "lumpy" demand patterns: WagnerWhitin,
SilverMeal, Part Period Balancing, Period Order Quantity algorithms.
(last modified: 26 May 2003) The user can
enter the data or randomly generate the demand patterns.
 MARKOV.w3
Analysis of discretetime Markov chains. (last modified: 6
February 2002 )
Assumes finite number of states. Steadystate
distribution; computation of absorption probabilities. User can
enter problem data or randomly generate a Markov chain. Includes
Markov chain model of a periodicreview (s,S) inventory system
with backordering.
 MDP.w3
Solves Markov Decision Problems with infinitelymany discrete
time periods, with either average cost/period or total discounted
cost criteria. Three algorithms are demonstrated: Value Iteration,
Policy Iteration, and Linear Programming. (last modified:
28 March 2002) The user can enter problem
data, randomly generate problem data, or provide the parameters
to generate a MDP model for an inventory replenishment application
with backordering and demand having Poisson distribution. Click
here
for presentation of sample output for the inventory replenishment
model.
 MEk1NN.w3 Analysis of
a singleserver queue with finite source population and service
which is a sum of k tasks each having exponential distributions
(which may or may not be identicalif identical, service time
has an Erlangk distribution.) (last modified: 4 March 2002)
 NETWORKS.w3
demonstrates various algorithms for (directed and undirected)
networks, e.g., shortest path, minimum spanning tree, postman
problem (last modified: 21 September 2001)
The network can be entered by the
user or randomly generated.
 PFOLIO.w3 demonstrates
complementary pivoting method for solving quadratic programming
problems deriving from portfolio selection (selecting investments
to minimize variance of return, subject to a minimum acceptable
expected rate of return, given historical data). (last modified:
3 October 2003) User can enter his/her
own data, or generate data.
 POSYGP.w3
for solution of posynomial geometric programming problems. (last modified: 5 November 2003 )
Accompanying data file containing several
predefined GP models is GPMODELS.sf.
 PROBLIB.w3 computes some
probability distribution functions and inverses, as well as generates
random numbers. Included are the following distributions:
Binomial, Uniform, Poisson, Exponential, Erlang, Normal, Gumbel,
Pascal, Weibull. (last modified: 24 January 2002).
 QAP.w3 demonstrates some
algorithms for the Quadratic Assignment Problem,
including simulated annealing. The user may enter his/her own
data or generate random problems. (last modified: 5 November
2003)
 QCLD1 Discretetime onedimensional
DP with continuous variaables, quadratic objective, and linear
transition equations. (last modified 17 March 2002)
 QCLDN
Discretetime multidimensional DP with continuous variables
(QC/LD: quadratic criterion/linear dynamics). (last modified:
9 March 2002 ) (or QCLDN2,
an experimental version of QCLDN)
 QCLDAM.w3
Discretetime control of release of water from a network of reservoirs
(application of QC/LD model). (last modified: 22 November
2003)
 RANK.w3 demonstrates a branchandbound
algorithm for computing a ranking of objects, given pairwise
preferences expressed by a subject, so as to minimize the number
of discrepancies (i.e., instances in which A is ranked higher
than B but B was preferred to A). (last modified: 27 September
2001)
The algorithm is described in Chapter 2 of
Graph Theory in Operations Research, by T. B. Boffey (Macmillan
Press, London) 1982.
 SEARCH.w3 contains several
algorithms for unconstrained optimization: steepest
descent, Newton's method, conjugate gradient, DFP (a quasiNewton
method), & Powell's method. The current runtime version
does not allow you to enter the function definitions; load the
following files for some sample functions: ROSENB.sf,
NLPHW3.sf, ... (last
modified: 12 September 2003)
 SIGGP.w3 implements an
algorithm for solving signomial geometric programming problems,
using condensation to create a succession of posynomial approximations
to the signomial GP problem. The user can specify the starting
point for the algorithm, which influences the local optimum to
which the algorithm converges. No guarantee of global optimality
can be made! (last modified: 25 November 2003)
 SLPWR.w3
TwoStage Stochastic LP with Recourse, assuming finite set of
random scenarios. (last modified: 13 May 2002) Accompanying
data files are PAR.sf,
FARM1.sf,
and FARM2.sf.
PAR is the production planning problem for golf bags,
FARM1 is the planning problem of the farmer in the problem
of Birge & Louveaux, in which the technology matrix (coefficients
of first stage variables in second stage) are random, while FARM2
is a modification of the farmer's planning problem (with random
objective and righthandside as well). Allows for random generation
of test problems. Click here for presentations of sample output
from the PAR
and FARM2
examples.
 SLPWSR.w3
Stochastic LP with Simple Recourse (2 stages).
(last modified: 5 May 2002)
Uses separable programming LP to find the
minimum expected cost. Assumes that only righthandsides are
random, with probability distributions which are either discrete,
or continuous (normal). When the probability distribution is
normal, a gridrefinement (columngeneration) algorithm is used.
Allows random generation of stochastic transportation problems.
 SLPWR_SD.w3
Stochastic LP with Recourse Stochastic Decomposition
(last modified: 13 May 2002)
Uses Benders' decomposition to approximately
solve the problem in which the righthandsides are continuous
normallydistributed independent random variables. Uses the Stochastic
Decomposition algorithm of Higle and Sens. Click
here
for presentation of sample output from a stochastic transportation
problem (data file: STPC.sf)
 SOSLP.w3 Demonstrates the
restricted basis entry rule for adapting the simplex LP algorithm
to solve problems with piecewise linear functions (either convex,
concave, or neither). These functions are modeled using Special
Ordered Sets of Type 2. (Current version accepts piecewiselinear
functions in objective only.)
 STOPLOSS.w3 computes
upper & lower bounds on the stoploss insurance premium, given
past claim data in the form of numbers of claims observed in
each of a finite number of intervals (cells). The extremal distribution
yielding the upper or lower bounds may be restricted to be within
a certain "distance" of the historical claim distribution,
where "distance" may be
measured by:
> the Chisquare statistic
> the "modified" Chisquare statistic
> the Idivergence.
(Last modified: 6 June 2002.)
 STSP.w3 demonstrates several
heuristic algorithms and a branchandbound algorithm for the
symmetric traveling salesman problem. (last modified: 12 October
2003) The user can enter data or randomly
generate data. Algorithms include nearest neighbor, farthest
& nearest insertion, exchange algorithms, simulated annealing,
vertex penalty, as well as branch&bound using vertex penalty
algorithm for computation of lower bounds. (Cf. also ATSP.w3
for asymmetric problems.)
 TRIM.w3 solves the onedimensional
"trim" or "cutting stock" problem, using
an LP model with columns generated by solving knapsack problems.
(last modified: 26 May 2003) The user
can enter data or randomly generate data.
 TRANSPORT.w3
solves the "classical" transportation problem with
or without capacity constraints on the individual shipments.
Also illustrates Vogel's Approximation Method (VAM) and NorthwestCorner
Method. (last modified: 3 October 2001) The
user can enter data or randomly generate data.
 UBT.w3 is an implementation
of the "Upper Bounding Technique", a variation of the
revised simplex method which more efficiently handles upper &/or
lower bounds on the variables.(last modified: 28 August 2002)
The current version assumes equality constraints,
so that the user must explicitly define slack &/or surplus
variables. (These can be given upper bounds in order to constrain
a linear function to lie in some bounded interval.)
 WEBER.w3 addresses Weber's
problem of locating a single facility in the plane so as to minimize
the sum of shipping costs to customers (assumed to be proportional
to Euclidean distances). A heuristic is also included for the
multifacility location/allocation problem. (Last modified
5 November 2003.) The user can enter data or
randomly generate data.
To run the code in a workspace, simply doubleclick or open
the workspace. A window will be opened, offering a menu from which
you can choose items.
Please notify me if you encounter difficulties, such as the program's
terminating without warning. (It would be helpful if you can describe
what you were doing at the time if this should happen.) You might
find the graphical user interface a bit cumbersome at times, as
I had to rewrite some of the code for the runtime version.
These workspaces were written for educational purposes only,
to demonstrate the various algorithms using small examples.
to Dennis Bricker's
home page
http://www.engineering.uiowa.edu/~dbricker/APL_software.html
dennisbricker@uiowa.edu
Last modified: 31 August 2004