Reaching Feasibility Quickly for Sets of Linear Constraints

Finding a feasible solution for a set of linear constraints and bounds is an essential step in many problems, including linear programming. Many linear systems have large numbers of variables and constraints, and the computation time for finding a feasible point can be very large. This thesis proposes an improved projection method for finding a feasible point in linear systems. The method increases the acceleration and improves the direction of movement towards the feasible region. Multiple algorithms developed in this research apply various approaches for the movement acceleration. The thesis also develops an optimization model for finding an optimal set of algorithms having the highest performance in a concurrent implementation. A new presolving technique is introduced which simplifies a linear system before starting the main algorithms. Concurrent computing of the algorithms is proposed for finding a feasible point in large linear systems.