一类组合优化问题与非凸二次规划的等价

The Equivalence between a Class of Combinatorial Optimization Problems and a Special Class of Nonconvex Quadratic Programming

本文研究一类著名的组合优化问题,如旅行商问题,k-着色问题和最大切割问题等。首先构造了它们的一个特殊的二次0-1规划模型(Ⅰ),然后证明了(Ⅰ)与其松驰问题(Ⅱ)在最优性意义下的等价性,从而建立了这类组合优化问题与一类特殊的非凸二次(连续)规划之间的联系,提供了一种用连续二次规划的算法求解这类组合优化问题的途径,为这类难题的算法研究开辟了一个新的方向。

This paper considers a class of famous difficult problems in network palanning, such as the travelling salesman problem, k-colored problem and maximum cut problem. Firstly, it constructs a spectial class of 0-1 quadratic programming (I) to formulate these problems,and then verifies that (I) is equivalent to its relaxed problem (I) in the sense of optimizaion, and establishes the connection between these combinatorial probelms and a kind of special (continnuous) nonconvex quadratic programming, providing a new way to solve this class of combinatorial problems by use of the nonlinear programming algorithms.