Network design arc set with variable upper bounds. (English) Zbl 1122.90053
Authors’ abstract: We study the network design arc set with variable upper bounds. This set appears as a common substructure of many network design problems and is a relaxation of several fundamental mixed-integer sets studied earlier independently. In particular, the splittable flow arc set, the unsplittable flow arc set, the single node fixed-charge flow set, and the binary knapsack set are facial restrictions of the network design arc set with variable upper bounds. Here we describe families of strong valid inequalities that cut off all fractional extreme points of the continuous relaxation of the network design arc set with variable upper bounds. Interestingly, some of these inequalities are also new even for the aforementioned restrictions studied earlier.
Reviewer: Hartmut Noltemeier (Würzburg)
MSC:
| 90C11 | Mixed integer programming |
| 90C35 | Programming involving graphs or networks |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90B15 | Stochastic network models in operations research |
Keywords:
network design; mixed-integer rounding; flow covers; cutting planes; polyhedral structure; strong valid inequalities; families of strong valid inequalitiesReferences:
| [1] | Atamtürk, Oper Res Lett 29 pp 107– (2001) |
| [2] | Atamtürk, Math Program 92 pp 425– (2002) |
| [3] | Atamtürk, Math Program 98 pp 145– (2003) |
| [4] | Atamtürk, Oper Res 52 pp 487– (2004) |
| [5] | , Network design arc set with variable upper bounds, IBM Research Report, RC23598, 2005. |
| [6] | Atamtürk, Math Program 92 pp 315– (2002) |
| [7] | Balas, Math Program 8 pp 146– (1975) |
| [8] | Balas, SIAM J Appl Math 34 pp 119– (1978) |
| [9] | Bienstock, INFORMS J Comput 8 pp 243– (1996) |
| [10] | , , Designing private line networks–Polyhedral analysis and computation, CORE Discussion Paper 9647, Université Catholique de Louvain, Louvain-la-Nueve, Belgium, 1996. |
| [11] | Gu, INFOMRS J Comput 10 pp 427– (1998) |
| [12] | Gu, INFORMS J Comput 11 pp 117– (1999) |
| [13] | Gu, Math Program 85 pp 439– (1999) |
| [14] | Gu, J Combin Optim 4 pp 109– (2000) |
| [15] | Hammer, Math Program 8 pp 179– (1975) |
| [16] | Klabjan, Math Oper Res 27 pp 711– (2002) |
| [17] | , Lifting, superadditivity, mixed integer rounding, and single node flow sets revisited, CORE Discussion Paper 2003/1, Université Catholique de Louvain, Louvain-la-Nueve, Belgium, 2003. |
| [18] | Magnanti, Math Program 60 pp 233– (1993) |
| [19] | Marchand, Oper Res 49 pp 363– (2001) |
| [20] | Nemhauser, Math Program 46 pp 379– (1990) |
| [21] | Padberg, Oper Res 23 pp 833– (1979) |
| [22] | Padberg, Oper Res 32 pp 842– (1984) |
| [23] | Stallaert, Discrete Appl Math 77 pp 73– (1997) |
| [24] | van Hoesel, Math Program 92 pp 335– (2002) |
| [25] | Wolsey, Math Program 8 pp 165– (1975) |
| [26] | Wolsey, Oper Res 24 pp 367– (1976) |
| [27] | Integer programming, Wiley, New York, 1998. · Zbl 0930.90072 |
| [28] | Zemel, Math Program 15 pp 268– (1978) |
| [29] | Zemel, Math Oper Res 14 pp 760– (1989) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
