A CHARACTERIZATION OF THE UNCAPACITATED NETWORK DESIGN POLYTOPE

被引：13

作者：

HELLSTRAND, J ^{[1
]}

LARSSON, T ^{[1
]}

MIGDALAS, A ^{[1
]}

机构：

[1] LINKOPING UNIV,DEPT MATH,S-58183 LINKOPING,SWEDEN

来源：

OPERATIONS RESEARCH LETTERS | 1992年 / 12卷 / 03期

关键词：

UNCAPACITATED NETWORK DESIGN; QUASI-INTEGRALITY; INTEGER PROGRAMMING; POLYHEDRAL COMBINATORICS; LINEAR PROGRAMMING;

D O I：

10.1016/0167-6377(92)90100-H

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The uncapacitated network design problem is considered. We show that the feasible polytope of the continuous relaxation of this problem has the property that any path along the edges of the convex hull of its integer points is also a path along the edges of the polytope itself. This property may be of computational interest since it implies the possibility of solving the uncapacitated network design problem by a pivoting scheme.

引用

页码：159 / 163

页数：5

共 10 条

[1]

Balas E., 1972, OPER RES, V20, P1153

[2]

BALAS E, 1975, OPER RES, V23, P75

[3]

BALAS E, 1975, COMBINATORIAL PROGRA

[4]

GAL T, 1990, 149A FERN HAG WORK P

[5]

Heller I, 1956, LINEAR IN EQUALITIES, V38, P247

[6] SIMPLEX PIVOTS ON THE SET PACKING POLYTOPE [J].

IKURA, Y ;

NEMHAUSER, GL .

MATHEMATICAL PROGRAMMING, 1985, 33 (02) :123-138

[7] NETWORK DESIGN AND TRANSPORTATION-PLANNING - MODELS AND ALGORITHMS [J].

MAGNANTI, TL ;

WONG, RT .

TRANSPORTATION SCIENCE, 1984, 18 (01) :1-55

[8]

Schrijver A., 1986, THEORY LINEAR INTEGE

[9]

Trubin V, 1969, SOVIET MATH DOKLADY, V10, P1544

[10]

Yemelichev V. A., 1984, POLYTOPES GRAPHS OPT

← 1 →