0-1 reformulations of the multicommodity capacitated network design problem. (English) Zbl 1168.90002
Summary: We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.
Keywords:
multicommodity capacitated network design; reformulation; valid inequalities; cutting-plane method; column generationReferences:
| [1] | Agarwal, Y. K., Design of capacitated multicommodity networks with multiple facilities, Operations Research, 50, 333-344 (2002) · Zbl 1163.90381 |
| [2] | Atamtürk, A., On capacitated network design cut-set polyhedra, Mathematical Programming, 92, 425-437 (2002) · Zbl 1008.90003 |
| [3] | Atamtürk, A.; Günlük, O., Network design arc-set with variable upper bounds, Networks, 50, 17-28 (2007) · Zbl 1122.90053 |
| [4] | Atamtürk, A.; Rajan, D., On splittable and unsplittable flow capacitated network design arc-set polyhedra, Mathematical Programming, 92, 315-333 (2002) · Zbl 1094.90005 |
| [5] | Avella, P.; D’Auria, B.; Salerno, S., A LP-based heuristic for a time-constrained routing problem, European Journal of Operational Research, 173, 120-124 (2006) · Zbl 1125.90031 |
| [6] | Balakrishnan, A.; Graves, S., A composite algorithm for a concave-cost network flow problem, Networks, 19, 175-202 (1989) · Zbl 0673.90034 |
| [7] | Balakrishnan, A.; Magnanti, T. L.; Mirchandani, P., Network design, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), John Wiley and Sons), 311-334 · Zbl 1068.90503 |
| [8] | Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Operations Research, 28, 1130-1154 (1980) · Zbl 0449.90064 |
| [9] | Barahona, F., Network design using cut inequalities, SIAM Journal on Optimization, 6, 823-837 (1996) · Zbl 0856.90112 |
| [10] | Barnhart, C.; Hane, C. A.; Vance, P., Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems, Operations Research, 48, 318-326 (2000) |
| [11] | Barnhart, C.; Jin, H.; Vance, P. H., Railroad blocking: A network design application, Operations Research, 48, 603-614 (2000) |
| [12] | Belotti, P.; Brunetta, L.; Malucelli, F., Multicommodity network design with discrete node costs, Networks, 49, 90-99 (2007) · Zbl 1131.90006 |
| [13] | Ben Hamor, H.; Desrosiers, J., Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems, Computers & Operations Research, 33, 910-927 (2006) · Zbl 1079.90097 |
| [14] | Berger, D.; Gendron, B.; Potvin, J.-Y.; Raghavan, S.; Soriano, P., Tabu search for a network loading problem with multiple facilities, Journal of Heuristics, 6, 253-267 (2000) · Zbl 0969.68642 |
| [15] | Bienstock, D.; Chopra, S.; Günlük, O.; Tsai, C., Minimum cost capacity installation for multicommodity network flows, Mathematical Programming, 81, 177-199 (1998) · Zbl 0922.90064 |
| [16] | Bienstock, D.; Günlük, O., Computational experience with a difficult mixed-integer multicommodity flow problem, Mathematical Programming, 68, 213-237 (1995) · Zbl 0834.90054 |
| [17] | Bienstock, D.; Günlük, O., Capacitated network design-polyhedral structure and computation, INFORMS Journal of Computing, 8, 243-259 (1996) · Zbl 0871.90031 |
| [18] | Chabrier, A.; Danna, E.; Le Pape, C.; Perron, L., Solving a network design problem, Annals of Operations Research, 130, 217-239 (2004) · Zbl 1156.90472 |
| [19] | Chopra, S.; Gilboa, I.; Sastry, S. T., Source sink flows with capacity installation in batches, Discrete Applied Mathematics, 85, 165-192 (1998) · Zbl 0908.90117 |
| [20] | M. Chouman, T.G. Crainic, B. Gendron, A cutting-plane algorithm based on cutset inequalities for multicommodity capacitated fixed charge network design, Publication crt-316, Centre de recherche sur les transports, Université de Montréal, 2003; M. Chouman, T.G. Crainic, B. Gendron, A cutting-plane algorithm based on cutset inequalities for multicommodity capacitated fixed charge network design, Publication crt-316, Centre de recherche sur les transports, Université de Montréal, 2003 |
| [21] | A.M. Costa, J.-F. Cordeau, B. Gendron, Benders, metric and cutset inequalities for multicommodity capacitated network design, Computational Optimization and Applications, forthcoming, 2007; A.M. Costa, J.-F. Cordeau, B. Gendron, Benders, metric and cutset inequalities for multicommodity capacitated network design, Computational Optimization and Applications, forthcoming, 2007 · Zbl 1208.90026 |
| [22] | Crainic, T. G., Service network design in freight transportation, European Journal of Operational Research, 122, 272-288 (2000) · Zbl 0961.90010 |
| [23] | Crainic, T. G.; Frangioni, A.; Gendron, B., Bundle-based relaxation methods for multicommodity capacitated fixed charge network design problems, Discrete Applied Mathematics, 112, 73-99 (2001) · Zbl 1026.90010 |
| [24] | Crainic, T. G.; Gendreau, M.; Farvolden, J., Simplex-based tabu search for the multicommodity capacitated fixed charge network design problem, INFORMS Journal on Computing, 12, 223-236 (2000) · Zbl 1040.90506 |
| [25] | Crainic, T. G.; Gendron, B.; Hernu, G., A slope scaling/lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design, Journal of Heuristics, 10, 525-545 (2004) · Zbl 1062.90009 |
| [26] | Croxton, K. L.; Gendron, B.; Magnanti, T. L., A comparison of mixed-integer programming models for non-convex piecewise linear cost minimization problems, Management Science, 49, 1268-1273 (2003) · Zbl 1232.90311 |
| [27] | Croxton, K. L.; Gendron, B.; Magnanti, T. L., Models and methods for merge-in-transit operations, Transportation Science, 37, 1-22 (2003) |
| [28] | Croxton, K. L.; Gendron, B.; Magnanti, T. L., Variable disaggregation in network flow problems with piecewise linear costs, Operations Research, 55, 146-157 (2007) · Zbl 1167.90602 |
| [29] | Farwolden, J. M.; Powell, W. B., Subgradient methods for the service network design problem, Transportation Science, 28, 256-272 (1994) · Zbl 0814.90023 |
| [30] | Frangioni, A., Generalized bundle methods, SIAM Journal on Optimization, 13, 117-156 (2002) · Zbl 1041.90037 |
| [31] | Frangioni, A., About Lagrangian methods in integer optimization, Annals of Operations Research, 139, 163-193 (2005) · Zbl 1091.90048 |
| [32] | Gabrel, V.; Knippel, K.; Minoux, M., Exact solution of multicommodity network optimization problems with general step cost functions, Operations Research Letters, 25, 15-23 (1999) · Zbl 0967.90012 |
| [33] | Gabrel, V.; Knippel, K.; Minoux, M., A comparison of heuristics for the discrete cost multicommodity network optimization problem, Journal of Heuristics, 9, 429-445 (2003) |
| [34] | Gendron, B.; Crainic, T. G.; Frangioni, A., Multicommodity capacitated network design, (Soriano, P.; Sansò, B., Telecommunications Network Planning (1999), Kluwer Academics Publisher), 1-19 |
| [35] | Gendron, B.; Potvin, J.-Y.; Soriano, P., Diversification strategies in local search for a nonbifurcated network loading problem, European Journal of Operational Research, 142, 231-241 (2002) · Zbl 1082.90506 |
| [36] | Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design, Operations Research, 51, 655-667 (2003) · Zbl 1165.90360 |
| [37] | Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design, Annals of Operations Research, 131, 109-133 (2004) · Zbl 1067.90014 |
| [38] | Grünert, T.; Sebastian, H.-J., Planning models for long-haul operations of postal and express shipment companies, European Journal of Operational Research, 122, 289-309 (2000) · Zbl 0961.90007 |
| [39] | Günlük, O., A branch-and-cut algorithm for capacitated network design problems, Mathematical Programming, 86, 17-39 (1999) · Zbl 1015.90090 |
| [40] | Holmberg, K.; Yuan, D., A lagrangean heuristic based branch-and-bound approach for the capacitated network design problem, Operations Research, 48, 461-481 (2000) · Zbl 1106.90381 |
| [41] | Keha, A. B.; de Farias, I. R.; Nemhauser, G. L., Models for representing piecewise linear cost functions, Operations Research Letters, 32, 44-48 (2004) · Zbl 1056.90107 |
| [42] | Kliewer, G.; Timajev, L., Relax-and-cut for capacitated network design, (Proceedings of Algorithms-ESA 2005: 13th Annual European Symposium on Algorithms. Proceedings of Algorithms-ESA 2005: 13th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 3369 (2005)), 47-58 · Zbl 1162.90576 |
| [43] | Leung, J. M.; Magnanti, T. L.; Singal, V., Routing in point-to-point delivery systems: Formulations and solution heuristics, Transportation Science, 24, 245-260 (1990) · Zbl 0723.90019 |
| [44] | Magnanti, T. L.; Mirchandani, P., Shortest paths, single origin-destination network design, and associated polyhedra, Networks, 23, 103-121 (1993) · Zbl 0791.90064 |
| [45] | Magnanti, T. L.; Mirchandani, P.; Vachani, R., The convex hull of two core capacitated network design problems, Mathematical Programming, 60, 233-250 (1993) · Zbl 0788.90071 |
| [46] | Magnanti, T. L.; Mirchandani, P.; Vachani, R., Modeling and solving the two-facility capacitated network loading problem, Operations Research, 43, 142-157 (1995) · Zbl 0830.90051 |
| [47] | Magnanti, T. L.; Wong, R. T., Network design and transportation planning: Models and algorithms, Transportation Science, 18, 1-55 (1984) |
| [48] | Minoux, M., Network synthesis and optimum network design problems: Models, solution methods and applications, Networks, 19, 313-360 (1989) · Zbl 0666.90032 |
| [49] | Mirchandani, P., Projections of the capacitated network loading problem, European Journal of Operational Research, 122, 534-560 (2000) · Zbl 0961.90013 |
| [50] | Padberg, M. W.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric travelling salesman problems, SIAM Review, 33, 60-100 (1991) · Zbl 0734.90060 |
| [51] | Raghavan, S.; Stanojević, S., A note on search by objective relaxation, (Raghavan, S.; Anandalingam, G., Telecommunications Planning: Innovations in Pricing, Network Design and Management (2006), Springer), 181-201, (Chapter 10) |
| [52] | F.S. Salman, R. Ravi, J. Hooker, Solving the capacitated local access network design problem, Working Paper, Purdue University, 2004; F.S. Salman, R. Ravi, J. Hooker, Solving the capacitated local access network design problem, Working Paper, Purdue University, 2004 · Zbl 1243.90034 |
| [53] | Sellmann, M.; Kliewer, G.; Koberstein, A., Lagrangian cardinality cuts and variable fixing for capacitated network design, (Proceedings of Algorithms-ESA 2002: 10th Annual European Symposium on Algorithms. Proceedings of Algorithms-ESA 2002: 10th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2461 (2002)), 845-858 · Zbl 1040.90004 |
| [54] | Valério de Carvalho, J. M., Exact solution of bin-packing problems using column generation and branch-and-bound, Annals of Operations Research, 86, 629-659 (1999) · Zbl 0922.90113 |
| [55] | Valério de Carvalho, J. M., LP models for bin packing and cutting stock problems, European Journal of Operational Research, 141, 253-273 (2002) · Zbl 1059.90095 |
| [56] | Zak, E. J., Row and column generation technique for a multistage cutting stock problem, Computers & Operations Research, 29, 1143-1156 (2002) · Zbl 0994.90111 |
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.
