A fix-and-optimize matheuristic for university timetabling

University course timetabling covers the task of assigning rooms and time periods to courses while ensuring a minimum violation of soft constraints that define the quality of the timetable. These soft constraints can have attributes that make it difficult for mixed-integer programming solvers to find good solutions fast enough to be used in a practical setting. Therefore, metaheuristics have dominated this area despite the fact that mixed-integer programming solvers have improved tremendously over the last decade. This paper presents a matheuristic where the MIP-solver is guided to find good feasible solutions faster. This makes the matheuristic applicable in practical settings, where mixed-integer programming solvers do not perform well. To the best of our knowledge this is the first matheuristic presented for the University Course Timetabling problem. The matheuristic works as a large neighborhood search where the MIP solver is used to explore a part of the solution space in each iteration. The matheuristic uses problem specific knowledge to fix a number of variables and create smaller problems for the solver to work on, and thereby iteratively improves the solution. Thus we are able to solve very large instances and retrieve good solutions within reasonable time limits. The presented framework is easily extendable due to the flexibility of modeling with MIPs; new constraints and objectives can be added without the need to alter the algorithm itself. At the same time, the matheuristic will benefit from future improvements of MIP solvers. The matheuristic is benchmarked on instances from the literature and the 2nd International Timetabling Competition (ITC2007). Our algorithm gives better solutions than running a state-of-the-art MIP solver directly on the model, especially on larger and more constrained instances. Compared to the winner of ITC2007, the matheuristic performs better. However, the most recent state-of-the-art metaheuristics outperform the matheuristic.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem

The travelling salesman problem (TSP)   is one of the most prominent NP-hard combinatorial optimisation problems. After over fifty years of intense study, the TSP continues to be of broad theoretical and practical interest. Using a novel approach to empirical scaling analysis, which in principle is applicable to solvers for many other problems, we demonstrate that some of the most widely studied types of TSP instances tend to be much easier than expected from previous theoretical and empirical results. In particular, we show that the empirical median run-time required for finding optimal solutions to so-called random uniform Euclidean (RUE) instances – one of the most widely studied classes of TSP instances – scales substantially better than Θ(2ⁿ)$\Theta (2^n)$ with the number n of cities to be visited. The Concorde solver, for which we achieved this result, is the best-performing exact TSP solver we are aware of, and has been applied to a broad range of real-world problems. Furthermore, we show that even when applied to a broad range of instances from the prominent TSPLIB benchmark collection for the TSP, Concorde exhibits run-times that are surprisingly consistent with our empirical model of Concorde’s scaling behaviour on RUE instances. This result suggests that the behaviour observed for the simple random structure underlying RUE is very similar to that obtained on the structured instances arising in various applications.     

A polynomial-time solution to Papadimitriou and Steiglitz's ‘traps’

Papadimitriou and Steiglitz constructed ‘traps’ for the symmetric travelling salesman problem (TSP) with n = 8k cities. The constructed problem instances have exponentially many suboptimal solutions with arbitrarily large weight, which differ from the unique optimal solution in exactly 3k edges, and hence local search algorithms are ineffective to solve this problem. However, we show that this class of ‘catastrophic’ examples can be solved by linear programming relaxation appended with k subtour elimination constraints. It follows that this class of problem instances of TSP can be optimized in polynomial time.     

An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP.     

A matheuristic based on Lagrangian relaxation for the multi-activity shift scheduling problem

The multi-activity shift scheduling problem involves assigning a sequence of activities to a set of employees. In this paper, we consider the variant where the employees have different qualifications and each activity must be performed in a specified time window; i.e., we specify the earliest start period and the latest finish period. We propose a matheuristic in which Lagrangian relaxation is used to identify a subset of promising shifts, and a restricted set covering problem is solved to find a feasible solution. Each shift is represented by a context-free grammar. Computational tests are carried out on two sets of instances from the literature. For the first set, the matheuristic finds a solution with an optimality gap less than 0.01% for 70% of the instances and improves the best-known solution for 16% of them; for the second set, the matheuristic reaches the best-known solutions for 55% of the instances and finds better solutions for 37.5% of them.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

On the empirical scaling of running time for finding optimal solutions to the TSP

We study the empirical scaling of the running time required by state-of-the-art exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, we use a recently introduced statistical approach to obtain scaling models from observed performance data and to assess the accuracy of these models. For Concorde, the long-standing state-of-the-art exact TSP solver, we compare the scaling of the running time until an optimal solution is first encountered (the finding time) and that of the overall running time, which adds to the finding time the additional time needed to complete the proof of optimality. For two state-of-the-art inexact TSP solvers, LKH and EAX, we compare the scaling of their running time for finding an optimal solution to a given instance; we also compare the resulting models to that for the scaling of Concorde’s finding time, presenting evidence that both inexact TSP solvers show significantly better scaling behaviour than Concorde.     

Integer programming models and linearizations for the traveling car renter problem

The traveling car renter problem (CaRS) is an extension of the classical traveling salesman problem (TSP) where different cars are available for use during the salesman’s tour. In this study we present three integer programming formulations for CaRS, of which two have quadratic objective functions and the other has quadratic constraints. The first model with a quadratic objective function is grounded on the TSP interpreted as a special case of the quadratic assignment problem in which the assignment variables refer to visitation orders. The second model with a quadratic objective function is based on the Gavish and Grave’s formulation for the TSP. The model with quadratic constraints is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP. The formulations are linearized and implemented in two solvers. An experiment with 50 instances is reported.     

General k-opt submoves for the Lin–Kernighan TSP heuristic

Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin–Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code.     

Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization

The precedence constrained traveling salesman problem (TSP-PC), or the sequential ordering problem (SOP), consists of finding an optimal TSP tour that will also satisfy the namesake precedence constraints, typically specified as a partial order or a directed acyclic graph. Its dynamic programming (DP) solution was proposed as early as 1979, however, by late 1990s, it mostly fell out of use in plain TSP-PC. Revisiting this method, we are able to close one of the long-standing TSPLIB SOP problem instances, ry48p.3.sop, and provide improved bounds on its time complexity. Harnessing the “omnivorous” nature of DP, we prove the validity of DP optimality principle for TSP-PC with both (i) abstract cost aggregation function, which may be the arithmetic + operation as in “ordinary” TSP or $\max$ as in Bottleneck TSP, or any other left-associative nondecreasing in the first argument operation and (ii) travel cost functions depending on the set of pending tasks (“sequence dependence”). Using the latter generalization, we close several TD-SOP (time-dependent TSP-PC) instances based on TSPLIB SOP as proposed by Kinable et al., including rbg253a.sop. Through the restricted DP heuristic, which was originally formulated for time-dependent TSP by Malandraki and Dial, we improve the state-of-the-art upper bounds for all yet unsolved TSPLIB-based TD-SOP instances, including those with more than 100 cities. We also improve worst-case complexity estimates for DP in TSP-PC.     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.     

The multi-commodity one-to-one pickup-and-delivery traveling salesman problem

This paper concerns a generalization of the traveling salesman problem (TSP) called multi-commodity one-to-one pickup-and-delivery traveling salesman problem (m-PDTSP) in which cities correspond to customers providing or requiring known amounts of m different commodities, and the vehicle has a given upper-limit capacity. Each commodity has exactly one origin and one destination, and the vehicle must visit each customer exactly once. The problem can also be defined as the capacitated version of the classical TSP with precedence constraints. This paper presents two mixed integer linear programming models, and describes a decomposition technique for each model to find the optimal solution. Computational experiments on instances from the literature and randomly generated compare the techniques and show the effectiveness of our implementation.     

On relaxations of the max k-cut problem formulations

A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.     

Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems

 Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming. In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000 or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the general cutting-plane method in large-scale applications. Received: December 6, 2002 / Accepted: April 24, 2003 Published online: May 28, 2003 RID="*" ID="*" Supported by ONR Grant N00014-03-1-0040     

The x-and-y-axes travelling salesman problem

The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomial time. The running time of the resulting algorithm is quadratic in the number of cities.     

A parallel matheuristic for the technician routing and scheduling problem

The Technician Routing and Scheduling Problem (TRSP) consists in routing staff to serve requests for service, taking into account time windows, skills, tools, and spare parts. Typical applications include maintenance operations and staff routing in telecoms, public utilities, and in the health care industry. In this paper, we present a formal definition of the TRSP, discuss its relation with the Vehicle Routing Problem with Time Windows (VRPTW), and review related research. From a methodological perspective, we describe a matheuristic composed of a constructive heuristic, a parallel Adaptive Large Neighborhood Search, and a mathematical programming based post-optimization procedure that successfully tackles the TRSP. We validate the matheuristic on the Solomon VRPTW instances, where we achieve an average gap of $0.23\,\%$ , and matched 44 out of 55 optimal solutions. Finally, we illustrate how the matheuristic successfully solves a set of TRSP instances extended from the Solomon benchmark.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

A matheuristic for the truck and trailer routing problem

In the truck and trailer routing problems (TTRPs) a fleet of trucks and trailers serves a set of customers. Some customers with accessibility constraints must be served just by truck, while others can be served either by truck or by a complete vehicle (a truck pulling a trailer). We propose a simple, yet effective, two-phase matheuristic that uses the routes of the local optima of a hybrid GRASP × ILS as columns in a set-partitioning formulation of the TTRP. Using this matheuristic we solved both the classical TTRP with fixed fleet and the new variant with unlimited fleet. This matheuristic outperforms state-of-the-art methods both in terms of solution quality and computing time. While the best variant of the matheuristic found new best-known solutions for several test instances from the literature, the fastest variant of the matheuristic achieved results of comparable quality to those of all previous method from the literature with an average speed-up of at least 2.5.