9401424 Lee The research is concerned with the modeling and investigation of solution techniques for nonlinear-objective combinatorial optimization problems. Three basic solution techniques are to be investigated. These techniques are (1) a combination of linearization and polyhedral methods, (2) combination of eigenvalue bounding methods with polyhedral and Lagrangian methods, and (3) model assessment through geometric methods. Three classes of problems are identified as sources of problems to be used in testing the models and their solution methods. The application areas for which the algorithms will be tested are network design problems with inter-link costs, fixed charge facility location problems, and experimental design problems. The outcome of this research are the development of (1) more general methods for tightening integer programming formulations of difficult discrete planning problems with nonlinear objective function, (2) techniques for integrating algebraic bounding methods for planning problems with nonlinear objective functions, and (3) general principles for the design of branch-and-cut procedures for integer programming based approaches for discrete planning problems with both linear and nonlinear objective function. Other outcomes of the research will be the development of understanding similar to those of planning problems in network design and experimental design problems.
