Threaded Mode | Linear Mode

ftneek · 11-14-2023, 06:24 AM

(11-14-2023 02:25 AM)Albert Chan Wrote: You can do this with simplex_le too, but not much typing is saved.
Constraints already are "=", artificial variables need to start with -1, thus result negated.

> simplex_le([[1,2,0,1,-1,0,0,20],[2,1,1,0,0,-1,0,10],[-1,4,-2,3,0,0,-1,40],[1,4,3,2,0,0,0,0]],-3)

[35,[5,0,0,15,0,0,0],[[0,3/2,-1/2,1,-1/4,0,-1/4,15],[0,0,0,0,-3/2,1,1/2,0],[1,1/2,1/2,0,-3/4,0,1/4,5],[0,1/2,7/2,0,5/4,0,1/4,-35]]]

Inside numbers not quite match, because simplex_le use pivots order {5,6,1}. But that shouldn't matter.

Does that input still save computing time? That is closer, potentially promising. Order of pivots does not matter. But the coefficients of the objective function/z row should match simplex2, including in sign, else the dual solution will not be correct. To me it seems those columns need to be multiplied by -1, except for the entries where the b coefficient is 0... But to me this just seems to be creating new, strange rules and complicating things. For example adding negative slack variables to "=" constraints, why? That does serve a purpose, but I don't think it's explained in this textbook. I know another book that refers to that has "soft and hard constraints" for when you sometimes want to allow the "=" constraints to be violated for a cost, my upcoming project actually uses that idea. If it does not save computing time, I suggest just using the intended standard form.

As I mentioned in the other thread, artificial variables are not always required to solve a system, but can always be used as starting place for the simplex algorithm, and their use cuts down on computation time (when compared to size of <= + >= matrix). Learning how to put systems in standard form is not very difficult, there are only a few rules to follow for when the following arise: ">=","=","<=", unrestricted variables. I think that's everything.. Once you learn the few rules you should be able to handle most systems. But I agree it is not convenient to have to enter this information manually. A program to convert to standard form for the user would be immensely convenient and useful.

That was what I was going to start with originally, but handling user input would have taken too much time for me then. So I just wrote the main simplex2 code (the original simplex()) with the assumption that it will be provided the correct inputs to use, ideally by a helper method that sets everything up for you, which was my goal for simplex() (current version).

The algorithm does make some assumptions, and in return makes some guarantees. Namely if it is provided a non degenerate matrix in standard form, it is guaranteed to return the optimal solution to the primal and dual system (or determine no solution) in a finite number of iterations. Even if the matrix is degenerate, there are a few things we can try that should guarantee finiteness. If the assumption is not met, I don't know what is guaranteed.

If you want an algorithm that does not use artificial variables, there are some out there. I encourage you to read the article/link in the source comment. If I were to implement another simplex algorithm, it would probably be that one unless I find something more promising. It uses no artificial variables, requires less multiplications and additions, and has the dual solution embedded in the matrix. But I follow this text this semester, as my course uses it heavily.

I don't want to make it seem like I'm squashing this idea. If you just want a faster simplex algorithm for large problems, that's fine. But (unless you can figure out how to consistently match the signs of simplex2) it should be made clear that the intention is to only provide solutions to the primal, and that finding the dual solution would require converting to dual problem AND rewriting in standard form (maybe not if using your method) AND another round of simplex iteration, probably expensive for a large system. Needing to run a second tableau, the computation time is probably at least back to running simplex2 as originally intended... My original intention was for extensions of the program to make it easier to use, extract the desired information, or add functionality without limiting its capabilities. In my opinion without the dual solution available, the capabilities are being limited. But it should useful if you want only the primal, fast.