Economics Network CHEER Virtual Edition

Volume 11, Issue 1, 1997

Worms logo *

Linear Programming on the Web

Ziggy MacDonald
University of Leicester

Introduction

In previous issues of this journal I have written about the Excel Solver add-on as an appropriate and powerful medium for teaching linear programming (MacDonald 1995 & 1996). Estelles et al (1996) have also written about the virtues of GAMS as a tool for teaching mathematical programming. However, the time is probably right to look beyond the traditional teaching mediums and consider what is available on the internet, particularly the World Wide Web. There appears to be quite a wealth of linear programming (LP) related material on the web, however, much of it is directed at practising researchers. Fortunately there is some growth in the available teaching material and subsequently this article will consider what is currently available with a view to what we might expect in the very near future.

OR/MS Sites

There tends not to be specific linear programming sites on the web, rather, LP material is typically found under more general collections of operations research/management science (OR/MS) resources. There are, as you would expect, a considerable number of OR related sites. Michael Trick's Operations Research Page provides a very comprehensive guide to these but it does require some skilful searching to seek out the LP-related material. However, for the purposes of writing this paper, it is rather fortunate that there appears to be three very large sites that dominate the web. These can be found at the World-Wide-Web for Operations Research and Management Science (WORMS) , the Optimisation Technology Center (OTC) and the Institute for Operations Research and the Management Sciences (INFORMS). Given the quality of material on the first two of these sites these will form the focus of this paper although reference will be made to the latter. All of these sites provide a rich resource for an introductory exploration of LP (and most other OR topics) although much of the material goes well beyond the needs of most undergraduate courses. The WORMS site is based at the University of Melbourne and is run by the graduate students of the Operations Research Group (under supervision by Moshe Sniedovich). The site contains a lot of material for student exploration including a virtual encyclopaedia which is continually being added to by OR/MS practitioners around the word. Of particular relevance is the section concerning interactive solvers which will be considered in more detail later. The Optimisation Technology Center, founded in 1994, is a joint enterprise of the Argonne National Laboratory and Northwestern University. This site has a wealth of material including information about optimisation algorithms and applications, software packages, and a collection of case studies, some of which are fully interactive (an interactive Diet Problem case study is considered later). The INFORMS site is the internet manifestation of the merged OR Society of America and The Institute of Management Science. It has a large section dedicated to education and offers traditional support material (e.g. instructional videos) in addition to published material and bibliographic services. It doesn't, however, offer the truly interactive features that the other two sites have to offer which are the subject of the following section.

On-Line Simplex

For the teaching of Simplex, the OTC has its impressive Simplex Java Applet. With this tool, a student can enter a problem with a maximum of seven variables and seven constraints, and step through the simplex method to find its solution. This type of interactive web material is undoubtedly the way forward for web-based teaching resources, the typical alternative that is currently available being the standard page where a student can download documents which will ultimately be printed off and used away from the computer. Before I describe the tool I should offer a word of warning. In the first place, the Applet is very sensitive and I did have difficulty in getting it to do anything initially (http://www-c.mcs.anl.gov/home/otc/Guide/CaseStudies/simplex/index.html an older version is also available which appears to be slightly more stable) [I cannot find the older version - web editor]. What is more, because it makes use of Applet windows, it is very easy to be fooled into thinking that nothing is happening when you click the button to enter a new problem. You do not get an hour glass suggesting that something is happening, rather, if you sit and be patient a small window will appear in time prompting you to define the problem dimensions. What is more difficult is getting rid of the windows once you have completed the problem, but I believe these minor irritations will disappear as the technology evolves. Returning to the tool, to start the routine the user clicks the 'New Problem' button from the web page and a small window appears in which the user describes the LP model in terms of the number of variables and constraints with the use of some input boxes. Following this the user is presented with the window shown in Figure One in which the LP equations can entered via a combination of input boxes and drop-down list-boxes. This is one of the attractive features of Java scripting although one should be aware of the lack of error-trapping facilities (you can, if you so desire, enter any old rubbish in the boxes, which is true of any Java application).

Download the
Screen Shot
Figure One: Linear Program Input Box

Having entered the problem formulation the user clicks the 'Preprocess' button which reveals the problem in simplex form via another Applet Window, shown in Figure Two, which reveals the initial basic feasible solution.

Download the
Screen Shot
Figure Two: Simplex Formulation of the Problem

At this point the user can then choose how to proceed to the optimal solution. The 'Step' method allows the user to get involved with the solution generating process by determining the entering variable. At this point, I have to confess that I became just a little confused as the display did not appear to update between steps, although the message window did give some indication of what was going on. What is important, however, is that this is a clear indication of what is possible on the web and it suggests to me that as Java scripting develops, the sophistication of this type of material will greatly improve.

The other main site (WORMS) has put considerable effort in exploring the capabilities of Java scripting with its experimental JAVA section. This appears to be their 'work-in-progress' space (note) and an attempt has been made to reveal the efforts required to get Java to do the things that we want from the web. The real stuff of interest, however, is not available directly from WORMS (as far as I can tell), as it appear that the more advanced developments of this technology are available from "Simplex Place", a site written by the same author (Moshe Sniedovich) which lives on the same server. The end result is perhaps unrivalled on the web. In addition to a detailed explanation of the theory of the simplex method (written in a readable and lively style), the site provides an interactive simplex tool created with JavaScript which is embedded in the web page, removing the possible confusion of Applet windows floating around. It's a similar animal to the OTC's impressive Simplex Java Applet, but it lives in a far richer teaching environment and has more in common with the traditional methodological approach of textbooks. This is the essence of my particular attraction to this site. The user can discover the simplex method from the first principles of gaussian elimination, through the determination of entering variable (referred to as the Greedy Rule!) and leaving variable to the optimality test, and at each stage of the learning process there is a Java tool for practising the methods (with OTC's Simplex Applet, the instructional material is separate from the interactive tool). Having worked through this support material the user can then proceed to interact directly with each tableau on the road to a final solution. This is illustrated in figure Three.

Download the Screen Shot
Figure Three: Interactive Tableau

The student makes use of the tool in Figure Three as though it were a traditional simplex tableau (unlike that provided by OTC). In terms of learning, the student can use this tool to check all the calculations for each set of row operations required to pivot each tableau. What is particularly promising about this site is the author's obvious desire to keep on improving the tool. Promised features include a facility to describe the order of the problem and the ability to deal with 'greater than or equal to' constraints explicitly (i.e. by utilising the Big M tableau method). If this occurs by the time I teach the subject next academic session I will certainly be recommending this site to my students (in addition to Excel Solver!).

On-Line Graphical Method

The site that gave me the most excitement (I was even driven to email the author to communicate this excitement!) was concerned with the graphical method for solving LPs. The site in question is called "Anima-LP: A Tool for teaching Linear Programming". (http://weber.u.washington.edu/~cvj/animalp.html)[Now at Download the Screen Shot
Figure Four: On-Line Graphical Solution

In Figure Four one can see the graphical solution to the 'Diet Problem', previously discussed in MacDonald (1996) and Estelles et al (1996), as created with this interactive tool. Not only can students enter the constraints etc. via a spread-sheet like interface and observe the corresponding graphical representation as it changes, the application is written such that one can directly alter the constraints by clicking and dragging the graphical view. As the graphical view is manipulated, the problem definition given above it is automatically resolved. Although the on-line version is perhaps a little sensitive (you have to remember to press enter after each change you make in the problem definition) this is clearly the way forward for interactive web-based teaching. Not only would I recommend this site to anyone charged with introducing students to linear programming, I will certainly be referring my third year business economics to this page.

On-Line Solvers

Another particularly exciting development on the web is the development of powerful on-line solvers, not intended for instruction and certainly capable of handling large problems. The OTC has an excellent example of this via its system referred to as the Network-Enabled Optimisation System - NEOS. Not limited to linear programming, the NEOS server has solvers for unconstrained optimisation, stochastic linear programming, bound constrained optimisation, non-linearly constrained optimisation and linear net work optimisation. Although one is required to input problems in MPS format (note), using the on-line solvers is very straightforward, and given that the output is returned very quickly (both over the web and via a separate email) they can be demonstrated live in a lecture theatre. Having said this, this unique resource at NEOS is most likely to be more suitable for project-based work for more advanced students.

Miscellaneous Material

The case studies at OTC are a promising development although at present there is only one available for LP (The Diet Problem!). The user can work through the formulation of a diet problem and can then proceed to interact with the problem by choosing from a list of foods (with accompanying details on price and nutritional information) those which are to be included in the problem. In my first attempt I selected raw broccoli and lettuce. The tool informed me that this was infeasible as I could not meet my minimal nutritional requirements (no wonder I permanently feel ill!). The point is that users can select a basket of foods, alter the nutritional constraints if so desired, and find the optimal choice with associated minimum cost. The user can then proceed to analyse the problem solution further and look at the sensitivity information and a breakdown of the nutritional contribution of each food in the final solution. Overall this is a useful resource but it does requires some careful experimentation to be useful as an instructional tool.

Other miscellaneous resources include the Imperial College Management School OR-Library, maintained by John Beasley. This library contains data-sets for a variety of OR type problems from assignment problems to vehicle routing problems. The LP section contains twenty seven data files, but beyond this the material is of limited value. Perhaps of greater use is the Mathematical Programming Glossary, maintained by Harvey Greenberg. The site contains material contributed by a variety of sources (including a lot of LP-related material) and is excellent for brief but detailed information on all aspects of mathematical programming. Finally there is the standard LP FAQ (Frequently Asked Questions). The OTC maintains these for LP and they provide a useful resource for students wishing to gain an introductory insight into the world of LP.

Concluding Remarks

The quantity and quality of LP material available on the web, like other subjects, appears to expand on a daily basis. The sites mentioned in this paper can only represent a snapshot of what is currently available and is certainly not exclusive. The selective list presented here was a deliberate choice, simply intended to highlight the quality of material that can be found. The new direction for the web is interaction beyond simple clicking of links. The Java revolution is much hailed and, although far from being fully exploited, the use of it exhibited by the sites mentioned here is promising. I expect to see more developments in this direction with students having access to interactive web facilities that go well beyond the constricts of traditional instruction.


References

Estelles, T. C., Arre, M. M. & Garrido, R. S., 1996, "Economic Optimisation with GAMS", Computers in Higher Education Economic Review, 10 (2) 2-7

MacDonald, Z., 1995, "Teaching Linear Programming using Microsoft Excel Solver", Computers in Higher Education Economic Review, 9 (3) 7-10

MacDonald, Z., 1996, "Economic Optimisation: An Excel Alternative to Estelles et al's GAMS Approach.", Computers in Higher Education Economic Review, 10 (3) 2-5

Notes

As an aside, I did get a bit lost on this page as I often do at sites that make extensive use of frames. I fail to see why web page designers believe that half a dozen frames with one web page will somehow enhance the accessibility of the material. Hopefully, as the web develops, authors will start to adhere to the rules that apply to software interface design whereby navigation is at the top of the list of considerations during development.

MPS format is the de facto standard ASCII medium among most of the commercial LP codes. MPS input format was originally introduced by IBM to express linear and integer programs in a standard way. The main feature of MPS format is that it is a fixed column format (as opposed to entering the model as equations), and everything (variables, rows, etc.) gets a name, thus care must be taken that all information is placed in the correct columns.


Ziggy MacDonald
Department of Economics
University of Leicester
University Road
Leicester. UK
LE1 7RH

E-mail abm1@le.ac.uk
Top | CHEER Home

Copyright 1989-2007