Methods for Solving Mixed Integer Programs Using Adjoint Lattices

使用伴随格求解混合整数规划的方法

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

This grant provides funding for developing advanced solution methodology for mixed integer programming problems using the adjoint lattice basis approach recently developed by the PI. The mixed integer problems are optimization problems that involve integer and continuous variables in the optimization model. The models may have nonlinear constraints in addition to the linear constraints. Models involving general integer variables with nonlinear constraints are very hard to solve. These models arise in engineering and management problem areas such as inventory, production and chemical process planning, layout, logistics and financial optimization. For example, non-linearity arises naturally while modeling uncertainty using the second moment. There has been some, but limited progress towards solving large scale models of this type. This proposal on the development of integer programming methodology will improve our ability to solve problems from this wide range of application areas. The adjoint lattice concept allows us to describe these algorithms in the original space, without requiring any problem dimension reductions required in earlier developments of branching on hyperplane type algorithms. As a result we are able to perform several steps of these algorithms in the space of original variables. The use of adjoint lattice allows for new possibilities of "more intelligent" computations of branching hyperplanes, for example, the adjoint lattice framework opens up the possibility of computing branching hyperplanes more heuristically, and allows for the possibility of alternative computations for generating cutting planes, and feasible integer solutions. The restructuring also allows alternative ways of computing a feasible integer solutions. This research will further develop the adjoint lattice methodology. In particular, we will develop (i) methods for using approximate adjoint lattices when generating branching hyperplanes; (ii) branch-and-cut algorithms for mixed integer nonlinear programming problems using adjoint lattices; (iii) methods for generating feasible solutions in the original space without computing kernel lattices; (iv) study the use of segment lattice basis reduction methods in our context; (iv) study more efficient methods for finding analytic or volumetric centers of continuous relaxations; (v) branch-and-cut algorithms for mixed integer nonlinear programming problems when the constraint functions are not differentiable. This development will allow the use of adjoint lattice based methodology for solving large sparse mixed integer programs.

该补助金提供资金，用于使用PI最近开发的伴随格基方法开发混合整数规划问题的高级解决方法。 混合整数优化问题是在优化模型中包含整数和连续变量的优化问题。 除了线性约束之外，模型还可以具有非线性约束。 含有一般整数变量和非线性约束的模型很难求解。 这些模型出现在工程和管理问题领域，如库存，生产和化学工艺规划，布局，物流和财务优化。例如，当使用二阶矩对不确定性建模时，自然会出现非线性。 已经有一些，但有限的进展，以解决这种类型的大规模模型。 这个关于整数规划方法的发展的建议将提高我们解决这一广泛应用领域的问题的能力。 伴随格的概念使我们能够在原始空间中描述这些算法，而不需要任何问题的维数减少所需的分支超平面型算法的早期发展。 因此，我们能够在原始变量的空间中执行这些算法的几个步骤。 伴随格的使用允许分支超平面的“更智能”计算的新可能性，例如，伴随格框架打开了更直观地计算分支超平面的可能性，并且允许用于生成切割平面的替代计算的可能性，以及可行的整数解。 重构还允许计算可行整数解的替代方式。 本研究将进一步发展伴随格方法。 特别是，我们将开发（i）在生成分支超平面时使用近似伴随格的方法;（ii）使用伴随格的混合整数非线性规划问题的分支和切割算法;（iii）在不计算核格的情况下在原始空间中生成可行解的方法;（iv）研究在我们的上下文中使用分段格基约简方法;（iv）研究更有效的方法来寻找连续松弛的解析或体积中心;（v）当约束函数不可微时，混合整数非线性规划问题的分支切割算法。 这一发展将允许使用伴随格为基础的方法来解决大型稀疏混合整数规划。