The Covering Tour Problem (CTP) is defined on a graph G = (V ∪ W, E), where W is a set of vertices that must be covered. The CTP consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a prespecified distance from the cycle. The problem is first formulated as an integer linear program, polyhedral properties of several classes of constraints are investigated, and an exact branch-and-cut algorithm is developed. A heuristic is also described. Extensive computational results are presented.
The problem of maximizing the production of good sets of semiconductor chips under random yield is reexamined in this paper. (A set of semiconductor chips is called a semiconductor kit.) This problem has been considered by Avram and Wein (Avram, F., L. Wein. 1992. A product design problem in semiconductor manufacturing. Opns. Res. 40(5) 986–998.) and Singh et al. (Singh, M. R., C. T. Abraham, R. Akella. 1988. Planning for production of a set of components when yield is random. Fifth IEEE CHMT Internat. Electronic Manufacturing Technology Proc.). To solve this problem we show that under certain combinations of assumptions the production process can be replaced by a black box. The use of the black box model considerably simplifies the analysis and reduces the simulation effort required for carrying out parametric analysis of the proposed solution procedure. The model includes that of Avram and Wein, and we extend their results to more general settings and strengthen their conclusions. Using the black box model, it is shown that the strategy of placing different types of chips on a single wafer gives larger yield of kits in a stochastic sense than the traditional method of placing single types of chips on a wafer. We compare the production of kits under different chip design and lot release policies and also carry out a parametric analysis with respect to factors such as set proportions and yield.
We consider a variant of the classical symmetric Traveling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This NP-hard problem is known in the literature as the symmetric Generalized Traveling Salesman Problem (GTSP), and finds practical applications in routing, scheduling and location-routing. In a companion paper (Fischetti et al. [Fischetti, M., J. J. Salazar, P. Toth. 1995. The symmetric generalized traveling salesman polytope. Networks 26 113–123.]) we modeled GTSP as an integer linear program, and studied the facial structure of two polytopes associated with the problem. Here we propose exact and heuristic separation procedures for some classes of facet-defining inequalities, which are used within a branch-and-cut algorithm for the exact solution of GTSP. Heuristic procedures are also described. Extensive computational results for instances taken from the literature and involving up to 442 nodes are reported.
Most earlier mathematical studies of baseball required particular models for advancing runners based on a small set of offensive possibilities. Other efforts considered only teams with players of identical ability. We introduce a Markov chain method that considers teams made up of players with different abilities and which is not restricted to a given model for runner advancement. Our method is limited only by the available data and can use any reasonable deterministic model for runner advancement when sufficiently detailed data are not available. Furthermore, our approach may be adapted to include the effects of pitching and defensive ability in a straightforward way. We apply our method to find optimal batting orders, run distributions per half inning and per game, and the expected number of games a team should win. We also describe the application of our method to test whether a particular trade would benefit a team.