Title: An iterated local search algorithm for the traveling purchaser problem

Authors: Tomás Kapancioglu (CEMAPRE) and Raquel Bernardino (CEMAPRE & ISEG, ULisboa)

Abstract: The Traveling Purchaser Problem (TPP) is a generalization of the Traveling Salesman Problem (TSP) in which a list of items must be acquired by visiting a subset of markets. The objective is to minimize the total cost sustained along the route, including purchasing and traveling costs. Due to the NP-hard nature of the problem, solving the TPP in an exact manner is computationally challenging, implying the need for heuristic approaches to obtain quality solutions efficiently. This study proposes an algorithm based on the metaheuristic Iterated Local Search (ILS), complemented by a route configuration procedure that adjusts the subset of markets in the solution. The ILS is tested in benchmark instances, providing a performance comparison with other methods. The computational experiment for the asymmetric instances reveals the effectiveness and efficiency of the ILS, outperforming previously published results with statistical significance. Additional experiments are presented for the symmetric instances, pointing to the competitiveness and versatility of the ILS in relation to other heuristic approaches used in the literature.

Title: Formulations and Branch-and-cut algorithms for the Period Travelling Salesman Problem

Authors:  Sofia Henriques and Ana Paias (CMAFcIO, ULisboa)

Abstract: The Period Travelling Salesman Problem (PTSP) generalizes the Travelling Salesman Problem (TSP). We consider a time horizon with different periods and a directed graph with a depot and n customers, in which each customer has a required number of periods to be visited in. The objective of the PTSP is to assign each client to as many periods as it is required while determining the set of routes, one for each period, with minimum cost. Each route starts and ends at the depot and visits the clients assigned to that specific period only once. The PTSP combines an assignment and a routing problem in a single problem, making it very difficult to solve to optimality, even for instances with few clients. We will present, both compact and non-compact, ILP formulations for the PTSP and new valid inequalities, generalizing the work available in the literature. The main conclusions from our theoretical study will be presented, as well as computational results on instances with up 70 nodes and 5 periods. Finally, we intend to motivate some interesting topics of future work for the PTSP.

Title: Branch-and-cut algorithms for colorful components problems

Authors:  Carmine Sorgente (University of Salerno), Martina Cerulli (University of Salerno), Claudia Archetti (University of Brescia)

Abstract: We tackle three optimization problems in which a colored graph, where each node is assigned a color, must be partitioned into colorful connected components. A component is defined as colorful if each color appears at most once. The problems differ in the objective function, which determines which partition is the best one. These problems have applications in community detection, cybersecurity, and bioinformatics. We present integer non-linear formulations, which are then linearized using standard techniques. To solve these formulations, we develop exact branch-and-cut algorithms, embedding various improving techniques, such as valid inequalities, bounds limiting the number of variables, and warm-start and preprocessing techniques. Extensive computational tests on benchmark instances demonstrate the effectiveness of the proposed procedures. The branch-and-cut algorithms can solve reasonably sized instances efficiently. To the best of our knowledge, we are the first to propose an exact algorithm for solving these problems.

Title: On extensions of Node-Depot Assignment Formulations for the Hamiltonian p-Median Problem

Authors:  Francisco Canas and Luís Gouveia (CMAFcIO, ULisboa)

Abstract: Given a weighted complete undirected graph with weights on the edges and a positive integer p, the symmetric Hamiltonian p-Median Problem (HpMP) is to find a minimum weight set of p elementary cycles partitioning the vertices of the graph. We focus on a variant of the HpMP (the HpMP>=) where solutions with strictly more than p cycles are also feasible. We present new extensions of known node-depot assignment (NDA) compact formulations. NDA models are characterized by the inclusion of NDA variables, which are 1 if and only if node d acts as the depot of the cycle node i is in (or alternatively, if node i is ``assigned" to node d), in addition to edge variables, which are 1 if and only if the corresponding edge is in some cycle. We extend these formulations with edge-depot assignment (EDA) variables, which are 1 if and only if node d acts as the depot of the cycle edge {i,j} is in. In this talk, we propose new formulations which use the EDA variables; relate these models with formulations including only the edge and NDA variables; present new inequalities in the space of the edge and NDA variables that are obtained from the new models using EDA variables; and present computational results obtained with the new models. Preliminary computational results show that the new models produce very strong LP relaxation bounds and, when used in combination with a modern ILP solver, allow for the resolution of instances with over one-hundred nodes.

Title: Synchronization in Vehicle Routing: Optimization-Simulation Approach

Authors:  Raquel Bernardino (CEMAPRE & ISEG, ULisboa), Daniel Santos (CEGIST & IST, ULisboa) & Filippo Visintin (Department of Industrial Engineering, Università degli Studi di Firenze)

Abstract: The Traveling Purchaser Problem (TPP) is a generalization of the Traveling Salesman Problem (TSP) in which a list of items must be acquired by visiting a subset of markets. The objective is to minimize the total cost sustained along the route, including purchasing and traveling costs. Due to the NP-hard nature of the problem, solving the TPP in an exact manner is computationally challenging, implying the need for heuristic approaches to obtain quality solutions efficiently. This study proposes an algorithm based on the metaheuristic Iterated Local Search (ILS), complemented by a route configuration procedure that adjusts the subset of markets in the solution. The ILS is tested in benchmark instances, providing a performance comparison with other methods. The computational experiment for the asymmetric instances reveals the effectiveness and efficiency of the ILS, outperforming previously published results with statistical significance. Additional experiments are presented for the symmetric instances, pointing to the competitiveness and versatility of the ILS in relation to other heuristic approaches used in the literature.

Title: Revisiting a Cornuéjols-Nemhauser-Wolsey formulation for the p-median problem

Authors:  Cristina Requejo (ISEG and CEMAPRE, University of Lisbon), Agostinho Agra (Department of Mathematics and CIDMA, University of Aveiro)

Abstract: A formulation for the simple facility location and p-median problems introduced by Cornuéjols, Nemhauser and Wolsey (1980) [2] is revisited. Despite being the smallest known formulation regarding the number of variables, this formulation is barely used in the literature. Recently, it has been employed as the result of Benders decomposition of other formulations for large scale p-median problems [3]. We reintroduce the formulation for the p-median problem as the intersection of a selection problem with an additional family of optimality constraints to define the costs correctly. We establish connections to the classical formulation and to the Radius formulation [1]. By exploring the optimality constraints, we discuss approaches to derive bounds for large-size instances. These approaches are based on relaxations obtained by eliminating optimality constraints and can be seen as simple matheuristic to solve large size instances. In particular, we characterize relaxations which provide the optimal solution, and therefore, can be seen as new formulations for the p-medium problem. Computational tests are reported [1] showing that the renewed formulation can be used efficiently to solve p-medium instances.