An extended formulation for the ring/ring problem
Abstract
This work introduces a branch-and-price approach for the design of a two-level network in which each level is a ring.
Keywords:
integer linear programming, branch-and-price, column generation
References
Baldacci, R., Mingozzi, A., and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations Research, 59(5):1269–1283.
Gamrath, G., Fischer, T., Gally, T., Gleixner, A. M., Hendel, G., Koch, T., Maher, S. J., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J. T., and Witzig, J. (2016). The SCIP Optimization Suite 3.2. Technical report, Optimization Online.
Irnich S., D. G. (2005). Column Generation, chapter Shortest Path Problems with Resource Constraints. Springer.
Miller, C., Tucker, A., and Zemlin, R. (1960). Integer programming formulations and traveling salesman problems. Journal of ACM, 7:326–329.
Poggi, M. and Uchoa, E. (2014). Chapter 3: New exact algorithms for the capacitated vehicle routing problem. In MOS-SIAM Series on Optimization, pages 59–86. Society for Industrial and Applied Mathematics.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016a). A branch-and-cut algorithm for two-level survivable network design problems. Computers & Operations Research, 67:102–112.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016b). The ring/κ-rings network design problem: Model and branch-and-cut algorithm. Networks, 68(2):130–140.
Thomadsen, T. and Stidsen, T. (2005). Hierarchical ring network design using branch-and-price. Telecommunication systems, 29(1):61–76.
Gamrath, G., Fischer, T., Gally, T., Gleixner, A. M., Hendel, G., Koch, T., Maher, S. J., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J. T., and Witzig, J. (2016). The SCIP Optimization Suite 3.2. Technical report, Optimization Online.
Irnich S., D. G. (2005). Column Generation, chapter Shortest Path Problems with Resource Constraints. Springer.
Miller, C., Tucker, A., and Zemlin, R. (1960). Integer programming formulations and traveling salesman problems. Journal of ACM, 7:326–329.
Poggi, M. and Uchoa, E. (2014). Chapter 3: New exact algorithms for the capacitated vehicle routing problem. In MOS-SIAM Series on Optimization, pages 59–86. Society for Industrial and Applied Mathematics.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016a). A branch-and-cut algorithm for two-level survivable network design problems. Computers & Operations Research, 67:102–112.
Rodrı́guez-Martı́n, I., Salazar-González, J.-J., and Yaman, H. (2016b). The ring/κ-rings network design problem: Model and branch-and-cut algorithm. Networks, 68(2):130–140.
Thomadsen, T. and Stidsen, T. (2005). Hierarchical ring network design using branch-and-price. Telecommunication systems, 29(1):61–76.
Published
2020-06-30
How to Cite
OSÓRIO, Cecília Lescano; HOSHINO, Edna Ayako.
An extended formulation for the ring/ring problem. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 89-92.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11097.
