Ping-Qi Pan

The famous simplex method, invented by George B. Dantzig in 1947, moves from vertex to vertex in the underlying polyhedron until achieving an optimal vertex. As one of the most widely used mathematical tools, it has dominated the field of Linear Programming for nearly eighty years. However, it has exponential time complexity, and its performance turned out somehow unsatisfactory when solving some difficult LP problems since the solution process can sink into a degenerate vertex for too long. In 1984, Karmarkar published his work on the interior-point algorithm, which goes across the interior of the polyhedron, and which was not only of polynomial time complexity but also appeared fast. As such, it immediately drew the attention of researchers worldwide, giving rise to an upsurge in the interor-point method. Some scholars even considered it the winner against the simplex method for solving large-scale and sparse LP problems. However, the technique can only approach an optimal solution on the boundary, and it...