Methods for Solving Linear and Nonlinear Mixed Integer Programs

求解线性和非线性混合整数规划的方法

• 批准号: 9908038
• 负责人: Sanjay Mehrotra
• 金额: $ 20.32万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9908038&HistoricalAwards=false
• 关键词: Methods; Solving; Linear; Nonlinear; Mixed

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.

多个库存、生产和工艺计划、布局、选址、物流、预算、财务计划和投资问题被建模为线性或非线性混合整数规划。这些模型是在大中型企业优化运营时出现的，被认为是非常困难的。尽管实际问题的模型涉及数千个变量，但在实践中只解决了非常小的问题(几百个变量)。以前的工作介绍了几个解决这些问题的新想法。它们是：(1)发展了一种新的混合凸0-1问题的分枝割方法；(2)对于非线性和线性混合0-1问题，使用了非线性割；(3)对于混合线性0-1和整数问题，在接近最优的顶点解上生成割。这些思想需要进一步改进，以将它们转化为求解通用线性和非线性混合整数规划的实用计算方法。这个项目将研究用析取程序生成的割集对于凸混合0-1问题的有效性，并将研究如何有效地生成这些割集。本文将研究半定松弛的使用以及它们在求解非线性混合0-1规划中的价值。还将研究利用非线性割集来解决这些问题。如果成功，这项研究将使能够成功求解的困难的非线性整数规划的规模增加一个数量级。这项研究有一个实验和软件开发(计算)部分，其中将进行广泛的测试，以验证所研究的想法的实用性。由于研究的重点是开发求解具有一般结构的线性和非线性整数模型的方法，从实用的角度来看，成功的结果有望对现实世界模型的求解产生最广泛的影响。