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.