Research on Optimization Algorithms.

This is a summary of research carried out under this grant. Some of the results are for linear complementarity problems, existing pivot algorithms like Lemkes complementary pivot method, Murtys principal pivoting method, Cottle-Dantzig principal pivoting method, Vander Heydens variable dimension algorithm, are all exponential growth algorithms in the worst case even on very nice classes f problems. Polynomially bounded ellipsoid methods have been developed for solving convex quadratic programs or linear complementarity problems associated with positive semidefinite matrices. A practically efficient critical index algorithm based on orthogonal projections has been developed for linear complementarity problems associated with positive definite symmetric matrices. Efficient blossom algorithms have been developed for edge covering problems and 1-matchingcovering problems in undirected networks, as well as efficient subroutines for performing various types of sensitivity analysis. A computer package for 1-matchingcovering algorithms suitable for large scale applications has been developed. A bounding strategy for the set covering problem based on the 1-matchingcovering problem and Lagrangean relaxation has been developed. Efficient linear time algorithms have been developed for checking the adjacency of two given 1-matchingcovering incidence vectors on the 1-matchingcovering polytope.