Linear programming (LP) techniques are very useful in decision-making processes in organizations, including solving resource allocation problems for profit or nonprofit organizations. Linear programming solvers are available. These state-of-the-art LP solvers can solve fairly large problems using personal computers because of advances in technology. Many linear programming problems can be very large, including thousands of variables and constraints.

Many of the state-of-the-art LP solvers can provide solutions to the large problems, but it may not be possible to determine whether or not these solutions are optimal or even close to optimal. In this paper, the authors have implemented a system to verify whether the basis is primal feasible and/or dual feasible. Additionally, the system can find or determine the optimal starting point from an arbitrary basis, and it uses exact arithmetic to guarantee correctness of the results. This system is called LPex.

The objective of the LPex system is to solve medium- to large-scale linear programming problems and the approach taken to verify for optimality. If the solution is not optimal, the system repairs it. The LPex system consists of several modules based on exact arithmetic (integer or rational). One module deals with discovering block structure in matrices; another module computes LU-factorizations of sparse matrices with integer and rational entries. The next module solves sparse linear systems over the rational entries using Wiedemann’s method [1] over finite fields.

Additional modules of the LPex system include ones for determining whether a basis of the linear program is primal or dual feasible; for implementing primal simplex; for implementing the dual simplex; and for dealing with the criss-cross method. Finally, the system contains a module for solving linear programs from scratch. The paper presents the verify-and-repair strategy to determine the optimal solution of medium-to-large linear programming problems. The approach indicates that the existing inexact LP solvers usually provide a solution that is close to optimal, but the LPex server will be able to collect instances that cause difficulties with existing inexact solvers with exact verification.