Explosion in the Number of Iterations

Klee and Minty (Luenberger and Ye, 2008) showed that the Simplex strategy of passing through adjacent vertices may require prohibitive computational times. Let us consider the following problem  

The problem solved by the Simplex method requires that 2 — 1 vertices be passed through. If nv = 50, we have about 10 vertices. If a computer performs a million pivots of the Simplex algorithm per second, it would take about 33 years to solve this problem  

Interior Point algorithms (Luenberger and Ye, 2008 Martin, 1999 Vanderbei, 2007) were created to overcome this shortcoming of the Simplex method. 

The appearance of the first of Interior Point algorithms (Karmarkar, 1984) caused a kind of revolution in the field of applied mathematics since the Simplex method s long history had seemed exhaustive when it came to solving linear programming problems. 

To overcome the sequence of adjacent vertices, the problem is written in the standard form and then transformed into the following one  

---

The Attic method is different from the Interior Point in that it does not make constraints inviolable through a barrier. While it does not have to use vertices at each iteration, as per Simplex methods, it often limits or prevents an explosion in the number of vertices to be sequentially analyzed. 

---