OPERA TB - A MATLAB Toolbox for Operational Analysis

At the Department of Mathematics and Physics (IMa)

The MATLAB toolbox OPERATB 1.0 is part of TOMLAB. OPERA is a set of MATLAB m-files, which solves many basic optimization problems in operations research and mathematical programming. The focus is on dense problems. Included are routines for linear programming (LP), network programming (NP), integer programming (IP) and dynamic programming (DP). The focus is on dense problems. The toolbox is running in both MATLAB 5.1 and MATLAB 4.2c and works on both PC (NT4.0, Win95, Windows 3.11) and Unix systems (SUN, HP).

The MATLAB toolbox OPERA TB is a set of MATLAB m-files, which solves many basic optimization problems in operations research and mathematical programming. Included are routines for linear programming (LP), network programming (NP), integer programming (IP) and dynamic programming (DP). The focus is on dense problems, but sparse LP problems may be solved calling the commercial solver MINOS.

Linear Programming problems may either be solved using an interactive menu program (lpopt), or solved by direct call to a parameter driven driver routine (lpRun). In either case the problem may be solved using any of the installed optimization solvers. OPERA has its own solvers, but may also call solvers in MathWorks Optimization Toolbox (if this toolbox is installed) as well as many FORTRAN/C codes using MEX-file interfaces.

A MEX-file interface for both PC and Unix has been developed for the commercial optimization code MINOS , used both for linear programming and nonlinear programming (in NLPLIB TB 1.0). MEX-file interfaces working on both PC and Unix have also been developed for the commercial codes from the Systems Optimization Laboratory (SOL) NPSOL, NPOPT, LPSOL and NLSSOL(all of them also present in the NAG library, with other names). The aim is to expand this list in the near future.

The internal solvers in OPERA solve LP-problems using the simplex method, the primal dual simplex method and interior points methods like Karmakar's method.

For NP-problems OPERA TB has three starting point methods for the transport problem (TP) and the transport simplex method, three shortest path algorithms and the Ford & Fulkersons' augmenting path algorithm to solve maximum flow problems. Included is also a routine to find the minimum spanning tree of an undirected graph and a network simplex algorithm to solve the Minimum Cost Network Flow Problem (MCNFP). The symmetric travelling salesman problem is solved using Lagrangian Relaxation and the subgradient method using Polyak rule II.

The IP-problems are either solved with a branch and bound algorithm or a simple implementation of the Gomorov cutting plane method. A routine to solve 0/1 IP with Balas method is also included..

As example of dynamic programming algorithms one routine solving knapsack problems and one routine solving deterministic inventory problems are implemented.

Many files which run simple tests on the different solvers are included ( in a separate directory operdemo). The test examples are mainly exercises from the books by Luenberger (Linear and Nonlinear Optimization) and Winston (Operations Research - Applications and Algorithms) and from course material used in optimization courses at Linköping University.

Some predefined linear programming test examples are included, which are used by the menu program and the driver routine. The aim is to expand this set in the future, to get a set of interesting test problems. It is very easy to define your own problems to be solved by the menu program and the driver.

OPERA TB 1.0 is developed by Kenneth Holmström, project leader of the Applied Optimization and Modeling (TOM) profile research area at Mälardalen University. It has been used for several years in optimization courses both at Mälardalen University and at Uppsala University.

OPERA TB 1.0 is distributed free of charge for academic purposes. Always cite the following reference::

Kenneth Holmström: OPERA TB 1.0 - A MATLAB Toolbox for Optimization Algorithms in Operations Research, Technical Report IMa-TOM -97-1, Department of Mathematics and Physics, Mälardalen University, Sweden.

Overview of OPERA TB 1.0

Installation on PC systems: OPERA is normally installed as part of TOMLAB, normally \matlab\tomlab\opera or \matlab\toolbox\tomlab\opera. This path must be added to the MATLABPATH. Before starting any OPERA routines, call operaini, which sets the number of columns and declares the global variables used. If you have a screen with more than 80 columns, change the variable MAXCOLS in operaini.m to the correct number.

Installation on Unix systems: OPERA is normally installed as part of TOMLAB, usually in a directory like /home/tomlab/opera or /home/matlab/toolbox/tomlab/opera. This path must be added to the MATLABPATH. Before starting any OPERA routines, call operaini, which sets the number of columns and declares the global variables used. If you have a screen with more than 80 columns, change the variable MAXCOLS operaini.m to the correct number.

If OPERA is installed as a standalone toolbox, the following routines from the NLPLIB toolbox must be included: inputV and inputSet.

In the following we describe OPERA TB 1.0 by giving tables describing all MATLAB functions and some short selected comments. The first table describes the two menu programs currently present in the toolbox.

Menu Programs Description
lpopt.m Menu program for linear programming(LP) problems
simplex.m Interactive input of an LP on canonical standard form

The menu program lpopt calls the driver routine lpRun in the next table. The simple menu program simplex only calls the internal OPERA solvers lpsimp1 and lpsimp2.

Driver Routines Description
lpRun.m Driver to solve predefined or user defined LP problems

Like MathWorks Optimization Toolbox, OPERA and NLPLIB are using a default vector with optimization parameters. In Optimization Toolbox, this routine is called foptions and is using a vector with length 18. Our solvers need more parameters, currently 29, and therefore the routine goptions, which is part of NLPLIB, is defined. In OPERA the routine lpDef (see the Utility table below) calls goptions. Both lpopt and lpRun are using lpDef to setup the default parameter vector.

The internal linear programming solvers lpsimp1, lpsimp2 and lpdual all have three rules for variable selection implemented. Blands rule is the choice if fear of cycling exists. There are two variants of minimum cost variable selection, one which sorts the variables increasing in each step (the default choice) and one whichs corresponds to Dantzigs' original rule. The table also describes the routines which implements two Karmakar type of inner point methods.

Linear Programming Description
lpsimp1.m The phase I simplex algorithm. Find basic feasible solution (bfs). Using Blands rule and two variants of the Minimum Cost rule for variable selection, sort variables increasing (default) and Dantzigs' original rule.
lpsimp2.m The phase II simplex algorithm (revised simplex algorithm). Using Blands rule and two variants of the Minimum Cost rule for variable selection (default)
lpdual.m The primal dual simplex algorithm.
karmark.m Karmakar's algorithm (from Todd/Goldfarb). Kanonical form.
lpkarma.m Input: LP on equality form. Converts and calls karmark.m
akarmark.m Affine scaling variant of Karmarkars algorithm

Implemented in OPERA are three routines to find a starting basis for the transportation problem and one routine to solve the problem, see the table below.

Transportation Programming Description
TPnw.m Find bfs to TP using Northwest Corner Method
TPmc.m Find bfs to TP using Minimum Cost Method
TPvogel.m Find bfs to TP using Vogel's Method
TPsimplx.m Simplex for TP (Transportation Problem)

The routines for network programming are using the forward reverse star data representation technique.

Network Programming Description
gsearch.m Searching all reachable nodes in a network. Stack approach.
gsearchq.m Searching all reachable nodes in a network. Queue approach
mintree.m Finds the minimum spanning tree of an undirected graph.
dijkstra.m Shortest path using Dijkstras algorithm
labelcor.m Shortest path using a label correcting algorithm
modlabel.m Shortest path using a modified label correcting algorithm
maxflow.m Maximum flow using Ford and Fulkersons' augmenting path algorithm
salesman.m Symmetric Travelling Salesman Problem (TSP) solver using Lagrangian Relaxation and the Subgradient Method with Polyak rule II
nwsimplx.m Minimum Cost Network Flow Problems (MCNFP) by the Network Simplex Algorithm

OPERA has two routines for pure integer programs (IP) and one for pure binary IP, given in the next table.

Integer Programming Description
cutplane.m Gomorovs' cutting plane algorithm for Integer Programs (IP)
branch.m Branch and bound for Integer Programs (IP)
balas.m Branch and bound algorithm for binary IP using Balas method.

Two simple implementations of dynamic programming algorithms are described in the table below.

Dynamic Programming Description
dpinvent.m Dynamic programming algorithm for the inventory problem
dpknap.m Dynamic programming algorithm for the knapsack problem
Lagrangian Relaxation Description
ksrelax.m Lagrangian relaxation with knapsack subproblems
urelax.m Lagrangian relaxation with knapsack subproblems, plot result

The following table describes the low level test functions and the corresponding setup routines needed for the predefined linear programming test problems. The driver routine lpRun may also call nonlinear solvers to solve the LP problem, therefore some extra low level routines are needed, see NLPLIB TB for a more detailed description.

Predefined LP Test Problems Description
lp_init.m Test problems, used by lpRun.m.
lp2_init.m More test problems, used by lpRun.m.
lp_f.m Define the objective function for LP, cTx (for NLP solvers)
lp_g.m Define the gradient function for LP, c (for NLP solvers)
lp_H.m Define the Hessian matrix for LP, 0-matrix (for NLP solvers)
lp_c.m Define the constraint vector for LP, b-Ax (for NLP solvers)
lp_dc.m Define the constraint gradient matrix for LP, -AT (for NLP solvers)

Utility routines used in OPERA. Some of them are also used by NLPLIB TB.

Utility Routines Description
a2frstar.m Convert node-arc A matrix to Forward-reverse star representation
z2frstar.m Convert table of arcs (and costs) to Forward-reverse star
LPuPinit.m Setup the initial user parameter vector, user_P, for a given problem
LPuPset.m Set (pack) the user parameter vector, user_P
LPuPget.m Get (unpack) the values in user parameter vector, user_P
lpDef.m Define optimization parameters to run LP with lpRun/lpOpt.
mPrint.m Print matrix, format: NAME(i,:) a(i,1) a(i,2) ... a(i,n)
printmat.m Print matrix with row and column labels
vPrint.m Print vector in rows, format: NAME(i1:in) v(i1) v(i2) ... v(in)
xPrint.m Print vector x, row by row, with format.
xPrinti.m Print integer vector x. Calls xprint.m.
xPrinte.m Print integer vector x in exponential format. Calls xprint.m.
getAbc.m Returns the matrices, A,b and c, that defines a LP problem.

It is possible from MATLAB to call FORTRAN and C/C++ code using dynamically linked subroutines, MEX-files. On PC Windows systems these interfaces are either built using 16-bit DLL files or the modern 32-bit REX MEX-file interface. A severe restriction is that the standard I/O routines in C and FORTRAN are not available; DLL MEX-files must use the Windows file I/O functions instead. For long it has been very difficult to develop a working MEX-file interface on PC Windows systems, especially MEX-file interfaces to FORTRAN code. Most optimization solvers are written in FORTRAN and also most of them draws heavy on a functioning I/O system. On Unix systems it is much easier to develop working MEX-file interfaces, and FORTRAN MEX-file code is available for several optimization solvers.

In OPERA TB there is currently one MEX-file interface developed, to the commercial solver MINOS. As standard, MINOS has a very advanced I/O handling, but is also possible to switch it off and use MINOS as a silent subroutine. The MEX-file interface is written in C and compiled and linked using the WATCOM C/C++ version 10.6 compiler. It was impossible to make it work without converting the whole MINOS code to C (using f2c).

MEX-file Interface Description
minoslp.m Interface routine which calls the MEX-file interface to MINOS, the file minosmex with no extension (Unix), MEX (NT4.0), or DLL (Win95, Windows3.11).

The following tables shows a number of example files, which illustrates the use of all algorithms in OPERA. These files are stored in a separate directory, operdemo.

Linear Programming Test Examples
exinled.m First simple LP example from a course in Operations Research
excycle.m Menu with cycling examples
excycle1.m The Marshall-Suurballe cycling example. Run both Blands selection rule and the Minimal reduced cost rule and compare results
excycle2.m The Kuhn cycling example
excycle3.m The Beale cycling example
exKleeM.m The Klee-Minty example. Shows that the simplex algorithm with Dantzigs selection rules visits all vertices.
exfl821.m Run Fletcher exercise 8.21. Illustrates redundancy in constraints
ex412b4s.m Winston example 4.12 B4, using lpsimp1 and lpsimp2
expertur.m Perturbed both right hand side and objective function for Luenberger 3.12-10,11
ex6rev17.m Winston chapter 6 Review 17. Simple example of calling the dual simplex solver lpdual
ex611a2.m Winston example 6.11 A2. A simple problem solved with the dual simplex solver lpdual
Linear Programming Test Examples running interior point methods
exww597.m Test of karmark and lpsimp2 on Winston example .pg 597 and Winston 10.6 Problem A1
exstrang.m Test of karmark and lpsimp2 on Strangs' nutshell example.
exkarma.m Test of akarmark
exKleeM2.m Klee-Minty example solved with lpkarma and karmark
OR Demonstration Simple introduction to Operations Research (in Swedish)
ordemo.m Demo giving simple examples of the use of Operations Research
lpdemo.m LP problems described. Called from ordemo.
nwdemo.m NP problems described. Called from ordemo
Transportation Programming Test Examples
extp_bfs.m Testing routines for finding a bfs to a TP (TPnw,TPmc,TPvogel)
exlu119.m Testing a TP-problem from Luenberger pg. 119, running the routines to find a starting base and then TPsimplx
exlu119U.m Test unbalanced TP on Lu pg. 119, disturbed. Run TPsimplx
extp.m Runs simple TP example. Find starting base and solve with TPsimplx
Network Programming Test Examples
exgraph.m Testing network routines on simple example
exflow.m Testing several maximum flow examples
pathflow.m Pathological test example for maximum flow problems
exflow31.m Test example N31 from LiU
exmcnfp.m Minimum Cost Network Flow Problem (MCNFP) example from Ahuja et.al.
exulys16.m Travelling Salesman (TSP) example Odyssey of Ulysses
Integer Programming Test Examples
expkorv.m Test of cutplane and branch. Example PKorv from Holmberg, Linköping University.
exIP39.m Test example I39 from Linköping University
exbalas.m Test of 0/1 IP (Balas algorithm) on simple example
Dynamic Programming Test Examples
exinvent.m Test of dbinvent on two inventory examples.
exknap.m Test of dbknap (call branch and cutplane) on five knapsack examples
Lagrangian Relaxation Test Examples
exrelax.m Test of ksrelax on oneLP-example from Fischer -85.
exrelax2.m Simple example, runs ksrelax
exIP39rx.m Test example I39 from Linköping University, relaxed. Call urelax and plot.

The optimization solvers in MathWorks Optimization Toolbox which are possible to use in OPERA are listed in the table below. The user must of course have a valid license. The driver routine checks if the actual routine is in the path, possible to call, and then uses feval to run it.

Optimization Toolbox Routine Solves Type of Problem
constr Constrained minimization
lp Linear programming
qp Quadratic programming

Last change 1997-08-18