Eleonora Vercesi The most successful approaches for the TSP use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder: What is the … Read more
In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (DCUT) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the DCUT formulation on metric instances. A key contribution of our … Read more
In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for small-sized instances. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ( \(P_{ASEP}^n\) ) and its vertices. The polytope’s symmetries … Read more
This paper introduces a computational method for generating metric Travelling Salesperson Problem (TSP) instances having a large integrality gap. The method is based on the solution of an NP-hard problem, called IH-OPT, that takes in input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and compute a TSP instance having … Read more