A SIMPLEX METHOD FOR COUNTABLY INFINITE LINEAR PROGRAMS

We introduce a simplex method for general countably infinite linear programs. Previous literature has focused on special cases, such as infinite network flow problems or Markov decision processes. A novel aspect of our approach is the placing of data and decision variables in a Hilbert space that elegantly encodes a ``discounted"" weighting to ensure the continuity of infinite sums. Under some assumptions, including that all basic feasible solutions are nondegenerate with strictly positive support and the set of bases is closed in an appropriate topology, we show convergence to the optimal value for our proposed simplex algorithm. We show that existing applications naturally fit this more general framework.