EXPRESSING COMBINATORIAL OPTIMIZATION PROBLEMS BY LINEAR-PROGRAMS
EXPRESSING COMBINATORIAL OPTIMIZATION PROBLEMS BY LINEAR-PROGRAMS
复制标题
DOI：
10.1016/0022-0000(91)90024-y
复制
发表时间：
1991-12-01
影响因子：
1.1
通讯作者：
YANNAKAKIS, M
中科院分区：
文献类型：
--
作者：
YANNAKAKIS, M
1.引言许多组合优化问题要求在解向量的离散集S上优化线性函数C 'x。例如，在旅行推销员问题（TSP）的情况下。X=（Xij）是11维变量向量，其坐标对应于n个节点上的完全图Ki的边，c是城市间距离的向量，并且SG（{0，1}）是n个城市的图尔斯的特征向量的集合（被认为是Ki的边的子集）。在加权（完美）匹配问题的情况下，S是Ki（n偶数）的完美匹配的特征向量的集合。这类问题等价于：min（max）c 'x服从x E凸船体（S）.解的凸船体是一个多面体，它的名字来自相应的问题：TSP（分别是）。匹配）多面体。类似的多面体已被定义和广泛研究的其他常见问题：（加权）二部完美匹配（分配多面体），最大独立集和团问题（顶点包装和团多面体），等优化一个线性函数在一个多面体允许免费复制的全部或部分本材料被授予提供领带副本不直接商业利益，ACM版权声明和出版物的标题和日期ap-pc~ r。并注意到复制是由计算机协会的许可。复制，否则，或重新发布，需要收费和/或许可证。
1. INTRODUCTION Many combinatorial optimization problems call for the optimization of a linear function c’x over a discrete set S of solution vectors. For example, in the case of the Tr veling Salesman Problem (TSP). X=(Xij) is an 11;-dimensional variable vector whose coordinates correspond to the edges of the complete graph K, on n nodes, c is the vector of inter-city distances, and SG(’{O, l) is the set of characteristic vectors of the tours of n cities (considered as subsets of the edges of K,,). In the case of the weighted (perfect) matching problem, S is the set of characteristic vectors of the perfect matchings of K,(n even). These problems are equivalent to: min (max) c’x subject to x E convex hull (S). The convex hull of the solutions is a polytope, which takes its name from the corresponding problem: the TSP (resp. matching) polytope. Analogous polytopes have been defined and studied extensively for other common problems:(weighted) bipartite perfect matching(assignment polytope), maximum independent set and clique problem (vertex-packing and clique polytopes), etc. Optimizing a linear function over a polytopePermission to copy without fee all or part of this material is granted provided that tie copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date ap-pc~ r. and notice is given that copying is by Permission of the Associslion for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or sP&fic permission.