Simplex Algorithm

[ftneek]

Attached is an implementation of the simplex algorithm as developed in
An Introduction to Linear Programming and Game Theory 3rd Edition, Paul R. Thie and Gerard E. Keough (ISBN: 978-0470232866).

Thanks to Albert Chan for his contributions. I have also included their simplex_le() method.

I originally posted it in this thread, but there's been a few changes since then.

2023/11/11: initial upload
2023/11/17: some speed improvements. simplex2 was renamed to simplex_core(), shown examples will still work if you just change the name.
2023/11/18: added simplex_int() for integer programming problems. simplex_core() returns a list of basic variables as 4th item when there is a solution. Updated and added some integer tests. See post 26 for an example.
2023/11/19: speed improvements, new simplex() wrapper. See post 27 for example inputs.
2023/11/19: fixed exact-> floating point bug for integer problems, more tests
2023/11/21: fixed bug in infinite solution code, new test
2023/12/21:

• new files for simplex, tests, and Game Theory
• improved simplex() command can handle maximization problems, integer restrictions, binary restrictions, or unrestricted variables. No need to manually input slack/artificial variables or negate the objective function row.
• adds solveGame() to solve 2-person zero-sum games
• minor bug fixes, changes to documentation, returns x as a column
• simplex_core() and simplex_int() accept linear programs in canonical form; simplex_core2() and simplex_int2() accept programs in standard form (simplex2 was renamed to simplex_core2)
  

2023/12/22: new files for simplex and tests, bug fix
2023/12/23:

• new files for simplex and tests
• simplex_core returns ∅ for infeasible model with no solution/empty feasible region
• simplex_core and simplex_int accept an additional parameter
• incorporates changes to simplex_le
  

2024/01/06:

• new simplex, tests, and hashin files
• switches to Bland's pivoting rule when a repeated basis is detected to prevent cycling
• infeasible models return "∅" instead of ∅