ON THE MIXED CHINESE POSTMAN PROBLEM

被引：14
|
作者：
RALPHS, TK
机构：
[1] School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY
来源：
OPERATIONS RESEARCH LETTERS | 1993年 / 14卷 / 03期
基金：
美国国家科学基金会;
关键词：
CHINESE POSTMAN PROBLEM; HALF-INTEGRALITY; GRAPH; FLOW;
D O I：
10.1016/0167-6377(93)90021-8
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The mixed Chinese postman problem is a version of the well-known Chinese postman problem in which the underlying graph consists of both directed and undirected edges. We give an integer linear programming formulation for this problem and then show that the extreme points of its linear relaxation polyhedron are all half-integral.
引用
收藏
页码：123 / 127
页数：5
相关论文
共 50 条
12345