Methods for Solving Mixed Integer Programs Using Adjoint Lattices

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

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.