Simplex-Algorithm

About the Tool

The online Operations Research Tool (ORTOOL) illustrates the simplex algorithm and allows to solve even large linear programs. All computations are preformed precisely (i.e. in fractions) and the tool is able to deal with large numbers with arbitrary precision. The tool guides the user step by step to the solution of a linear program. The implementation has taken care that computations are transparent with respect to standard pivot rules such as Bland's (smallest index) or Danzig's (steepest ascent) rule that are discussed in introductory textbooks. However, the tool also demonstrates that it is possible to design more efficient pivot rules. Allowing to compare different approaches, it also seeks to stimulate further research.

The tool is open to the academic public as well as interested practitioners. It has been created primarily to give students a training platform when studying linear programming and preparing for exams. Some features, however, are only available to logged-in users (see below for details).

For convenience, users can download all data that they have entered as human-readable CSV-files. These files can be uploaded again if a user wants to continue working on the same data set. Users cannot store data on our server or access data entered or uploaded by other users.

Computational performance has not (yet) been a major focus and the software does not run on a high-performance server but rather a simple NAS. Most features of the web interface are implemented in PHP. Tableau transformations are performed by external programs written in C using the GNU Multiple Precision Arithmetic Library (GMP). In the current version, all computations are performed single-threaded and well-known approaches to increase performance such as LR decomposition of the tableau's matrix have not (yet) been implemented. Also, limits of a variable's domain are dealt with by adding respective constraints.

We do not explicitly track, save, or analyze data passed on to the tool. There is no database or systematic recording of usage. Only data that is passed on to the C-program is stored for hand-over in temporary files. Other user data is stored in PHP session variables that are lost once the session expires (typically after 1,440 seconds of inactivity of the user, fluctuations of PHP's garbage collection may apply).

We do not store any personal data. However, we do reserve the right to possibly record computation times of particular tasks which we may use to improve the software. And we do not take any responsibility that user activity will not leave digital traces. In particular, the system maintains log files that are standard on a Linux/Apache/PHP or Synology NAS installation (e.g. regarding web server access and system messages/failures). Particularly to users who work with confidential data we recommend SSL encryption (i.e. accessing the tool via https://btwtr2.oec.uni-bayreuth.de/ortool/simplex.php). Our SSL certificate is issued by the Universität Bayreuth and certified by DFN-Verein Global Issuing CA. Its fingerprint is ea927c63f6b76f725f8de6e4c944a4c7c8870426.

We maintain the right to possibly exclude heavy users. Researchers and practitioners who make frequent use of the software are kindly asked to request an account.

In order to avoid misuse and restrict computational ressources, the following limitations apply to public guest users:

• Integer requirements are ignored; the tool only solves the respective real number relaxation.
• All computations are limited to about 25-30 seconds. The tool will then interrupt its computation and display the latest tableau. The user may continue the computation by clicking on one of the respective buttons.
• Linear programs are limited to 1,000 variables and 1,000 constraints. An ASCII representation of a tableau is restricted to 5 kB.

We invite interested students to contribute to the project. In particular, we appreciate

• bug reports,
• further examples, and
• computational improvements.

Please provide comments and report errors to Stefan Seifert.