Generalized Branch-and-Cut Method for Mixed Integer Programming

含有一般整数变量和非线性约束的模型是很难求解的。在解决这种类型的大规模模型方面已经取得了一些进展，但进展有限。对实际测试问题的计算结果表明，最优目标值与松弛问题解在根结点的界之间的差距明显大于线性情况下得到的界，枚举树的大小迅速爆炸。为了克服解决这类大规模问题的困难，需要在几个方向上取得进展。需要进一步开发生成好的切割平面的方法，以及需要开发更先进的启发式算法来快速识别可行解。然而，我们认为，最根本的进步可能来自于分支切割方法中高级分支方案的发展。标准分支方案一次只对一个变量析取进行分支。Lenstra证明了通过在一般超平面上分支，我们可以在多项式时间内解决混合整数线性规划问题。伦斯特拉的算法已经发现了有限的实用价值。这是因为在他的算法中寻找分支超平面的计算代价很高。然而，有可能找到“质量好”但计算上不那么昂贵的分支飞机。本文将围绕这一问题以及求解非线性混合整数规划的相关问题展开研究。一些工程和管理问题导致模型是非线性的，可能是随机的，整数规划。这些问题领域包括库存、生产和化工流程规划、布局、选址、物流和财务优化。例如，在使用二阶矩对不确定性进行建模时，自然会出现非线性。这项提案要求资金支持我们正在进行的寻找解决此类模型的有效技术的研究。发展解决非线性整数规划问题的通用求解方法将产生广泛的影响，因为它将有助于解决来自许多不同领域的此类问题。

Models involving general integer variables with nonlinear constraints are very hard to solve. There has been some, but limited progress towards solving large scale models of this type. Computational results on practical test problems suggest that the gap between the optimum objective value and a bound from the solution of the relaxed problem at the root node is significantly larger when compared with bounds obtained in the linear case, and the size of the enumeration tree explodes quickly. To overcome the difficulties in solving large scale problems of this type, advances in several directions are needed. Methods for generating good cutting planes need to be developed further, as well as more advanced heuristics for identifying a feasible solution quickly need to be developed. However, we think that the most fundamental advance may come from the development of advanced branching schemes in a branch-and-cut method. The standard branching schemes branch on a single variable disjunction at a time. Lenstra showed that by branching on general hyperplanes we can solve a mixed integer linear programming problem in polynomial time. Lenstra's algorithm has found limited practical value. This is because the computational cost of finding the branching hyperplane in his algorithm is very high. However, there is a possibility for finding branching planes that are ``good quality'' but computationally not as expensive. This research will focus on this problem as well as related issues towards solving nonlinear mixed integer programs.Several engineering and management problems lead to models that are nonlinear, possibly stochastic, integer programs. These problem areas include inventory, production and chemical process planning, layout, location, logistics and financial optimization. For example, nonlinearity arises naturally while modeling uncertainty using the second moment. This proposal request funds to support our ongoing research for finding efficient techniques for solving such models. The development of general purpose solution methodology for solving nonlinear integer programming problem will have a wide ranging impact, as it would facilitate solving such problems arising from many different areas.