Application Of Cutting Plane Method In MINLP Problems

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.