【作者】 达林；

【导师】 查建中；

【作者基本信息】 北京交通大学 ， 载运工具运用工程， 2009， 博士

【摘要】 混合整数非线性规划(Mixed Integer Nonlinear Programming,MINLP)是一类包含连续和整数变量的非线性规划问题。MINLP是整数规划的一个重要分支,近几十年来MINLP的应用有了快速的发展,其应用领域包括流程工业、金融、工程、管理科学和运筹学等各个领域。MINLP问题的求解算法包括确定型算法和启发式算法,确定型算法是将难于求解的MINLP问题分解为相对容易求解的混合整数线性规划问题(Mixed Integer Linear Programming,MILP),其中一类分解方法是通过投影及对偶等方法将MINLP问题分解为MILP问题,另外一类是利用迭代构造切平面的方法将原问题分解为简单问题。本文的目标是通过对求解凸MINLP问题的各种确定型算法的研究,明确切平面在确定型算法中的重要作用,利用切平面的构造方法对已知算法进行改进,并争取构造出新的算法。本文首先给出了切平面在确定型算法中的作用,给出了切平面构造的位置和方法与各种算法收敛速度的关系,得出结论:切平面的构造影响算法的收敛速度,一般来说在非线性可行域边界上构造切平面的算法具有快的收敛速度,非线性可行域边界上构造的切平面称为支撑超平面;又MINLP问题的性质要求最优解为整数点,因此如果可以给出在整数点处快速生成支撑超平面的方法,就得到了一个简洁且收敛速度快的确定型算法。基于此我们给出了求解MINLP问题的支撑超平面算法的一般形式,并证明了其收敛性,同时提出了三个具体支撑超平面算法,分别为平行下降支撑超平面算法,基于内点的支撑超平面算法和不基于内点的支撑超平面算法。外逼近(Outer Approximation,OA)算法是求解MINLP问题的一个重要算法,有着很广泛的应用,该算法的缺点是需要利用两个NLP问题的求解。我们将SHP算法的思想引入到OA算法中,给出改进的OA算法,我们称新的算法为EOA(Extended Outer Approximation,EOA)算法。在EOA算法中,当第一个非线性规划问题无解时,利用Vinott’s SHP算法生成一个支撑超平面,替换OA算法中通过求解第二个NLP问题生成的切平面。新算法继承了OA算法在非线性可行域边界整数点生成切平面的优势,同时减少了NLP问题的求解次数。启发式算法和确定型算法是求解MINLP问题的两个不同类型的算法,确定型算法在求解MINLP问题时可以保证解的全局最优性,但对大规模问题的求解需要很长的计算时间,启发式方法不能保证解的全局最优,但求解问题时具有快速、简单的特点。本文我们给出了一种将启发式算法转化为确定型算法的切平面方法,新的算法继承了切平面方法全局收敛和启发式算法效率高的特点,并保证了算法的收敛速度和全局最优性,我们称这种算法为启发式切平面算法。更多还原

【Abstract】 Mixed Integer Nonlinear Programming (MINLP) refers to mathematical programming with continuous and integer variables. MINLP which is an important class of Integer Programming (IP) has experience tremendous progress in recent years. MINLP have been used in various applications, including process industry, financial, engineering, management science and operations research sectors. Algorithms which are proposed for solving MINLP include deterministic methods and heuristic methods. The deterministic methods target the formulation of sub-problems that are easier to solve than the original. One main decomposition idea involves projection and duality, and another decomposition idea is based on the generating of cutting planes.According to the study of the deterministic algorithms, we found that the cutting plane act an important role in the construction of the deterministic algorithms. Aim of present paper is to study function of cutting plane, and using cutting plane to improve or construct new algorithms. Function of cutting plane in deterministic algorithms is present first, relations of deterministic algorithms and position and method of generating cutting plane are shown following.According to the study of cutting plane, we found that the construction of cutting plane influence convergence speed of the different method. Generally, when the cutting planes are generated at boundary of nonlinear feasible region, the algorithms has fast convergence speed. It is called supporting hyperplane, when the cutting planes are generated at boundary of nonlinear feasible region. If the supporting hyperplane can be generate easily and quickly, the algorithms are constructed with fast convergence speed. Based on the theory discussed above, three kind of supporting hyperplane algorithm are presented. Outer Approximation (OA) method is an important algorithm and widely used for solving MINLP problems. Based on the study of OA, we improved OA method and a Extended OA (EOA) is presented, the EOA method can reduce complexity of OA method.Heuristic algorithm and deterministic algorithm are two broad classes method for solving MINLP problems. When given enough time and provide the problem satisfies certain conditions such as convexity, the deterministic algorithm can terminate with a guaranteed solution or an indication that the problem has no integer solution. If MINLP problems needed to be solved has large scale, that it becomes prohibitive to us a deterministic approach, then one has to resort to heuristic algorithm, which do not provide a guarantee that on termination the incumbent is a minimize. But heuristic algorithms, wildly applied in practical problems, are usually faster and more convenient than deterministic algorithms. At last, a kind of cutting plane method of transform the heuristic algorithms to deterministic algorithms is presented, and the new proposed method utilized the character of fast convergence speed of heuristic algorithms and the character of guaranteed solution of deterministic algorithms. The new proposed method is called heuristic cutting plane method.更多还原