Search

The increased performance densities in the top of elite sports, sometimes mutual contest results are within the error margins of the measuring systems, has caused major problems in comparing performances and deciding on winners. In case of Dutch speed skating, the pool of highly competitive athletes is large, and, since there is a limit on the number of Olympic participators per country, the Olympic selection procedure is obviously a precarious affair. Because more than 100 years of data is available, we are able to study in this respect the well-known Gould hypothesis: When the sport matures, the variation in performance, especially at the top, decreases, and extreme events, where one athlete outperforms all his competitors, become rarer. Since Gould’s hypothesis only holds with ‘unchanged rules of the game’, several data corrections, for example on the introduction of the klap skate, are needed. A major goal of this paper is to analyze the possible role of Gould’s hypothesis concerning the growing performance densities for top speed skating.

This research investigated whether it is possible to explain the performance of talented youth speed skaters between the age of 15 to 20 years. Multidimensional performance characteristics were compared with the speed skating performance on separate distances (500 m, 1.000 m, 1.500 m and 3.000 m) and the allround performance, in the season of 2009-2010. Eight athletes from the Dutch national youth speed skating team (18-19 year old), along with 20 talented athletes from the Dutch district teams (15- 17 year old) were included. Multidimensional performance characteristics consisted of anthropometrical, physiological, technical and psychological characteristics. Partial correlations were calculated between each performance characteristic and the speed skating performance, while controlling for gender and age. For the 500 m, jump height, measured as a squat jump (r=-.664) and countermovement jump (r=-.619), and the technique of the speed skaters (r=-.500) was found to be an explanation of the performance. For the 1.000 m this was only jump height, measured as a squat jump (r=-.555) and countermovement jump (r=-.491). The speed skating performance on the longer distances (1.500 m and 3.000 m) were found to be significantly related with evaluation (r=-.420 and r=-.481) and anaerobic power (r=.409 with the 3.000 m). The allround speed skating performance was significantly related with jump height, measured as a squat jump (r=-.406) and related with the technique (r=-.541). It can be concluded that explaining the performance of talented youth speed skaters is difficult. Nevertheless, this study reveals that jump height and technique seem to be important prerequisites for almost all distances.

Decathlon coaches usually spend days or even weeks on designing training schedules for their athletes. A major complication is the fact that the athlete has only limited time for an extensive range of training exercises, whereas the effects of exercises on the athlete's performance in the various events are interrelated. This paper presents a mathematical model for optimizing the use of the total available training time by assigning time to training exercises. The data used in this time capacity planning model concerns a decathlete preparing for the Olympic Games.

In this paper we deal with a pseudo-Boolean representation of the simple plant location problem. We define instances of this problem that are equivalent, in the sense that each feasible solution has the same goal function value in all such instances. We further define a collection of polytopes whose union describes the set of instances equivalent to a given instance. We use the concept of equivalence to develop a method by which we can extend the set of instances that we can solve using our knowledge of polynomially solvable special cases. (C) 2008 Elsevier Ltd. All rights reserved.

The selection of entries to be included/excluded in Branch and Bound algorithms is usually done on the basis of cost values. We consider the class of Depth First Search algorithms, and we propose to use upper tolerances to guide the search for optimal solutions. In spite of the fact that it needs time to calculate tolerances, our computational experiments for Asymmetric Traveling Salesman Problems show that in most situations tolerance-based algorithms outperform cost-based algorithms. The solution time reductions are mainly caused by the fact that the branching process becomes much more effective, so that optimal solutions are found in an earlier stage of the branching process. The use of tolerances also reveals why the widely used choice for branching on a smallest cycle in assignment solutions is on average the most effective one. Moreover, it turns out that tolerance-based DFS algorithms are better in solving difficult instances than the Best First Search algorithm from Carpaneto et al. [Carpaneto, G., Dell'Amico, M., Toth, P., 1995. Exact solution of large-scale asymmetric traveling salesman problems. ACM Transactions on Mathematical Software 21 (4), 394-409]. (C) 2006 Elsevier B.V. All rights reserved.

An automated production system is considered in which several robots are used for transporting parts between workstations following a given route in a carousel mode. The problem is to maximize the throughput rate. Extending previous works treating scheduling problems for a single robot, we consider a more realistic case in which workstations are served by multiple robots. A graph model of the production process is developed, making it possible to apply PERT-CPM solution techniques. The problem is proved to be solvable in polynomial time. (c) 2005 Elsevier B.V. All rights reserved.

In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems-the 0-1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases. (c) 2004 Elsevier B.V. All rights reserved.

A feasible family of paths in a connected graph G is a family that contains at least one path between any pair of vertices in G. Any feasible path family defines a convexity on G. Well-known instances are: the geodesics, the induced paths, and all paths. We propose a more general approach for such 'path properties'. We survey a number of results from this perspective, and present a number of new results. We focus on the behaviour of such convexities on the Cartesian product of graphs and on the classical convexity invariants, such as the Caratheodory, Helly and Radon numbers in relation with Graph invariants, such as the clique number and other Graph properties. (c) 2004 Elsevier B.V. All rights reserved.

The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. This problem often appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present two techniques that enhance the performance of branch and bound algorithms. The new algorithms thus obtained are called branch and peg algorithms, where pegging refers to fixing values of variables at each subproblem in the branch and bound tree, and is distinct from variable fixing during the branching process. We present exhaustive computational experiments which show that the new algorithms generate less than 60% of the number of subproblems generated by branch and bound algorithms, and in certain cases require less than 10% of the execution times required by branch and bound algorithms.

The Data Correcting Algorithm is a branch and bound type algorithm in which the data of a given problem instance is `corrected' at each branching in such a way that the new instance will be as close as possible to a polynomially solvable instance and the result satisfies an acceptable accuracy (the difference between optimal and current solution). In this paper the data correcting algorithm is applied to determining exact and approximate optimal solutions to the simple plant location problem. Implementations of the algorithm are based on a pseudo-Boolean representation of the goal function of this problem, and a new reduction rule. We study the efficiency of the data correcting approach using two different bounds, the Khachaturov-Minoux bound and the Erlenkotter bound. We present computational results on several benchmark instances, which confirm the efficiency of the data-correcting approach.

Sensitivity analysis of e-optimal solutions is the problem of calculating the range within which a problem parameter may lie so that the given solution re-mains e-optimal. In this paper we study the sensitivity analysis problem for e-optimal solutions tocombinatorial optimization problems with min-max ob-jectives where e > 0. We show that the problem is easy if the original problem is easy. We also show that the converse is true under the assumption that it is possible to calculate an e-optimal solution to the problem in polynomial time.

Neighborhood search heuristics like local search and its variants are some of the most popular approaches to solve discrete optimization problems of moderate to large size. Apart from tabu search, most of these heuristics are memoryless. In this paper we introduce a new neighborhood search heuristic that makes effective use of memory structures in a way that is different from that in common implementations of tabu search. We report computational experiments with this heuristic on the traveling salesperson problem and the subset sum problem.

In this paper we study partial monotonizations and level polytopes of the Hamiltonian Cycle Polytope, also called the symmetric Traveling Salesman Polytope. The kth Level Polytope is the convex hull of the characteristic vectors corresponding to sets of k edges in K-n that can be extended to Hamiltonian cycles (n greater than or equal to 3). For 0 less than or equal to alpha less than or equal to k,, the alpha-monotonization of the kth Level Polytope is the convex hull of the characteristic vectors corresponding to sets of at least alpha and at most k edges in K-n that can be extended to Hamiltonian cycles (n greater than or equal to 3). It is shown that for alpha

The cardboard company Kappa Graphic Board produces several kinds of cardboard with various weights and thicknesses. If the thickness is above a certain value (namely 1.7 mm), the cardboard is composed of three layers which are glued together, and is called heavy weight cardboard. The three layers are produced on different machines; the production speed depends on the thickness of the layers. In this paper we restrict our analysis to heavy weight cardboard. The objective is to find a composition of the layers such that the throughput time is minimized. The problem is solved by means of an LP-model in which the objective function is a linearized working hours function; also a number of constraints are linearized. The results of the calculations indicate that it is possible to decrease the total number of working hours in the production process without a large increase of production costs.

Although k-best solutions for polynomial solvable problems are extensively studied in the literature not much is known for NP -hard problems. In this paper we design algorithms for finding sets of k-best solutions to the Traveling Salesman Problem (TSP) for some positive integer k. It will be shown that a set of k-best Hamiltonian tours in a weighted graph can be determined by applying the so-called partitioning algorithms and by algorithms based on modifications of solution methods like branch-and-bound. In order to study the effectiveness of these algorithms the time for determining a set of k-best solutions is investigated for a number of instances in Reinelt’s TSPLIB library. It appears that the time required to find a set of k-best tours grows rather slowly in k. Furthermore the results of numerical experiments show that the difference in length between a longest and a shortest tour in the set of k-best solutions grows only slowly in k and that also the ‘structure’ of the tours in the set of k-best tours is quite robust. Scope and purpose After having solved an optimization problem, it is often the case that one still must verify whether the optimal solution satisfies some additional restrictions that are not included in the original model. Such conditions are called “subtle conditions”. In the case of subtle conditions, it is particularly of interest to have a set of k-best solutions in order to see which of the solutions in that set satisfy the extra conditions and how high the “price” is for incorporating such conditions. Algorithms for finding sets of k-best solutions have mainly been studied in the literature for polynomially solvable combinatorial optimization problems. Little is known on algorithms for finding k-best solutions for NP -hard combinatorial optimization problems. In this paper, we study algorithms for finding k-best solutions for one of the most notorious NP-hard problems, namely the Traveling Salesman Problem (TSP). Properties of the sets of k-best solutions for the TSP, such as the increase in tour length and the number of edges that the k-best solutions have in common or differ in, are discussed in detail.

This paper answers the (non)adjacency question for the whole spectrum of Hamiltonian cycles on the Hamiltonian cycle polytope (HC-polytope), also called the symmetric traveling salesman polytope, namely from Hamiltonian cycles that differ in only two edges through Hamiltonian cycles that are edge disjoint. The HC-polytope is the convex hull of the characteristic vectors corresponding to the Hamiltonian cycles of K-n, (n greater than or equal to 3). Let 2 less than or equal to k less than or equal to n. The k-interchange graph is the graph with as vertices the 1/2(n -1)! Hamiltonian cycles of K-n,, and an edge between two vertices if and only if the corresponding Hamiltonian cycles differ in an interchange of k edges. It is shown that the 2- and the 3-interchange graphs are the only ones that are subgraphs of the skeleton of the HC-polytope; the (n -1)- and the n-interchange graphs are the only ones that do not have edges in common with the skeleton. For each k with 4 less than or equal to k less than or equal to n-2, there are Hamiltonian cycles that are adjacent and cycles that are nonadjacent on the skeleton. Finally, the Hamiltonicity of k-interchange graphs is solved for several values of k.

This paper deals with a vehicle routing problem with split demands, namely the problem of determining a flight schedule for helicopters to off-shore platform locations for exchanging crew people employed on these platforms. The problem is formulated as an LP model and solved by means of a column-generation technique including solving TSP problems. Since the final solution needs to be integral, we have chosen a rounding procedure to obtain an integer solution. Since the LP approach needs a considerable amount of computer time, it is only suitable for long-term planning practices. For the usual short-term planning, we have designed the so-called Cluster-and-Route Heuristic together with a number of improvement heuristics. The Cluster-and-Route procedure constructs a suitable clustering of the platforms and simultaneously forms the routes of the helicopter flights associated with the clusters. This approach is different from the usual heuristics, in which the clusters are constructed first, and the routes for each cluster are made afterwards. Simulations with various data sets show that the new heuristic outperforms the usual heuristics for vehicle routing problems. Even better results are obtained when improvement heuristics are applied. We use four improvement heuristics, including, so-called 1-opt and 2-opt procedures.

We show how to use ATP and WTA rankings to estimate the probability that a player with a certain ranking advances to a specific round (for instance, the quarterfinals) in an upcoming tournament. We use the results from Grand Slam and Olympic tournaments in the period 2004 ? 2014. Pooling the data, which is justified according to our tests, allows us to compute probabilities with relatively small confidence intervals. For instance, the probability of a top 4 tennis player to reach the quarterfinals is 0.722 with a 95% confidence interval of (0.669; 0.771). This study was motivated by a request from the Dutch Olympic Committee (NOC*NSF). Based on our results, NOC*NSF decides which Dutch single tennis players to invite to participate at the 2016 Olympic Games of Rio de Janeiro

Seven criteria for integer sequences being graphic are listed. Being graphic means that there is a simple graph with the given integer sequence as degree sequence. One of the criteria leads to a new and constructive proof of the well-known criterion of Erdös-Gallai.

A Pseudo-Boolean Formulation of the SPLPPreprocessing SPLP instancesThe Data Correcting AlgorithmComputational Experience with SPLP Instances6.4.16.4.26.4.36.4.46.4.56.4.6Testing the Effectiveness of the Reduction Procedure RPBilde and Krarup-type InstancesGalvao and Raggi-type InstancesInstances from the OR-LibraryKorkel-type Instances with 65 SitesKorkel-typeInstances with 100 Sites

Although Branch-and-bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the classical BnB trees, and that Solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp-Steele procedure are tile fastest, and that 'iterative' Modified Karp-Steele patching generates the smallest search trees. (c) 2005 Elsevier B.V. All rights reserved.

The Data-Correcting (DC) Algorithm is a recursive branch-and-bound type algorithm, in which the data of a given problem instance are “heuristically corrected” at each branching in such a way that the new instance will be as close as possible to polynomially solvable and the result satisfies a prescribed accuracy (the difference between optimal and current solution). In this paper the DC algorithm is applied to determining exact or approximate global minima of supermodular functions. The working of the algorithm is illustrated by an instance of the Simple Plant Location (SPL) Problem. Computational results, obtained for the Quadratic Cost Partition Problem (QCP), show that the DC algorithm outperforms a branch-and-cut algorithm, not only for sparse graphs but also for nonsparse graphs (with density more than 40%), often with speeds 100 times faster.

This paper discusses stability analysis for the Traveling Salesman Problem (TSP). For a traveling salesman tour which is known to be optimal with respect to a given instance (length vector) we are interested in determining the stability region, i.e. the set of all length vectors for which the tour is optimal. The following three subsets of the stability region are of special interest: 1. (1) tolerances, i.e. the maximum perturbations of single edges; 2. (2) tolerance regions which are subsets of the stability region that can be constructed from the tolerances; and 3. (3) the largest ball contained in the stability region centered at the given length vector (the corresponding radius is known as the stability radius). It is well known that the problems of determining tolerances and the stability radius for the TSP are NP -hard so that in general it is not possible to obtain the above-mentioned three subsets without spending a lot of computation time. The question addressed in this paper is the following: assume that not only an optimal tour is known, but also a set of k shortest tours (k ⩾2) is given. Then to which extent does this allow us to determine the three subsets in polynomial time? It will be shown in this paper that having k-best solutions can give the desired information only partially. More precisely, it will be shown that only some of the tolerances can be determined exactly and for the other ones as well as for the stability radius only lower and/or upper bounds can be derived. Since the amount of information that can be derived from the set of k-best solutions is dependent on both the value of k as well as on the specific length vector, we present numerical experiments on instances from the TSPLIB library to analyze the effectiveness of our approach.

Scheduling in process industries is very complex, due to for example (partly) identical machines, shared resources, sequence-dependent set-up times, flow shops with limited intermediate storage, and manual operations carried out off-line. Moreover, it is not possible to define one objective function. Objectives of the scheduling are to obtain a feasible schedule, to meet due dates, to minimize the inventory, and to minimize additional costs such as costs of overtime and extra personnel.

The problem of minimizing and maximizing the objective function of the Traveling Salesman Problem (TSP) is discussed. In particular, we consider two special cases of the TSP, namely the small TSP and the large TSP, for which both a minimum and a maximum of the objective function can be obtained in polynomial time. The cost matrix C = ( c ij ) corresponding to the small (large) TSP is defined by c ij = min{ a i , b j } ( c ij = max{ a i , b j }) for each 1, j = 1, … n and n -dimensional real vector a and ba . The main purpose of this paper is to show the relationship between the subtour elimination algorithm of Gilmore and Gomory for the large TSP, and Gabovich's algorithm for the small TSP. The recognition problem for these two types of matrices is solved by using Deineko and Filonenko's algorithm for recognizing permuted distribution matrices. Finally, as an application, a problem from machine scheduling theory is considered.

In the process industry, homogeneous products have to be packed. For an unpacked product (milk, paint), a variety of packaging materials (glass, tin) and packaging sizes ( 1 2 litre, 1 kilo) are available. Generally, the packaging lines are used for various products (milk, buttermilk) in one type of packaging material (glass) and various packaging sizes ( 1 2 litre, 1 litre). These possibilities make the scheduling of the packaging lines rather complex. In recent years, under market pressure, the number of products in the process industry has been increased, the order sizes have been reduced, and the delivery times have been shortened. This has caused augmented scheduling tasks and, usually, the scheduling systems supporting these tasks have not followed these changes sufficiently. We have investigated and compared the origins of the increasing complexity of the scheduling problems of several companies in the process industry producing dairy products, pharmaceutical products, tobacco, paint, chocolate products, and foods, and we have analyzed the ways in which these companies deal with this increasing complexity in different situations. Schedulers have to deal with a wide range of information such as due dates, availability of material, sequence-dependent set-up times, and availability of packaging lines and employees. In most cases the scheduling is still done by hand, which is very time-consuming. We show the need for a more adequate support system which will provide necessary information, and speed up the development and evaluation of production schedules. We also discuss future trends with regard to the packaging process, and their likely effect on the scheduling process.

A τ-partition of a subset of a given p-set X can be extended in many different ways to a τ-partition of X. The Stirling number of the second kind S(p, τ) can be defined as the number of all τ-partitions of X, and can be regarded as the number of all possible extensions of the τ-partitions of all the τ-subsets of X. In this paper we study the number of extensions for a particular choice of τ-partitions of the m-subsets of X, with 1 ⩽ m ⩽ p.

This paper deals with questions raised by R.A. Brualdi concerning the structure matrix of (0,1)-matrices with fixed row and column sum vectors; namely, determining its rank and—in case the matrices are square—its eigenvalues. It turns out that the trace of the structure matrix has some interesting properties. The rank of the structure matrix has the values 1,2, or 3; this yields a classification of econometric models.

Two-minor stable matrices are square matrices such that all (2,2) minors with no elements on the main diagonal are zero. The effects of taxes and subsidies on the competitive prices of output in Leontief's input-output model are examined by e.g. Metzler, Allen and Atsumi. We reexamine these studies and give results under more “normal” assumptions. Using two-minor stable matrices, the question is answered under what conditions the prices of the nontaxed and nonsubsidized goods do not change.

The vertices of the skeleton of the symmetric Traveling Salesman Polytope are the characteristic vectors coffesponding to the Hamiltonian tours in the complete graph K(n) with n greater-than-or-equal-to 3, and the edges of this skeleton are the 1-faces of the polytope. It is shown that this skeleton contains a Hamiltonian tour such that the Hamiltonian cycles in K(n) corresponding to two successive vertices differ in a single interchange, i.e., the interchange graph corresponding to the TSP-polytope is Hamiltonian. It is also shown that the skeleton can be covered by 1/2(n-2)! cliques, and has diameter at most n-3.

The consequences of arbitrary changes of the final demand vector for the gross production vector in the open Leontief model are studied, and several properties of non-negative irreducible square matrices are obtained.

It was a pity for the manager Mr. Jenson that the young management trainee Tom did not offer him the optimal solution for the meetings scheduling problem that bothered Mr. Jensen so much. Below, three possible optimal solutions are offered using Apex, the cheapest insertion rule, and the three-Opt heuristic. Response from J. Telgen, author of the original paper, follows.