带多项式量级约束条件的多商品流BWTSP线性规划  

A Multi-Commodity Flow Linear Programming with Polynomial Constraints for Black and White Traveling Salesman Problem

作　　者：江贺[1] 张宪超[1] 车皓阳[2] 陈国良[3] 

机构地区：[1]大连理工大学软件学院,大连116621 [2]中国科学院软件研究所,北京100080 [3]中国科学技术大学计算机科学与技术系,合肥230027

出　　处：《计算机研究与发展》2007年第10期1796-1800,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60673046;60673066);辽宁省自然科学基金项目(20051082);大理理工大学青年教师培养基金项目

摘　　要：黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n2+n+2|B|个权值约束条件.最终得到原始问题仅包含3n2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.The black and white salesman problem（BWTSP） is a new NP-hard problem,which can be divided into the undirected BWTSP and the directed BWTSP according to the symmetry of edges in graph.As a basis of complete algorithm design for NP-hard problems,the number of constraints in linear programming（LP） remarkably influences the complexity of algorithm design.The existing Ghiani LP for the undirected BWTSP contains an exponential number of constraints.For a special case of the direct BWTSP whose L=＋∞,its LP with polynomial constraints can be obtained by being transformed into RATSP.However,there exists no LP for the general directed BWTSP.A new LP with polynomial constraints for the directed BWTSP is proposed.Firstly,the directed BWTSP is reduced to ATSP whenever Q=L=＋∞.Then,based on the Finke-Claus-Gunn LP with n（n＋4） constraints of ATSP,the n^2＋2｜W｜ cardinality constraints can be acquired by defining residual and used cardinality commodity flow.Finally,the new n^2＋n＋2｜B｜ weight constraints are obtained by similar ways.In this way,the new LP with 3n^2＋7n constraints only can be eventually acquired.Since the undirected BWTSP and the directed BWTSP with L=＋∞ are both special cases of the directed BWTSP,the results can be applicable to them too.

关 键 词：黑白旅行商问题 NP-难解 线性规划 完全算法 商品流 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]