Simplex Algorithm

[ftneek]

Thank you for the benchmarks. Now that I thought about it a little, since the simplex_le() method assumes the n constraints are <=, we know we need to add n slack variables. Thus if we make a list of the last n column indices (not counting/using b column) to use as initial basic variables, we can call simplex2() directly as we know all the arguments. This should speed up simplex_le() a bit. This is the idea, but I have a little trouble actually making the list at the moment.

Code:

 a := simplex2(a,makelist(I,I,b(2),b(2)+b(1)),b(2)+b(1)-1,0,0);

We have 0 artificial variables and should ignore 0 columns.

A similar idea could be used for artificial variables. Since simplex_le() assumes the top dir constraints are "=", this makes things easy. After the added identity matrix, we should add dir more columns (identity matrix like). But we should also add a row of 0's with 1's in positions of the new dir columns (the last dir columns, not counting/using b column). Again we can make a list of indices of the added columns and call simplex2 directly, bypassing the simplex() wrapper. Except this time we call simplex2(a,list,v,dir,0) since we have dir artificial variables. This is an "initial tableau" so we should not ignore any columns yet.

(11-12-2023 12:38 AM)Albert Chan Wrote:  

(11-11-2023 04:54 AM)ftneek Wrote:  > simplex2([[3,2,1,1,0,10],[2,5,3,0,1,15],[-2,-3,-4,0,0,0],[0,0,0,1,1,0]],{4,5},5,2,0)
[-130/7,[15/7,0,25/7,0,0],...]

I have no idea how this is setup, but it run faster , time = 0.0105 s

It is just manually entering the arguments simplex() tries to find. 2 constraints -> 2 basic variables. since all constraints are "=", they are the positions of 1's in the last row, hence positions {4,5}. We have 3 variables and 2 artificial variables -> v=5. 2 "=" constraints -> 2 artificial variables. Because we have artificial variables and it's an initial tableau, the last argument is 0.

(11-12-2023 12:38 AM)Albert Chan Wrote:  

(11-11-2023 11:51 PM)Albert Chan Wrote:  > m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> simplex_le(m, -2)
[-130/7, [15/7, 0, 25/7, 0, 0, 0, 0], ...]

> time(simplex_le(m, -2))      → time = 0.0195 s

Compare the time when supplying the equivalent inputs for simplex2 using <= + >= method, to see the time saved by bypassing the simplex wrapper.

> simplex2([[-3,-2,-1,1,0,0,0,-10],[-2,-5,-3,0,1,0,0,-15],[3,2,1,0,0,1,0,10],[2,5,3,0,0,0,1,15],[-2,-3,-4,0,0,0,0,0]],{4,5,6,7},7,0,0)
[-130/7,[15/7,0,25/7,0,0,0,0],...]