A General Decomposition Algorithm for Parallel Queues with Correlated Arrivals

Queueing with correlated arrivals occurs when customers arrive at a set of queues simultaneously. The difficulty in analyzing systems with correlated arrivals is due to the fact that the individual queueing systems are stochastically dependent. Exact methods for analyzing these systems are computationally intensive and are limited to only a few special cases. In this paper, we consider a system of parallel queues with bulk service and correlated arrivals. We show how the matrix-geometric approach can be used to obtain the performance measures of the system. We also develop an algorithm for large systems that efficiently approximates the performance measures by decomposing it into individual queueing systems. Finally, we describe how the principles of our decomposition algorithm can be extended to analyze a variety of different parallel queueing systems with correlated arrivals. We then evaluate the accuracy of our algorithm through a numerical study.     

On patching algorithms for random asymmetric travelling salesman problems

Let the arc-lengthsL _ij of a complete digraph onn vertices be independent uniform [0, 1] random variables. We consider the patching algorithm of Karp and Steele for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. We extend these ideas to thek-person travelling salesman problem and also consider the case where cities can be visited more than once.     

Interactive decision software and computer graphics for architectural and space planning

We describe the development and successful implementation of a decision support system now being used by several leading firms in the architecture and space planning industries. The system, which we call SPDS (spatial programming design system) has the following characteristics: (i) user-friendly convenience features permitting architects and space planners to operate the system without being experienced programmers; (ii) interactive capabilities allowing the user to control and to manipulate relevant parameters, orchestrating conditions to which his or her intuition provides valuable input; (iii) informative and understandable graphics, providing visual displays of interconnections that the computer itself treats in a more abstract methematical form; (iv) convenient ways to change configurations, and to carry out ‘what if’ analyses calling on the system’s decision support capabilities; (v) a collection of new methods, invisible to the user, capable of generating good solutions to the mathematical programming problems that underlie each major design component. These new methods succeed in generating high quality solutions to a collection of complex discrete, highly nonlinear problems. While these problems could only be solved in hours, or not at all, with previously existing software, the new methods obtain answers in seconds to minutes on a minicomputer. Major users, including Dalton, Dalton, Newport, and Marshal Erdwin, report numerous advantages of the system over traditional architectural design methods.     

Using the analytic center in the feasibility pump

The feasibility pump (FP) has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems. Briefly, FP alternates between two sequences of points: one of feasible solutions for the relaxed problem, and another of integer points. This short paper extends FP, such that the integer point is obtained by rounding a point on the (feasible) segment between the computed feasible point and the analytic center for the relaxed linear problem.     

Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.     

Fast regularized linear sampling for inverse scattering problems

A new numerical procedure is proposed for the reconstruction of the shape and volume of unknown objects from measurements of their radiation in the far field. This procedure is a variant and the linear sampling method has a very acceptable computational load and is fully automated. It is based on exploiting an iteratively computed truncated singular‐value decomposition and heuristics to extract the desired signal from the background noise. Its performance on a battery of examples of different types is shown to be promising. Copyright © 2010 John Wiley & Sons, Ltd.     

Designing and reporting on computational experiments with heuristic methods

This article discusses the design of computational experiments to test heuristic methods and provides reporting guidelines for such experimentation. The goal is to promote thoughtful, well-planned, and extensive testing of heuristics, full disclosure of experimental conditions, and integrity in and reproducibility of the reported results.     

Generating quadratic assignment test problems with known optimal permutations

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem of which the travelling-salesman problem is a special case. Although the QAP has been extensively studied during the past three decades, this problem remains very hard to solve. Problems of sizes greater than 15 are generally impractical to solve. For this reason, many heuristics have been developed. However, in the literature, there is a lack of test problems with known optimal solutions for evaluating heuristic algorithms. Only recently Paulubetskis proposed a method to generate test problems with known optimal solutions for a special type of QAP. This paper concerns the generation of test problems for the QAP with known optimal permutations. We generalize the result of Palubetskis and provide test-problem generators for more general types of QAPs. The test-problem generators proposed are easy to implement and were also tested on several well-known heuristic algorithms for the QAP. Computatinal results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP. Comparison with Palubetskis' procedure was made, showing the superiority of the new test-problem generators. Three illustrative test problems of different types are also provided in an appendix, together with the optimal permutations and the optimal objective function values.     

Another greedy heuristic for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic.     

Survivable networks,linear programming relaxations and the parsimonious property

We consider the survivable network design problem — the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and thek-edge-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable network design problem.The research of both authors was partially supported by the National Science Foundation under grant ECS-8717970 and the Leaders for manufacturing program at MIT.