Linear Programming with Non-Archimedean Right-Hand Sides

Abstract The goal of this work is to propose a new type of constraint for linear programs: inequalities having a non-Archimedean right-hand side. Here, the word non-Archimedean refers to values that can be infinite, finite, or infinitesimal. Because of the nature of such constraints, the polyhedron describing the feasible region becomes more complex, since its vertices are now represented by non-Archimedean coordinates, and so is the optimum of the problem. The introduction of such a constraint enlarges the class of linear programs, where the Archimedean ones become a special case. To tackle optimization problems over the resulting polyhedra, this work presents a solving routine, which consists in a generalization of the Simplex algorithm. This solver optimizes Archimedean linear programs as corner cases. Finally, the study presents three relevant applications which can benefit from the use of constraints with non-Archimedean right-hand side, making the use of the extended Simplex algorithm essential. For each application, an exemplifying benchmark is solved, showing the effectiveness of the solving routine.