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.