Revisiting  Degeneracy, Strict Feasibility, Stability, in Linear Programming

Unlike general conic programs,  LPs do not require strict feasibility in order to establish strong duality.  In this talk  we discuss that the specific degeneracy that arises from lack of strict feasibility necessarily causes difficulties in both simplex and interior point methods. In particular, we show that the lack of strict feasibility implies that every basic feasible solution is degenerate. This leads to efficient preprocessing techniques. We provide illustrations using various problems sets including the NETLIB problem set.


https://meetings.informs.org/wordpress/indianapolis2022/abstract-submission/