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 条
  • [21] Parameterized complexity of k-Chinese Postman Problem
    Gutin, Gregory
    Muciaccia, Gabriele
    Yeo, Anders
    THEORETICAL COMPUTER SCIENCE, 2013, 513 : 124 - 128
  • [22] THE MAXIMUM BENEFIT CHINESE POSTMAN PROBLEM AND THE MAXIMUM BENEFIT TRAVELING SALESMAN PROBLEM
    MALANDRAKI, C
    DASKIN, MS
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 65 (02) : 218 - 234
  • [23] A NOTE ON K-BEST SOLUTIONS TO THE CHINESE POSTMAN PROBLEM
    Saruwatari, Yasufumi
    Matsui, Tomomi
    SIAM JOURNAL ON OPTIMIZATION, 1993, 3 (04) : 726 - 733
  • [24] SOLVABLE CASES OF THE K-PERSON CHINESE POSTMAN PROBLEM
    PEARN, WL
    OPERATIONS RESEARCH LETTERS, 1994, 16 (04) : 241 - 244
  • [25] Uncertain Programming Model for Chinese Postman Problem with Uncertain Weights
    Zhang, Bo
    Peng, Jin
    INDUSTRIAL ENGINEERING AND MANAGEMENT SYSTEMS, 2012, 11 (01): : 18 - 25
  • [26] A 3/2-approximation algorithm for the mixed postman problem
    Raghavachari, B
    Veerasamy, J
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (04) : 425 - 433
  • [27] A branch-and-cut algorithm for the maximum benefit Chinese postman problem
    Corberan, Angel
    Plana, Isaac
    Rodriguez-Chia, Antonio M.
    Sanchis, Jose M.
    MATHEMATICAL PROGRAMMING, 2013, 141 (1-2) : 21 - 48
  • [28] A branch-and-cut algorithm for the maximum benefit Chinese postman problem
    Ángel Corberán
    Isaac Plana
    Antonio M. Rodríguez-Chía
    José M. Sanchis
    Mathematical Programming, 2013, 141 : 21 - 48
  • [29] Technical Note: Solving the "Chinese postman problem" for effective contour deformation
    Wang, Jingqian
    Zhang, Yongbin
    Zhang, Lifei
    Dong, Lei
    Balter, Peter A.
    Court, Laurence E.
    Yang, Jinzhong
    MEDICAL PHYSICS, 2018, 45 (02) : 767 - 772
  • [30] Capacitated Postman Problem
    Fabry, Jan
    Pelikan, Jan
    MATHEMATICAL METHODS IN ECONOMICS 2013, PTS I AND II, 2013, : 153 - 158
12345