Simplex Algorithm

[ftneek]

(11-12-2023 11:04 PM)Albert Chan Wrote:  Just curious, if simplex2 can assume no artificial variables, can it speed up more?

simplex2 makes no assumption. Well, it assumes that it was provided a matrix in standard or canonical form and enough basic variables to use. It is able to take a tableau from any stage and continue iteration, but it needs inputs to know where to start from. But I suppose if you know in advance that you have no "=" constraints, then you know you will have 0 artificial variables. I guess there could be a separate version of simplex2, that assumes no artificial variables, and the parts/logic involving artificial variables could be altered or removed from the method. But that would require maintaining 2 versions of essentially the same code.

Artificial variables only really affect the indices to use in checks of b column and c row, and there is an IF art>0 inside the while loop. It is only used once, but the if statement is reached when the algorithm decides to exit the while loop or use Dual Simplex. Once artificial variables have served their purpose, ign:=art (so we will not consider the artificial entries in the c row, they are allowed to be negative) and art:=0, the IF art>0 statement has been used and won't be needed again. Also n:=1, now we only ignore the c row/z entry in the b column, as the artificial row was deleted. I'm not sure the time saved by removing those parts of the code and maintaining a separate version would be worth it. But maybe it could be possible to simplify the arguments of simplex2.

There are potentially optimizations that could be made as well. For example sometimes the matrix is already given in canonical form, or some columns already are. Then it makes sense to omit row operations from the basic variable columns already in canonical form, but I'm not sure if detecting that would have a smaller computation cost than just keeping it as is. The IF aij!=0 in canonicalForm is to prevent division by zero, and may already handle it.

Again, I would like to set up some tests to ensure that any changes to the code do not effect the output of simplex2.