Mixed integer programming formulations for the balanced traveling salesman problem with a lexicographic objective. (English) Zbl 1476.90287

Greco, Salvatore (ed.) et al., Metaheuristics for combinatorial optimization. Selected papers based on the presentations at the first international metaheuristics summer school, MESS 2018, Acireale-Sicily, Italy, July 21–25, 2018. Cham: Springer. Adv. Intell. Syst. Comput. 1332, 1-15 (2021).
Summary: This paper presents a Mixed Integer Program to solve the Balanced TSP. It exploits the underlying structure of the instances and is able to find optimal solutions for all the instances provided in the Metaheuristics Summer School competition. We study the efficiency of this new model on several variants of the Balanced TSP. The proposed method was ranked first in the MESS18 Metaheuristic competition among 9 submissions.
Instances and ranking:
Source code: https://gitlab.com/librallu/balancedtspcode.
For the entire collection see [Zbl 1464.90002].


90C27 Combinatorial optimization
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming


Full Text: DOI


[1] Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1-3), 23-47 (2003) · Zbl 1060.90056
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.