The Chvátal–Gomory procedure for integer SDPs with applications in combinatorial optimization

In this paper we study the well-known Chvátal–Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the...

The first AI4TSP competition: Learning to solve stochastic routing problems

This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the...

Bi-sided facility location problems: an efficient algorithm for k-centre, k-median, and travelling salesman problems

This study introduces a general framework, called Bi-sided facility location, for a wide range of problems in the area of combined facility location and routing problems such as locating test centres and designing the network of supermarkets. It is based on a multi-objective optimisation model to enhance the service quality which the clients...

Learning to Solve Multiple-TSP With Time Window and Rejections via Deep Reinforcement Learning

We propose a manager-worker framework (the implementation of our model is publically available at: https://github.com/zcaicaros/manager-worker-mtsptwr) based on deep reinforcement learning to tackle a hard yet nontrivial variant of Travelling Salesman Problem (TSP), i.e. multiple-vehicle TSP with time window and rejections (mTSPTWR), where...

Models and heuristics for hard routing and knapsack problems

One of the world’s biggest challenges is that living beings have to share a limited amount of resources. As people of science, we strive to find innovative ways to better use these resources, to reach and positively affect more and more people. In the field of optimization, we aim at finding an optimal allocation of limited sets of resources to...

Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem

Metaheuristics have been widely used to solve NP-hard problems, with excellent results. Among all NP-hard problems, the Travelling Salesman Problem (TSP) is potentially the most studied one. In this work, a variation of the TSP is considered; the main differences being, edges may have positive or negative costs and the objective is to return...

A priori TSP in the scenario model

In this paper, we consider the a priori traveling salesman problem in the scenario model. In this problem, we are given a list of subsets of the vertices, called scenarios, along with a probability for each scenario. Given a tour on all vertices, the resulting tour for a given scenario is obtained by restricting the solution to the vertices...

Maintenance optimization for railway infrastructure networks

Maintenance is crucial for the proper functioning and lifetime extension of a railway infrastructure network, which is composed of various infrastructures with different functions. In this thesis we develop robust and tractable model-based approaches for maintenance optimization of railway infrastructure networks. In addition, we develop a...