Research Initiation: Investigations in Nonlinear-Objective Combinatorial Optimization

[401424]李本研究涉及非线性目标组合优化问题的建模和求解技术的研究。三种基本的解决技术将被研究。这些技术是(1)线性化和多面体方法的结合，(2)特征值边界法与多面体和拉格朗日方法的结合，以及(3)通过几何方法进行模型评估。在测试模型及其解决方法时，确定了三类问题作为问题的来源。算法将被测试的应用领域是具有互连成本的网络设计问题、固定收费设施位置问题和实验设计问题。本研究的成果是：(1)对具有非线性目标函数的困难离散规划问题的整数规划公式的更一般的紧化方法的发展，(2)对具有非线性目标函数的规划问题的积分代数边界法的技术，(3)具有线性和非线性目标函数的离散规划问题的基于整数规划方法的分支切断程序设计的一般原则。研究的其他结果将是发展理解类似于网络设计和实验设计问题中的规划问题。

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.