Circumventing the Slater conundrum in countably infinite linear programs

•Provides duality results for general countably infinite linear programs.•Proves properties of the Lagrangian function and saddle points.•Applies results to countable-state MDPs and to a robust auction-design problem.

Duality results on countably infinite linear programs are scarce. Subspaces that admit an interior point, which is a sufficient condition for a zero duality gap, yield a dual where the constraints cannot be expressed using the ordinary transpose of the primal constraint matrix. Subspaces that permit a dual with this transpose do not admit an interior point. This difficulty has stumped researchers for a few decades; it has recently been called the Slater conundrum. We find a way around this hurdle.We propose a pair of primal-dual spaces with three properties: the series in the primal and dual objective functions converge; the series defined by the rows and columns of the primal constraint matrix converge; and the order of sums in a particular iterated series of a double sequence defined by the primal constraint matrix can be interchanged so that the dual is defined by the ordinary transpose. Weak duality and complementary slackness are then immediate. Instead of using interior point conditions to establish a zero duality gap, we call upon the planning horizon method. When the series in the primal and dual constraints are continuous, we prove that strong duality holds if a sequence of optimal solutions to finite-dimensional truncations of the primal and dual CILPs has an accumulation point. We show by counterexample that the requirement that such an accumulation point exist cannot be relaxed. Our results are illustrated using several examples, and are applied to countable-state Markov decision processes and to a problem in robust optimization.