Abstract
•Show that the strongest known compact formulations reduce to a more compact model.•Devise a new compact formulation by RLT outperforming the strongest existing models.•The projections of this model into the original space yields other tighter models.•The dominance relationships are stated between the new models and the existing ones.•The proposed models are compared experimentally with existing compact formulations.
We provide new compact formulations of polynomial size for the asymmetric traveling salesman problem obtained through the Reformulation-Linearization Technique. The first one is obtained directly by this latter approach while the two others are derived by performing projections of this formulation on the variables of the existing models. We show that the devised formulations are stronger than the state-of-the-art models. Computational experiments conducted on benchmark instances for the classical variant and with precedence constraints confirm the better quality of the relaxations provided by our proposed formulations.