Modified Fourier-Motzkin Elimination Algorithm for Reducing Systems of Linear Inequalities with Unconstrained Parameters

The need for eliminating redundancies in systems of linear inequalities arises in many applications. In linear programming (LP), one seeks a solution that optimizes a given linear objective function subject to a set of linear constraints, sometimes posed as linear inequalities. Linear inequalities also arise in the context of tensor decomposition. Due to the lack of uniqueness in higher-order tensor decomposition, non-negativity constraints are imposed on the decomposition factors, yielding systems of linear inequalities. Eliminating redundancies in such systems can reduce the number of computations, and hence improve computation times in applications. Current techniques for eliminating redundant inequalities are not viable in higher dimensions. As an alternative we propose a modified version of the Fourier-Motzkin Elimination Algorithm (ModFMEA), implemented in MatLab, to reduce redundancies in a given system of linear constraints over reals posed as linear inequalities. Reduction is obtained, at each orthant containing the solution set, by taking the lower and upper bounds of x_i-normalized inequalities x_i \u3e= l and u \u3e= x_i respectively, where l and u are linear terms with no occurrence of x_i, for i = 1,2,...,N. The reduced system over the whole solution set can be obtained by taking the union of the reduced system at each orthant. This method eliminates redundancies by retaining a system of linear inequalities that define the set of feasible solutions. It works under the assumption that all of the variables are unconstrained, i.e., variables may take on negative and positive values. Experimental results demonstrate reduction of systems in higher dimensions for both bounded and unbounded solution sets with feasible computational times, and provide important hindsight into its workings that allows us to design an extension of ModFMEA (ExModFMEA) that yields even more reduction