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.
|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.
|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.
|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.
|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.
|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.
|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.
|dpinvent.m||Dynamic programming algorithm for the inventory problem|
|dpknap.m||Dynamic programming algorithm for the knapsack problem|
|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.
|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).
|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|
Last change 1997-08-18