A branch and cut algorithm for hub location problems with single assignment

被引：96

作者：

Labbé, M

Yaman, H

Gourdin, E

机构：

[1] Free Univ Brussels, Serv Optimisat, B-1050 Brussels, Belgium

[2] Bilkent Univ, Dept Ind Engn, TR-06800 Ankara, Turkey

[3] France Telecom R&D, DAC OAT, F-92794 Issy Les Moulineaux, France

来源：

MATHEMATICAL PROGRAMMING | 2005年 / 102卷 / 02期

关键词：

hub location; polyhedral analysis; branch and cut;

D O I：

10.1007/s10107-004-0531-x

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. The aim of this paper is to investigate polyhedral properties of these problems and to develop a branch and cut algorithm based on these results.

引用

页码：371 / 405

页数：35

共 25 条

[11]

Goemans MX, 1997, APPROXIMATION ALGORI, P144

[12]

Gourdin E, 2002, FACILITY LOCATION APPLICATIONS AND THEORY, P275

[13]

Grotschel M, 2012, Geometric algorithms and combinatorial optimization, V2

[14]

Gu Z., 1998, INFORMS Journal on Computing, V10, P427, DOI 10.1287/ijoc.10.4.427

[15] FACET OF REGULAR 0-1 POLYTOPES [J].

HAMMER, PL ;

JOHNSON, EL ;

PELED, UN .

MATHEMATICAL PROGRAMMING, 1975, 8 (02) :179-206

[16]

Jünger M, 2000, SOFTWARE PRACT EXPER, V30, P1325, DOI 10.1002/1097-024X(200009)30:11<1325::AID-SPE342>3.0.CO

[17]

2-T

[18] VALID INEQUALITIES AND FACETS OF THE CAPACITATED PLANT LOCATION PROBLEM [J].

LEUNG, JMY ;

MAGNANTI, TL .

MATHEMATICAL PROGRAMMING, 1989, 44 (03) :271-291

[19]

Martello S., 1990, KNAPSACK PROBLEMS AL

[20]

Padberg M. W., 1973, Mathematical Programming, V5, P199, DOI 10.1007/BF01580121

← 1 2 3 →