Single-commodity flow-based formulations and accelerated benders algorithms for the high-multiplicity asymmetric traveling salesman problem and its extensionsFootnote

Please note this paper has been re-typeset by Taylor & Francis from the manuscript originally provided to the previous publisher.

References

• Aguayo, M. M. (2016). Modeling, analysis, and exact algorithms for some biomass logistics supply chain design and routing problems (PhD thesis). Virginia Polytechnic Institute and State University.
   Google Scholar
• Baker, T., & Muckstadt, J. (1989). The CHES problems. Technical Paper. Providence: Chesapeake Decision Sciences, Inc.
   Google Scholar
• Balas, E., Ceria, S., & Cornujols, G. (1993). A lift-and-project cutting plane algorithm for mixed 01 programs. Mathematical Programming, 58(1–3), 295–324.
   Web of Science ®Google Scholar
• Bertsimas, D., Gamarnik, D., & Sethuraman, J. (2003). From fluid relaxations to practical algorithms for high-multiplicity job-shop scheduling: The holding cost objective. Operations Research, 51(5), 798–813.
   Web of Science ®Google Scholar
• Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2005). A framework for the complexity of high-multiplicity scheduling problems. Journal of Combinatorial Optimization, 9(3), 313–323.
   Web of Science ®Google Scholar
• Brauner, N., Crama, Y., Grigoriev, A., & Van De Klundert, J. (2007). Multiplicity and complexity issues in contemporary production scheduling. Statistica Neerlandica, 61(1), 75–91.
   Web of Science ®Google Scholar
• Cheng, T., Shafransky, Y., & Ng, C. (2016). An alternative approach for proving the np-hardness of optimization problems. European Journal of Operational Research, 248(1), 52–58.
   Web of Science ®Google Scholar
• Cirasella, J, Johnson, D. S., McGeoch, L. A., & Zhang W. (2001). The asymmetric traveling salesman problem: Algorithms, instance generators, and tests. In A. L. Buchsbaum & J. Snoeyink (Eds.), Proceedings of ALENEX’01. Lecture Notes in Computer Science (Vol. 2153, pp. 32–59). Berlin: Springer.
   Google Scholar
• Clifford, J. J., & Posner, M. E. (2001). Parallel machine scheduling with high multiplicity. Mathematical Programming, 89(3), 359–383.
   Web of Science ®Google Scholar
• Cosmadakis, S. S., & Papadimitriou, C. H. (1984). The traveling salesman problem with many visits to few cities. SIAM Journal on Computing, 13(1), 99–108.
   Web of Science ®Google Scholar
• Crama, Y., & Gultekin, H. (2010). Throughput optimization in two-machine flowshops with flexible operations. Journal of Scheduling, 13(3), 227–243.
   Web of Science ®Google Scholar
• Desrochers, M., & Laporte, G. (1991). Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1), 27–36.
   Web of Science ®Google Scholar
• Filippi, C. (2010). An approximate algorithm for a high-multiplicity parallel machine scheduling problem. Operations Research Letters, 38(4), 312–317.
   Web of Science ®Google Scholar
• Filippi, C., & Romanin-Jacur, G. (2009). Exact and approximate algorithms for high-multiplicity parallel machine scheduling. Journal of Scheduling, 12(5), 529–541.
   Web of Science ®Google Scholar
• Fischetti, M., Salvagnin, D., & Zanette, A. (2010). A note on the selection of Benders’ cuts. Mathematical Programming, 124(1), 175–182.
   Web of Science ®Google Scholar
• Gabay, M., Rapine, C., & Brauner, N. (2016). High-multiplicity scheduling on one machine with forbidden start and completion times. Journal of Scheduling, 19(5), 609–616.
   Web of Science ®Google Scholar
• Gavish B, & Graves S. C. (1978). The travelling salesman problem and related problems. Working paper GR-078-78. Cambridge, MA: Operation Research Center, Massachusetts Institute of Technology.
   Google Scholar
• Grigoriev, A., & van de Klundert, J. (2006). On the high multiplicity traveling salesman problem. Discrete Optimization, 3(1), 50–62.
   Web of Science ®Google Scholar
• Hochbaum, D. S., & Shamir, R. (1991). Strongly polynomial algorithms for the high multiplicity scheduling problem. Operations Research, 39(4), 648–653.
   Web of Science ®Google Scholar
• IBM. (2017). Benders decomposition. Retrieved August 12, 2016, from https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/benders/defaultDecomp.html
   Google Scholar
• Kimbrel, T., & Sviridenko, M. (2008). High-multiplicity cyclic job shop scheduling. Operations Research Letters, 36(5), 574–578.
   Web of Science ®Google Scholar
• Lehoux-Lebacque, V., Brauner, N., & Finke, G. (2015). Identical coupled task scheduling: Polynomial complexity of the cyclic case. Journal of Scheduling, 18(6), 631–644.
   Web of Science ®Google Scholar
• Leung, J. Y.-T. (1982). On scheduling independent tasks with restricted execution times. Operations Research, 30(1), 163–171.
   Web of Science ®Google Scholar
• Magnanti, T. L. & Wong, R. T. (1981). Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3), 464–484.
   Web of Science ®Google Scholar
• Masin, M., & Raviv, T. (2014). Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem. Journal of Scheduling, 17(4), 321–338.
   Web of Science ®Google Scholar
• Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of ACM, 7(4), 326–329.
   Web of Science ®Google Scholar
• Öncan, T., Altnel K. I., & Laporte G. (2009). A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(3), 637–654.
   Web of Science ®Google Scholar
• Papadakos, N. (2008). Practical enhancements to the Magnanti-Wong method. Operations Research Letters, 36(4), 444–449.
   Web of Science ®Google Scholar
• Psaraftis, H. N. (1980). A dynamic programming approach for sequencing groups of identical jobs. Operations Research, 28(6), 1347–1359.
   Web of Science ®Google Scholar
• Roberti, R., & Toth, P. (2012). Models and algorithms for the asymmetric traveling salesman problem: An experimental comparison. EURO Journal on Transportation and Logistics, 1(1–2), 113–133.
   Google Scholar
• Rothkopf, M. (1966). The traveling salesman problem: On the reduction of certain large problems to smaller ones. Operations Research, 14(3), 532–533.
   Web of Science ®Google Scholar
• Rudin P. (2016). OR in an OB World. Retrieved April 12, 2016, from http://orinanobworld.blogspot.com/2016/12/support-for-benders-decomposition-in.html
   Google Scholar
• Sarin, S. C., Sherali, H. D., & Liao, L. (2014). Primary pharmaceutical manufacturing scheduling problem. IIE Transactions, 46(12), 1298–1314.
   Web of Science ®Google Scholar
• Sarin, S. C., Sherali, H. D., & Yao, L. (2011). New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem. Optimization Letters, 5(2), 259–272.
   Web of Science ®Google Scholar
• TSPLIB. (1997). A library of traveling salesmen and related problem instances. Retrieved January 3, 2016, from http://elib.zib.de/pub/mp-testdata/tsp/tsplib/atsp/index.html
   Google Scholar
• Van der Veen, J. A., & Zhang, S. (1996). Low-complexity algorithms for sequencing jobs with a fixed number of job-classes. Computers & Operations Research, 23(11), 1059–1067.
   Web of Science ®Google Scholar