diochnos/software/optimization
Ellipsoid
The popular Ellipsoid method used in Linear Programming.
Here you can download the latest version. (Feb 26, 2009)
In 2009 (Feb 26), I modified the source code so that I can indicate problematic situations that arise due to machine precision. Thanks to Ricardo Martins who came up with such a problematic situation. For more information, and examples, on what can go wrong read below the section Notes / Warnings to all users.
In 2008 (Mar 25), I modified the source code so that all the variables and comments are in English. Thanks to Xiao Linfu who motivated me.
The initial version of source code (NOT suggested to use it) plus a win32 executable can be found here.
Notes / Warnings to all users
I frequently have questions from various people about the implementation, so it is good to say here a few things.
First of all, the source code above was created for educational purposes only aiming on solving simple systems (few iterations, low required precision in arithmetic computations) and achieves this goal with the demo mode that it has.
Secondly, the Ellipsoid method is very sensitive, in the sense that it generally requires high precision while performing arithmetic. Hence, for practical considerations, the suggested method is to revise the source code and incorporate the capabilities of the GMP arithmetic library. In other words, there is no guarantee that the program will find a solution to your problem.
Examples of what can go wrong
Since Feb 26, 2009 I decided to write down some examples of what can go wrong in the Ellipsoid method.
- One such example was generated by Ricardo Martins and can be obtained here. Simply issue the command:
./ellipsoid < ricardo_in.txt