Methods for Solving Mixed Integer Programs Using Adjoint Lattices

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

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.