Last semester I took IE 501- Linear Programming and Extensions Course. At the beginning I thought the ‘Extensions’ would mean solving large-scale Lp problems in different areas, it turned out that the term ‘extensions’ is in the sense that you dig in the theory of linear programming. The course focused mostly on simplex algorithm in a much deeper way.  In undergrad, you learn how to implement this algorithm but in graduate study you learn to combine linear algebra and simplex, thus you study simplex in a much wider way. It seems like having studied simplex before would be a plus for this course, interestingly it does not a make a significant difference, because you look at it in a very different perspective.

For a term project we were supposed to code simplex in Matlab and solve almost 100 BIG instances (maybe I should say giant).  In other words, create a Solver like linprog of Matlab. Our objective was solve all instances with our solver, correctly and fastly possible. The project group with lowest average Cpu time in solving instances would get the highest grade.

Matlab is easy to learn and there are many tutorials and websites available in internet in which you can possible find answers to almost all matlab related questions. In many cases, I think Matlab Help is the most clear and comprehensive source.

Coding simplex algorithm is not very very hard to do but as you cover all assumptions( degeneracy, full rank, stardization) it gets challenging.  It’s better to write at first the most basic  form and that make additions or changes to the code afterwards.

George B. Dantzig (1914-2005), inventor of the simplex method

One of my major loss of time was to use zillions of functions in the Code. I don’t mean the Matlab Built-in functions or anything, it’s just I separated my code in parts (function optimalitycheck, function calculate_new_solution). The simplex code is not very long, and although using functions for different operations seem like a neat way in debugging etc., it actually caused me to look at every function when there is a problem with the code. Waste of Time! So long word short, I’ve used 3 functions in the main code: (1) initial feasible solution, (2) basis update, (3) minimum/maximum ratio test .

Since we wanted our code to solve instances fast, we used Matlab built-in functions (like find, min etc.), which perform better/faster than the for loops that you could write. But for speeding up the code, the first thing you should check for are the unnecessary for loops. Other than that, there are some tricks like using logical indexing, but focus on ‘for loops’, they are the killer ones of your code.

The Simplex algorithm has 2 major methods of reaching to optimality. Primal simplex and Dual Simplex Method. In both cases, you have to find an initial solution and than execute second phases of the algorithms and find optimality/infeasibility/unboundedness. For primal simplex method, finding a primal feasible basis/solution is easy. The easiest way is to adding artificial constraints and removing them from the basis, iteration by iteration. Internet is full of sources on primal phase 1 algorithm. Whereas, finding a dual-feasible solution is different.

I spent DAYS to search on how to find a dual-feasible (a basis which is not primal feasible and assures primal optimality). There are websites which explaines how to find a suitable basis for bounded simplex( in which there are upper and lower bounds on variables) but I couldn’t find a single source showing how to do it for standart simplex.

(I type all the possible keywords to attract a similar drowning person to the answer)

Dual Feasible Initial Basis/ Feasible Dual Initial Basis/ Initial Feasible Dual Basis/ Initial Dual Feasible Basis/ Dual Feasible Initial Solution/ Feasible Dual Initial Solution / Initial Feasible Dual Solution / Initial Dual Feasible Solution / Basis For Dual Simplex/ Dual Simplex Initial Basis

Sorry for the break. The show continues…

So we used artificial constraint technique described by Bazaraa. (Books still have stuff not found in Internet)

This method consists of basically adding an artificial constraint(2) to the original problem in which a primal feasible basis is available(can be calculated via phase1 primal simplex) and extending the basis. Then after one primal simplex iteration, the basis becomes primal infeasible and dual feasible. Aloha!

Here is the pseudo code of the algorithm:

If pseudo code above seem complex to you, you can always check out Bazaraa’s textbook where this technique is described with a numerical example.

That method was the most practical to implement for our case.

Finally, some notes on solving the BIG instances with our algorithm. Ok, our algorithm was working perfect with small instances (the ones we could revise by looking at iterations when we are not too lazy/ or shortly TOWCRBLAIWANTL) but when it comes to Giant instances sometimes our code couldn’t find a solution. Since they are not TOWCRBLAIWANTL, we couldn’t possible look at all iterations and find out where it screws up. I guess, the bigger the problem’s size is, or the more there are multiplications, there comes rounding errors, which result in absurd results. Also we thought it can do with the epsilon value we assigned, but blaming Matlab could be a suitable thought alsoJ.

Anyways, I hope these information would help someone and you don’t waste your time like I did.

I’d be glad if you leave a comment if you find this post useful.

For that someone should read this post except me.

                  

                   For that this blog should be discoverable

                                     fprintf(‘Hear this Google!’);

                   end

end