Article ID Journal Published Year Pages File Type
6421180 Applied Mathematics and Computation 2014 17 Pages PDF
Abstract

Solving a general linear programming problem using the simplex algorithm relies on introducing artificial variables that creates a large search space. This paper presents the non-acute constraint relaxation technique that not only eliminates the need for artificial variables but also reduces the start-up time to solve the initial relaxation problem. To guarantee the optimal solution or infeasibility or unboundedness of a linear programming problem, the algorithm reinserts the non-acute constraints back to the relaxation problem. The results of this algorithm are superior than the original simplex algorithm with artificial variables for a linear programming problem with a large number of acute constraints.

Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,