Decomposition and local search based methods for the traveling umpire problem

The Traveling Umpire Problem (TUP) is a challenging combinatorial optimization problem based on scheduling umpires for Major League Baseball. The TUP aims at assigning umpire crews to the games of a fixed tournament, minimizing the travel distance of the umpires. The present paper introduces two complementary heuristic solution approaches for the TUP. A new method called enhanced iterative deepening search with leaf node improvements (IDLI) generates schedules in several stages by subsequently considering parts of the problem. The second approach is a custom iterated local search algorithm (ILS) with a step counting hill climbing acceptance criterion. IDLI generates new best solutions for many small and medium sized benchmark instances. ILS produces significant improvements for the largest benchmark instances. In addition, the article introduces a new decomposition methodology for generating lower bounds, which improves all known lower bounds for the benchmark instances.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

Maximizing breaks and bounding solutions to the mirrored traveling tournament problem

We investigate the relation between two aspects of round robin tournament scheduling problems: breaks and distances. The distance minimization problem and the breaks maximization problem are equivalent when the distance between every pair of teams is equal to 1. We show how to construct schedules with a maximum number of breaks for some tournament types. The connection between breaks maximization and distance minimization is used to derive lower bounds to the mirrored traveling tournament problem and to prove the optimality of solutions found by a heuristic for the latter.     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

A new branch-and-price algorithm for the traveling tournament problem

The traveling tournament problem (ttp) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp. The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes in Computer Science, Springer Verlag Berlin/Heidelberg, pp. 100–109, who suggest to solve the tour-generation subproblem by constraint programming. In contrast to their approach, our method explicitly utilizes the network structure of the compact formulation: First, the column-generation subproblem is a shortest-path problem with additional resource and task-elementarity constraints. We show that this problem can be reformulated as an ordinary shortest-path problem over an expanded network and, thus, be solved much faster. An exact variable elimination procedure then allows the reduction of the expanded networks while still guaranteeing optimality. Second, the compact formulation gives rise to supplemental branching rules, which are needed, since existing rules do not ensure integrality in all cases. Third, non-repeater constraints are added dynamically to the master problem only when violated. The result is a fast exact algorithm, which improves many lower bounds of knowingly hard ttp instances from the literature. For some instances, solutions are proven optimal for the first time.     

Dantzig–Wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling

In this paper, we considered the problem of Curriculum-Based Course Timetabling, i.e., assigning weekly lectures to a time schedule and rooms. We developed a Column Generation algorithm based on a pattern formulation of the time scheduling part of the problem by Bagger et al. (2016). The pattern formulation is an enumeration of all schedules by which each course can be assigned on each day; it is a lower bounding model. Pattern enumeration has also been considered in Burke (2008), where the authors enumerated all schedules to which each curriculum can be assigned on each day. We applied the Dantzig–Wolfe reformulation, so each column corresponded to a schedule for an entire day.We solved the reformulation with the Column Generation algorithm, where each pricing problem generated a full schedule for a single day. We provided a pre-processing technique that, on average, removed approximately 45% of the pattern variables in the pricing problems. We then extended the pre-processing technique into inequalities that we added to the model. Lastly, we describe how we applied Local Branching to the pricing problem by using the columns generated in previous iterations.We compare the lower bounds we obtained, with other methods from literature, on 20 data instances of real-world applications. For 16 instances the optimal solutions are known, but the remaining four are still open. Our approach improved the best-known lower bound for all four open instances, and decreased the average gap from 24 to 11%.     

An effective VNS for the capacitated p-median problem

In the capacitated p-median problem (CPMP), a set of n customers is to be partitioned into p disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Competitive Memetic Algorithms for Arc Routing Problems

The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.     

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.     

Improved lower bounds for the early/tardy scheduling problem with no idle time

In this paper, we consider the single machine earliness/tardiness scheduling problem with no idle time. Two of the lower bounds previously developed for this problem are based on Lagrangean relaxation and the multiplier adjustment method, and require an initial sequence. We investigate the sensitivity of the lower bounds to the initial sequence, and experiment with different dispatch rules and some dominance conditions. The computational results show that it is possible to obtain improved lower bounds by using a better initial sequence. The lower bounds are also incorporated in a branch-and-bound algorithm, and the computational tests show that one of the new lower bounds has the best performance for larger instances.     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.     

Team assignments and scheduling for the NCAA basketball tournament

The National Collegiate Athletic Association (NCAA) organizes a men's basketball tournament every March to determine the national champion for the current season. In organizing the tournament, the emphasis is typically on selection of the most deserving teams to participate and providing a fair, equitable environment in which to play that result in a true, undisputed champion for the season. However, there are growing concerns of dwindling actual attendance at tournament games and increasing financial burden on the NCAA related to reimbursable team travel expenses. In this paper, we describe the development of an integer program designed to optimize team assignments in the sense of minimizing the distance travelled by teams to game sites and the corresponding travel costs. The goal is to increase tournament accessibility to fans as well as lessen the financial impact to the NCAA while maintaining the integrity of the tournament. We test our model against actual tournament assignments from the past 5 years. Results show consistent and significant cost savings and reductions in distance travelled without compromising the fairness and structure of the tournament. Overall, we demonstrate the usefulness of the model in both operational and strategic business decisions.     

Survivable network design with shared-protection routing

In this paper we study the problem of designing a survivable telecommunication network with shared-protection routing. We develop a heuristic algorithm to solve this problem. Recent results in the area of global re-routing have been used to obtain very tight lower bounds for the problem. Our results indicate that in a majority of problem instances, the average gap between the heuristic solutions and the lower bounds is within 5%. Computational experience is reported on randomly generated problem instances with up to 35 nodes, 80 edges and 595 demand pairs and also on the instances available in SNDlib database.     

Note on the characteristic roots of tournament matrices

We give bounds for the real parts of the characteristic roots of tournament matrices.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

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.     

Packing Superballs from Codes and Algebraic Curves

In the present paper, we make use of codes with good parameters and algebraic curves over finite fields with many rational points to construct dense packings of superballs. It turns out that our packing density is quite reasonable. In particular, we improve some values for the best-known lower bounds on packing density.     

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.     

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.