An LP/NLP based branch and bound algorithm for convex MINLP optimization problems
An LP/NLP based branch and bound algorithm for convex MINLP optimization problems
复制标题
DOI：
10.1016/0098-1354(92)80028-8
复制
发表时间：
1992-10
影响因子：
4.3
通讯作者：
I. Quesada;I. Grossmann
中科院分区：
文献类型：
--
作者：
I. Quesada;I. Grossmann
本文旨在提高凸MINLP问题的求解效率，该问题的瓶颈在于0-1变量的组合搜索。提出了一种基于LP/NLP的分支定界算法，该算法在每次主迭代中避免了MILP主问题的显式解。相反，主问题是在树搜索期间动态定义的，以减少需要枚举的节点数量。通过求解LP子问题进行分支定界搜索预测下界，直到找到可行的整数解。在这些节点上求解非线性规划子问题，提供上界和新的线性近似，用于收紧搜索树中开放节点的线性表示。为了减小线性规划子问题的规模，提出了一种利用线性子结构的线性逼近方法。本文报道了几个测试问题的初步数值结果，结果表明，在大多数情况下，需要解决的NLP子问题数量保持不变的情况下，求解MI的费用需要枚举。
This paper is aimed at improving the solution efficiency of convex MINLP problems in which the bottleneck lies in the combinatorial search for the 0–1 variables. An LP/NLP based branch and bound algorithm is proposed in which the explicit solution of an MILP master problem is avoided at each major iteration. Instead, the master problem is defined dynamically during the tree search to reduce the number of nodes that need to be enumerated. A branch and bound search is conduced to predict lower bounds by solving LP subproblems until feasible integer solutions are found. At these nodes nonlinear programming subproblems are solved, providing upper bounds and new linear approximations which are used to tighten the linear representation of the open nodes in the search tree. To reduce the size of the LP subproblems, new types of linear approximations are proposed which exploit linear substructures in the MINLP problem. Preliminary numerical results on several test problems are reported which show that the expense of solving the MI need to be enumerated, while in most cases the number of NLP subproblems to be solved remains the same.