On the Simplex Method and the Interior-Point Method for Linear Programming

Sammanfattning

The field of linear programming is concerned with minimizing linear functionswithin a convex polytope defined by certain constraints. Different algorithms,such as the simplex method and primal-dual interior-point methods, havebeen developed to find an optimal solution. The simplex method movesalong the edges of the polytope, while primal-dual interior-point methodsmove inside the polytope. In this report, we studied Dantzig’s rule, Bland’srule, and the steepest edge rule, defining different variants of the simplexmethod, and the short-step path-following algorithm, long-step path-followingalgorithm, and the predictor-corrector method, which are different primal-dualinterior-point methods. In particular, we were interested in comparing thesemethods from a theoretical and practical perspective. Taking into accountthese different perspectives provides a more constructive overview of themethods, and what performance to expect when applying one of these methodsin practice, while being aware of the pitfalls that may be encountered in theory.We implemented the algorithms in Matlab, and the testing was performedon problems imported from Netlib. The long-step path-following algorithmexhibited the best performance, while the short-step path-following algorithmdisplayed the worst performance. The most unanticipated result was thatDantzig’s rule performed better than the steepest edge rule, which may havebeen caused by a naive implementation of the algorithm.