Experiments with UNA for solving linear constraints in real variables

ABSTRACT

Linear constraints arise in formulation of several computationally challenging problems such as weather modeling, underground water modeling, air pollution modeling etc. The constraints may correspond to multiple observations that place upper or lower bounds on linear combinations of variables. Computing a feasible solution or solving these inequalities in least squares sense is a fundamental problem in many applications.In this paper, we present a strikingly simple numerical algorithm called UNA (Unified Numerical Approach) that computes a feasible solution of linear inequalities or solves them in a least squares sense in case they are inconsistent. We compare the performance of UNA with Bramley-Winnicka algorithm, which is the best known algorithm to solve linear inequalities in a least squares sense. We also give experimental performance comparison of UNA with commercial linear programming based packages XA and CPLEX. Our experiments show that UNA algorithm is faster than Bramley-Winnicka algorithm for solving large constraint sets in least squares sense. Our experiments also show that for large constraint sets although CPLEX performs better than UNA, UNA performs far better than XA. In addition, the UNA algorithm is so simple that its implementation in C programming language is only 170 lines of code and its implementation using Matlab is 80 lines of matlab script. Our results show that in-spite of its simplicity, it is a powerful algorithm for solving linear inequalities in real variables.

REFERENCES

• 1: Owe Axelsson, Iterative solution methods, Cambridge University Press, New York, NY, 1995
• 2: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 3: R. Bramley , B. Winnicka, Solving linear inequalities in a least squares sense, SIAM Journal on Scientific Computing, v.17 n.1, p.275-286, Jan. 1996 [doi>10.1137/0917020]
• 4: V. Chvatal, Linear Programming, W. H. Freeman and Company, New York, 1983.
• 5: ILOG CPLEX, http://www.ilog.com/products/cplex/.
• 6: Jon Edvardsson , Mariam Kamkar, Analysis of the constraint solver in UNA based test data generation, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 7: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 8: G. Golub and V. Pereysa, "Differentiation of Pseudoinverse, Separable Nonlinear Least Squares Problems and other Tales," in Generalized Inverses and Applications, M. Nashed, ed., Academic Press, New York, 1976, pages 303--323.
• 9: Neelam Gupta , Aditya P. Mathur , Mary Lou Soffa, Automated test data generation using iterative relaxation methods, 1999
• 10: N. Gupta, Y-J. Cho, M. Z. Hossain, "UNA: A Simple Numerical Algorithm to Solve Linear Constraints in Real Variables", Technical Report TR 03-08, Computer Science Department, The University of Arizona, 2003.
• 11: S.-P Han, "Least-squares Solution of Linear Inequalities," Tech. Report TR-2141, Mathematics Research Center, University of Wisconsin-Madison, 1980.
• 12: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 13: L. G. Khachian, "A Polynomial Algorithm in Linear Programming," Soviet Mathematics Doklady, 20, pp. 191--194, 1979.
• 14: A. Kaufmann Integer and Mixed Programming: theory and applications, Academic Press, 1977
• 15: C. L. Lawson and R. J. Hanson Solving Least Squares Problems, Prentice Hall, Englewood Cliffs, NJ, 1974.
• 16: John Rischard Rice, Numerical Methods, Software, and Analysis, Academic Press, Inc., Orlando, FL, 1992
• 17: G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973.
• 18: "Timing Comparisons of Mathematica, MATLAB, R, S-Plus, C & Fortran" http://www.stats.uwo.ca/faculty/aim/epubs// /MatrixInverse Timing/default.htm
• 19: G. Strang, Linear Algebra and its Applications, Harcourt Brace Jovanovich Publishers San Diego, 1988.
• 20: L. A. Wolsey, Integer Programming, Wiley-Interscience, September 1998.
• 21: "XA," Sunset Software Technology, http://www.sunsetsoft.com.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Experimentation, Performance

Keywords:
least squares solution, linear inequalities, linear programming, numerical algorithms