IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v50y2002i4p656-669.html
   My bibliography  Save this article

On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems

Author

Listed:
  • Hanif D. Sherali

    (Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia 24061)

  • Patrick J. Driscoll

    (Department of Systems Engineering, U.S. Military Academy, West Point, New York 10996)

Abstract

This paper is concerned with applying the Reformulation-Linearization Technique (RLT) to derive tighter relaxations for the Asymmetric Traveling Salesman Problem (ATSP) formulation that is based on the Miller-Tucker-Zemlin (MTZ) subtour elimination constraints. The MTZ constraints yield a compact representation for the Traveling Salesman Problem (TSP), and their use is particularly attractive in various routing and scheduling contexts that have an embedded ATSP structure. However, it is well recognized that these constraints yield weak relaxations, and with this motivation, Desrochers and Laporte (1991) have lifted the MTZ constraints into facets of the underlying ATSP polytope. We show that a novel application of the RLT process from a nonstandard MTZ representation of the ATSP reveals a new formulation of this problem that is compact, and yet theoretically as well as computationally dominates the lifted-MTZ formulation of Desrochers and Laporte. This approach is also extended to derive tight formulations for the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), based on the MTZ subtour elimination constraints. Additional classes of valid inequalities are also developed for both these versions of the ATSP, and further ideas for developing tighter representations are suggested for future investigations.

Suggested Citation

  • Hanif D. Sherali & Patrick J. Driscoll, 2002. "On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems," Operations Research, INFORMS, vol. 50(4), pages 656-669, August.
    • Handle: RePEc:inm:oropre:v:50:y:2002:i:4:p:656-669
    DOI: 10.1287/opre.50.4.656.2865
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.50.4.656.2865
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.50.4.656.2865?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    2. Harlan Crowder & Manfred W. Padberg, 1980. "Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality," Management Science, INFORMS, vol. 26(5), pages 495-509, May.
    3. Hanif D. Sherali & Warren P. Adams & Patrick J. Driscoll, 1998. "Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems," Operations Research, INFORMS, vol. 46(3), pages 396-405, June.
    4. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Moeini, Asghar., 2017. "Identification of unidentified equality constraints for integer programming problems," European Journal of Operational Research, Elsevier, vol. 260(2), pages 460-467.
    2. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    3. R. Lougee-Heimer & W. Adams, 2005. "A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs," Annals of Operations Research, Springer, vol. 139(1), pages 289-320, October.
    4. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    5. Thomas Kirschstein & Christian Bierwirth, 2018. "The selective Traveling Salesman Problem with emission allocation rules," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 97-124, January.
    6. Albareda-Sambola, Maria & Fernández, Elena & Nickel, Stefan, 2012. "Multiperiod Location-Routing with Decoupled Time Scales," European Journal of Operational Research, Elsevier, vol. 217(2), pages 248-258.
    7. Teles, João P. & Castro, Pedro M. & Matos, Henrique A., 2013. "Univariate parameterization for global optimization of mixed-integer polynomial problems," European Journal of Operational Research, Elsevier, vol. 229(3), pages 613-625.
    8. Kirschstein, Thomas & Meisel, Frank, 2015. "GHG-emission models for assessing the eco-friendliness of road and rail freight transports," Transportation Research Part B: Methodological, Elsevier, vol. 73(C), pages 13-33.
    9. Borgonovo, E., 2010. "The reliability importance of components and prime implicants in coherent and non-coherent systems including total-order interactions," European Journal of Operational Research, Elsevier, vol. 204(3), pages 485-495, August.
    10. Khachai, Daniil & Sadykov, Ruslan & Battaia, Olga & Khachay, Michael, 2023. "Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm," European Journal of Operational Research, Elsevier, vol. 309(2), pages 488-505.
    11. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    12. Brian Lunday & Hanif Sherali & Kevin Lunday, 2012. "The coastal seaspace patrol sector design and allocation problem," Computational Management Science, Springer, vol. 9(4), pages 483-514, November.
    13. Rasmussen, Rasmus, 2011. "TSP in spreadsheets--A fast and flexible tool," Omega, Elsevier, vol. 39(1), pages 51-63, January.
    14. Schemeleva, Kseniya & Delorme, Xavier & Dolgui, Alexandre, 2018. "Evaluation of solution approaches for a stochastic lot-sizing and sequencing problem," International Journal of Production Economics, Elsevier, vol. 199(C), pages 179-192.
    15. Yuan Sun & Andreas Ernst & Xiaodong Li & Jake Weiner, 2021. "Generalization of machine learning for problem reduction: a case study on travelling salesman problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 607-633, September.
    16. Ferreira, Deisemara & Clark, Alistair R. & Almada-Lobo, Bernardo & Morabito, Reinaldo, 2012. "Single-stage formulations for synchronised two-stage lot sizing and scheduling in soft drink production," International Journal of Production Economics, Elsevier, vol. 136(2), pages 255-265.
    17. Duygu Pamukcu & Burcu Balcik, 2020. "A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 1-42, March.
    18. Paola Cappanera & Maria Grazia Scutellà, 2011. "Color-Coding Algorithms to the Balanced Path Problem: Computational Issues," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 446-459, August.
    19. Akgün, Ibrahim & Tansel, Barbaros Ç., 2011. "New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints," European Journal of Operational Research, Elsevier, vol. 212(2), pages 263-276, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ghosh, Diptesh & Sumanta Basu, 2011. "Diversified Local Search for the Traveling Salesman Problem," IIMA Working Papers WP2011-01-03, Indian Institute of Management Ahmedabad, Research and Publication Department.
    2. Muren, & Wu, Jianjun & Zhou, Li & Du, Zhiping & Lv, Ying, 2019. "Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 87-102.
    3. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    4. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    5. George Nemhauser, 2007. "Hooked on IP," Annals of Operations Research, Springer, vol. 149(1), pages 157-161, February.
    6. G Laporte, 2010. "A concise guide to the Traveling Salesman Problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 35-40, January.
    7. Jamal Ouenniche & Prasanna K. Ramaswamy & Michel Gendreau, 2017. "A dual local search framework for combinatorial optimization problems with TSP application," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1377-1398, November.
    8. Rafael Martinelli & Claudio Contardo, 2015. "Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 658-676, November.
    9. Ulrich Pferschy & Rostislav Staněk, 2017. "Generating subtour elimination constraints for the TSP from pure integer solutions," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(1), pages 231-260, March.
    10. Gong, Manlin & Hu, Yucong & Chen, Zhiwei & Li, Xiaopeng, 2021. "Transfer-based customized modular bus system design with passenger-route assignment optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 153(C).
    11. Ahmed Ghoniem & Hanif D. Sherali & Hojong Baik, 2014. "Enhanced Models for a Mixed Arrival-Departure Aircraft Sequencing Problem," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 514-530, August.
    12. Lisa K. Fleischer & Adam N. Letchford & Andrea Lodi, 2006. "Polynomial-Time Separation of a Superclass of Simple Comb Inequalities," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 696-713, November.
    13. Hanif D. Sherali & J. Cole Smith & Antonio A. Trani, 2002. "An Airspace Planning Model for Selecting Flight-plans Under Workload, Safety, and Equity Considerations," Transportation Science, INFORMS, vol. 36(4), pages 378-397, November.
    14. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    15. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    16. Olcay Polat & Duygu Topaloğlu, 2022. "Collection of different types of milk with multi-tank tankers under uncertainty: a real case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 1-33, April.
    17. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    18. Brian Lunday & Hanif Sherali & Kevin Lunday, 2012. "The coastal seaspace patrol sector design and allocation problem," Computational Management Science, Springer, vol. 9(4), pages 483-514, November.
    19. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    20. Stock-Williams, Clym & Swamy, Siddharth Krishna, 2019. "Automated daily maintenance planning for offshore wind farms," Renewable Energy, Elsevier, vol. 133(C), pages 1393-1403.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:50:y:2002:i:4:p:656-669. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.