Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Giuseppe Lancia has a total of 56 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Speeding Up Floyd–Warshall’s Algorithm to Compute All-Pairs Shortest Paths and the Transitive Closure of a Graph

    by Giuseppe Lancia, Marcello Dalpasso

    Floyd–Warshall’s algorithm is a widely-known procedure for computing all-pairs shortest paths in a graph of n vertices in Θ(n3) time complexity. A simplified version of the same algorithm computes the transitive closure of the graph with the same time complexity. The algorithm operates on an n×n matrix, performing n inspections and no more than n updates of each matrix cell, until the final matrix is computed. In this paper, we apply a technique called SmartForce, originally devised as a performance enhancement for solving the traveling salesman problem, to avoid the inspection and checking of cells that do not need to be updated, thus reducing the overall computation time when the number, u, of cell updates is substantially smaller than n3. When the ratio u/n3 is not small enough, the performance of the proposed procedure might be worse than that of the Floyd–Warshall algorithm. To speed up the algorithm independently of the input instance type, we introduce an effective hybrid approach. Finally, a similar procedure, which exploits suitable fast data structures, can be used to achieve a speedup over the Floyd–Warshall simplified algorithm that computes the transitive closure of a graph.


  • Code and Data Repository for Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood

    by Giuseppe Lancia, Paolo Vidoni

    The repository contains all files necessary to replicate computational experiments as those reported in the paper "Average case sub-quadratic exact and heuristic procedures for the traveling salesman 2-OPT neighborhood", by Giuseppe Lancia and Paolo Vidoni, INFORMS Journal on Computing, 2024.

  • Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood

    by Giuseppe Lancia, Paolo Vidoni

    We describe an exact algorithm for finding the best 2-OPT move that, experimentally, was observed to be much faster than the standard quadratic approach for a large part of a best-improvement local search convergence starting at a random tour. To analyze its average-case complexity, we introduce a family of heuristic procedures and discuss their complexity when applied to a random tour in graphs whose edge costs are either uniform random numbers in [0, 1] or Euclidean distances between random points in the plane. We prove that, for any probability p, there is a heuristic in the family that can find the best 2-OPT move with probability at least p in average-time [ ]) for uniform instances and [ ] for Euclidean instances. The exact algorithm is then proved to be even faster in the sense that in those instances in which a heuristic finds the best move, the exact algorithm finds it in a smaller time. We give empirical evidence that a slight variant of our algorithm finds the best move in [ ] time on both types of instances, achieving the best possible performance for this particular problem. Computational experiments are reported to show the effectiveness of our algorithms, both in best-improvement and in first-improvement 2-OPT local search. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms: Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0169 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0169 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .


  • Open Access

    Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time

    by Giuseppe Lancia, Paolo Vidoni

    We describe an exact algorithm for finding the best 2-OPT move which, experimentally, was observed to be much faster than the standard quadratic approach. To analyze its average-case complexity, we introduce a family of heuristic procedures and discuss their complexity when applied to a random tour in graphs whose edge costs are either uniform random numbers in [0, 1] or Euclidean distances between random points in the plane. We prove that, for any probability p: (i) there is a heuristic in the family which can find the best move with probability at least p in average-time O(n^3/2) for uniform instances and O(n) for Euclidean instances; (ii) the exact algorithm take lesser time then the above heuristic on all instances on which the heuristic finds the best move. During local search, while the tour becomes less and less random, the speed of our algorithm worsens until it becomes quadratic. We then discuss how to fine tune a successful hybrid approach, made of our algorithm in the beginning followed by the usual quadratic enumeration.

  • Open Access

    Algorithmic strategies for a fast exploration of the TSP $4$-OPT neighborhood

    by Giuseppe Lancia, Marcello Dalpasso

    We describe an effective algorithm for exploring the $$4$$ 4 -OPT neighborhood for the Traveling Salesman Problem. $$4$$ 4 -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ Θ ( n 4 ) algorithm by complete enumeration, but a $$\Theta (n^3)$$ Θ ( n 3 ) dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ Θ ( n 2 ) algorithm also exists for a particular subset of symmetric $$4$$ 4 -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ O ( n 2.5 ) ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ 4 -OPT move, and discuss the strength of the $$4$$ 4 -OPT neighborhood compared to 2- and $$3$$ 3 -OPT.


  • An ILP Approach to Determine Smallest 4-Regular Non-Hamiltonian, Nontraceable, and Nonhomogeneously Traceable Graphs

    by G. Lancia, E. Pippia, F. Rinaldi

    In this paper we study some open questions related to the smallest order \( f({\cal C},\lnot {\cal H}) \) of a \( 4 \)-regular graph which has a connectivity property \( {\cal C} \) but does not have a hamiltonian property \( \cal H \). In particular, \( \cal C \) is either connectivity, \( 2 \)-connectivity or \( 1 \)-toughness and \( \cal H \) is hamiltonicity, homogeneous traceability or traceability. A standard theoretical approach to these questions had already been used in the literature, but in many cases did not succeed in determining the exact value of \( f() \). Here we have chosen to use Integer Linear Programming and to encode the graphs that we are looking for as the binary solutions to a suitable set of linear inequalities. This way, there would exist a graph of order \( n \) with certain properties if and only if the corresponding ILP had a feasible solution, which we have determined through a branch-and-cut procedure. By using our approach, we have been able to compute \( f({\cal C},\lnot {\cal H}) \) for all the pairs of considered properties with the exception of \( {\cal C}= \)1-toughness, \( {{\cal H}}= \)traceability. Even in this last case, we have nonetheless significantly reduced the interval \( [LB, UB] \) in which \( f({\cal C},\lnot {\cal H}) \) was known to lie. Finally, we have shown that for each \( n \geq f({\cal C},\lnot {\cal H}) \) ( \( n \geq UB \) in the last case) there exists a \( 4 \)-regular graph on \( n \) vertices which has property \( \cal C \) but not property \( \cal H \).

  • Open Access

    Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data

    by Giuseppe Lancia, Paolo Serafini

    Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called patterns, which can be used to classify new samples as positive or negative. Since a data set can be explained in alternative ways, many computational problems arise related to the choice of a particular set of patterns. In this paper we study the computational complexity of several of these pattern problems (showing that they are, in general, computationally hard) and we propose some integer programming models that appear to be effective. We describe an ILP model for finding the minimum-size set of patterns explaining a given set of samples and another one for the problem of determining whether two sets of patterns are equivalent, i.e., they explain exactly the same samples. We base our first model on a polynomial procedure that computes all patterns compatible with a given set of samples. Computational experiments substantiate the effectiveness of our models on fairly large instances. Finally, we conjecture that the existence of an effective ILP model for finding a minimum-size set of patterns equivalent to a given set of patterns is unlikely, due to the problem being NP-hard and co-NP-hard at the same time.


  • Open Access

    Finding the Best 3-OPT Move in Subcubic Time

    by Giuseppe Lancia, Marcello Dalpasso

    Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the Θ(n3) enumeration of all triples is likely to exist for this problem, but algorithms with average case O(n3−ϵ) are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by O(n2.5)) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances.