A Simplex Based Parametric Programming Method for the Large Linear Programming Problem

摘要

We present a methodology of parametric objective function coefficient programming for large linear programming (LP) problem. Most of current parametric programming methodologies are based on the assumption that the optimal solution is available. Large linear programming problems in real-world might have millions of variables and constraints, which makes it difficult for the LP solver to return the optimal solutions. This paper extends the traditional parametric programming methodology by considering features of the large LP problems. By considering the tolerance of infeasibility and introducing a step size to deal with degeneracy of the problem, the parametric objective function coefficient linear programming of large LP problem can be conducted while the optimal solutions are not available. Experiment results of LP problems with different scales are provided.