Methods for Solving Linear and Nonlinear Mixed Integer Programs

几个库存，生产和工艺计划，布局，位置，物流，预算，财务计划和投资问题建模为线性或非线性混合整数方案。这些模型在优化大中型企业的操作时出现，并且被认为非常困难。虽然实际问题的模型涉及数千个变量，但只有非常小的问题（几百个变量）在实践中得到了解决。以前的工作为解决这些问题引入了几个新思路。这些成果是：(1)发展了一种新的0-1混合凸问题的分支切法；(2)非线性切割对非线性与线性混合0-1问题的应用；(3)生成0-1和整数混合线性问题的近最优顶点解切割。这些思想需要进一步完善，以转化为实用的计算方法来解决通用的线性和非线性混合整数规划。该项目将研究使用析取规划生成的凸混合0-1问题的切割的有效性，并将研究如何有效地生成这些切割。本文将研究半定松弛在这种情况下的应用，以及它们在求解非线性混合0-1规划中的价值。利用非线性切割来解决这些问题也将被研究。如果成功，本研究将使可成功解决的复杂非线性整数程序的规模增加一个数量级。该研究包括实验和软件开发（计算）部分，其中将进行广泛的测试以验证研究思想的实用性。由于研究的是求解具有一般结构的线性和非线性整数模型的方法，从实践的角度来看，一个成功的成果有望对求解现实世界的模型产生最广泛的影响。

Several inventory, production and process planning, layout, location, logistics, budgeting, financial planning and investment problems are modeled as linear or nonlinear mixed integer programs. These models arise when optimizing operations of medium to large size enterprises and are considered very hard. Although models for practical problems involve thousands of variables, only problems of very small size(a few hundred variables) have been solved in practice. Previous work introduced several new ideas towards solving these problems. These are: (1) development of a new branch-and-cut method for mixed convex 0-1 problems; (2) the use of nonlinear cuts for nonlinear and linear mixed 0-1 problems; and (3) generating cuts at near optimal vertex solutions for mixed linear 0-1 and integer problems. These ideas need further refinement to convert them into a practical computational methodology for solving general-purpose linear and nonlinear mixed integer programs. This project will study the effectiveness of cuts generated using disjunctive programs for the convex mixed 0-1 problems, and will investigate how these cuts can be generated efficiently. The use of semi-definite relaxations in this context will be investigated as well as their value in solving nonlinear mixed 0-1 programs. The use of nonlinear cuts for solving these problems will also be investigated. If successful, this research will increase the size of difficult nonlinear integer program that can be successfully solved by an order of magnitude. The research has an experimental and software development (computational) component where extensive testing will be performed to validate the practicality of the researched ideas. Since the research is on development of methods for solving linear and nonlinear integer models with general structure, from a practical point of view, a successful outcome is expected to have the widest impact in solving real world models.