Improved bounds for the traveling umpire problem: A stronger formulation and a relax-and-fix heuristic

Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too often. We strengthen a known integer programming formulation for the TUP and use it to implement a relax-and-fix heuristic that improves the quality of 24 out of 25 best-known feasible solutions to instances in the TUP benchmark. We also improve all best-known lower bounds for those instances and, for the first time, provide lower bounds for instances with more than 16 teams.     

Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem

This paper presents several methodological and algorithmic improvements over a state-of-the-art dynamic programming algorithm for solving the bi-objective {0,1} knapsack problem. The variants proposed make use of new definitions of lower and upper bounds, which allow a large number of states to be discarded. The computation of these bounds are based on the application of dichotomic search, definition of new bound sets, and bi-objective simplex algorithms to solve the relaxed problem. Although these new techniques are not of a common application for dynamic programming, we show that the best variants tested in this work can lead to an average improvement of 10 to 30 % in CPU-time and significant less memory usage than the original approach in a wide benchmark set of instances, even for the most difficult ones in the literature.     

Lower bounds for the ITC-2007 curriculum-based course timetabling problem

This paper describes an approach for generating lower bounds for the curriculum-based course timetabling problem, which was presented at the International Timetabling Competition (ITC-2007, Track 3). So far, several methods based on integer linear programming have been proposed for computing lower bounds of this minimization problem. We present a new partition-based approach that is based on the “divide and conquer” principle. The proposed approach uses iterative tabu search to partition the initial problem into sub-problems which are solved with an ILP solver. Computational outcomes show that this approach is able to improve on the current best lower bounds for 12 out of the 21 benchmark instances, and to prove optimality for 6 of them. These new lower bounds are useful to estimate the quality of the upper bounds obtained with various heuristic approaches.     

Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem

We develop ideas to enhance the performance of the variable neighborhood search (VNS) by guiding the search in the shaking phase, and by employing the Skewed strategy. For this purpose, Second Order algorithms and Skewed functions expressing structural differences are embedded in an efficient VNS proposed in the literature for the degree constrained minimum spanning tree problem. Given an undirected graph with weights associated with its edges, the degree constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. Computational experiments are conducted on the largest and hardest benchmark instances found in the literature to date. We report results showing that the VNS with the proposed strategies improved the best known solutions for all the hardest benchmark instances. Moreover, these new best solutions significantly reduced the gaps with respect to tight lower bounds reported in the literature.     

Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm

The Routing and Wavelength Assignment problem is a graph optimization problem which deals with optical networks, where communication requests in a network have to be fulfilled. In this paper, we present a multilevel distributed memetic algorithm (ML-DMA) for the static RWA which finds provable optimal solutions for most benchmark instances with known lower bounds and is capable of handling large instances. Components of our ML-DMA include iterated local search, recombination, multilevel scaling, and a gossip-based distribution algorithm. Results demonstrated that our ML-DMA is among the most sophisticated heuristic RWA algorithms published so far.     

Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search.     

Iterated local search for workforce scheduling and routing problems

The integration of scheduling workers to perform tasks with the traditional vehicle routing problem gives rise to the workforce scheduling and routing problems (WSRP). In the WSRP, a number of service technicians with different skills, and tasks at different locations with pre-defined time windows and skill requirements are given. It is required to find an assignment and ordering of technicians to tasks, where each task is performed within its time window by a technician with the required skill, for which the total cost of the routing is minimized. This paper describes an iterated local search (ILS) algorithm for the WSRP. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. The computational results indicate that the proposed algorithm can produce high-quality solutions in short computation times.     

The balanced academic curriculum problem revisited

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.     

Well-tuned algorithms for the Team Orienteering Problem with Time Windows

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.     

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.      

A Boolean satisfiability approach to the resource-constrained project scheduling problem

We formulate the resource-constrained project scheduling problem as a satisfiability problem and adapt a satisfiability solver for the specific domain of the problem. Our solver is lightweight and shows good performance both in finding feasible solutions and in proving lower bounds. Our numerical tests allowed us to close several benchmark instances of the RCPSP that have never been closed before by proving tighter lower bounds and by finding better feasible solutions. Using our method we solve optimally more instances of medium and large size from the benchmark library PSPLIB and do it faster compared to any other existing solver.     

Curriculum-based course timetabling with SAT and MaxSAT

This paper describes our work on applying novel techniques based on propositional satisfiability (SAT) solvers and optimizers to the Curriculum-based Course Timetabling problem. Out of 32 standard benchmark instances derived from the Second International Timetabling Competition held in 2007, our techniques yield the best known solutions for 21 of them (19 of them being optimal), improving the previously best known solutions for 9. In addition, we obtain 18 new lower bounds for this benchmark set by applying a new full (Weighted) Partial MaxSAT approach of the Curriculum-based Course Timetabling problem.     

Improved lower bounds and exact algorithm for the capacitated arc routing problem

In the capacitated arc routing problem (CARP), a subset of the edges of an undirected graph has to be serviced at least cost by a fleet of identical vehicles in such a way that the total demand of the edges serviced by each vehicle does not exceed its capacity. This paper describes a new lower bounding method for the CARP based on a set partitioning-like formulation of the problem with additional cuts. This method uses cut-and-column generation to solve different relaxations of the problem, and a new dynamic programming method for generating routes. An exact algorithm based on the new lower bounds was also implemented to assess their effectiveness. Computational results over a large set of classical benchmark instances show that the proposed method improves most of the best known lower bounds for the open instances, and can solve several of these for the first time.     

The variable neighborhood search for the two machine flow shop problem with a passive prefetch

We consider the two machine flow shop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. Some new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate a high efficiency of the proposed approach for the new class of instances as well as for other classes of instances of the problem.     

New bounds and constraint propagation techniques for the clique partitioning problem

This paper considers the problem of clustering the vertices of a complete edge-weighted graph. The objective is to maximize the sum of the edge weights within the clusters (also called cliques). This so-called Clique Partitioning Problem (CPP) is NP-complete, and has several real-life applications such as groupings in flexible manufacturing systems, in biology, in flight gate assignment, etc. Numerous heuristics and exact approaches as well as benchmark tests have been presented in the literature. Most exact methods use branch and bound with branching over edges. We present tighter upper bounds for each search tree node than those known from the literature, improve the constraint propagation techniques for fixing edges in each node, and present a new branching scheme. The theoretical improvements are reflected by computational tests with real-life data. Although a standard solver delivers best results on randomly generated data, the runtime of the proposed algorithm is very low when being applied to instances on object clustering.     

Decomposition methods for the two-stage stochastic Steiner tree problem

A new algorithmic approach for solving the stochastic Steiner tree problem based on three procedures for computing lower bounds (dual ascent, Lagrangian relaxation, Benders decomposition) is introduced. Our method is derived from a new integer linear programming formulation, which is shown to be strongest among all known formulations. The resulting method, which relies on an interplay of the dual information retrieved from the respective dual procedures, computes upper and lower bounds and combines them with several rules for fixing variables in order to decrease the size of problem instances. The effectiveness of our method is compared in an extensive computational study with the state-of-the-art exact approach, which employs a Benders decomposition based on two-stage branch-and-cut, and a genetic algorithm introduced during the DIMACS implementation challenge on Steiner trees. Our results indicate that the presented method significantly outperforms existing ones, both on benchmark instances from literature, as well as on large-scale telecommunication networks.     

Lagrangean bounds for the optimum communication spanning tree problem

This paper considers the Optimum Communication Spanning Tree Problem. An integer programming formulation that yields tight LP bounds is proposed. Given that the computational effort required to obtain the LP bounds considerably increases with the size of the instances when using commercial solvers, we propose a Lagrangean relaxation that exploits the structure of the formulation. Since feasible solutions to the Lagrangean function are spanning trees, upper bounds are also obtained. These bounds are later improved with a simple local search. Computational experiments have been run on several benchmark instances from the literature. The results confirm the interest of the proposal since tight lower and upper bounds are obtained, for instances up to 100 nodes, in competitive computational times.     

Soft car sequencing with colors: Lower bounds and optimality proofs

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.     

Boosting local search with Lagrangian relaxation

Local search algorithms play an essential role in solving large-scale combinatorial optimization problems. Traditionally, the local search procedure is guided mainly by the objective function of the problem. Hence, the greedy improvement paradigm poses the potential threat of prematurely getting trapped in low quality attraction basins. In this study, we intend to utilize the information extracted from the relaxed problem, to enhance the performance of the local search process. Considering the Lin-Kernighan-based local search (LK-search) for the p-median problem as a case study, we propose the Lagrangian relaxation Assisted Neighborhood Search (LANS). In the proposed algorithm, two new mechanisms, namely the neighborhood reduction and the redundancy detection, are developed. The two mechanisms exploit the information gathered from the relaxed problem, to avoid the search from prematurely targeting low quality directions, and to cut off the non-promising searching procedure, respectively. Extensive numerical results over the benchmark instances demonstrate that LANS performs favorably to LK-search, which is among the state-of-the-art local search algorithms for the p-median problem. Furthermore, by embedding LANS into other heuristics, the best known upper bounds over several benchmark instances could be updated. Besides, run-time distribution analysis is also employed to investigate the reason why LANS works. The findings of this study confirm that the idea of improving local search by leveraging the information induced from relaxed problem is feasible and practical, and might be generalized to a broad class of combinatorial optimization problems.     

A hybrid heuristic for the diameter constrained minimum spanning tree problem

We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.