Methods for Solving Linear and Nonlinear Mixed Integer Programs

点击翻译按钮获取中文摘要

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.