Search

This paper presents the results of an empirical study of the effects of coefficient correlation structure and constraint slackness settings on the performance of solution procedures on synthetic two-dimensional knapsack problems (2KP). The population correlation structure among 2KP coefficients, the level of constraint slackness, and the type of correlation (product moment or rank) are varied in this study. Representative branch-and-bound and heuristic solution procedures are used to investigate the influence of these problem parameters on solution procedure performance. Population correlation structure, and in particular the interconstraint component of the correlation structure, is found to be a significant factor influencing the performance of both the algorithm and the heuristic. In addition, the interaction between constraint slackness and population correlation structure is found to influence solution procedure performance. [ABSTRACT FROM AUTHOR]

This paper describes three approaches to assigning tasks to earth observing satellites (EOS). A fast and simple priority dispatch method is described and shown to produce acceptable schedules most of the time. A look ahead algorithm is then introduced that outperforms the dispatcher by about 12% with only a small increase in run time. These algorithms set the stage for the introduction of a genetic algorithm that uses job permutations as the population. The genetic approach presented here is novel in that it uses two additional binary variables, one to allow the dispatcher to occasionally skip a job in the queue and another to allow the dispatcher to occasionally allocate the worst position to the job. These variables are included in the recombination step in a natural way. The resulting schedules improve on the look ahead by as much as 15% at times and 3% on average. We define and use the "window-constrained packing" problem to model the bare bones of the EOS scheduling problem. [ABSTRACT FROM AUTHOR]

Routing problems appear frequently when dealing with the operation of communication or transportation networks. Among them, the message routing problem plays a determinant role in the optimization of network performance. Much of the motivation for this work comes from this problem which is shown to belong to the class of nonlinear convex multicommodity flow problems. This paper emphasizes the message routing problem in data networks, but it includes a broader literature overview of convex multicommodity flow problems. We present and discuss the main solution techniques proposed for solving this class of large-scale convex optimization problems. We conduct some numerical experiments on the message routing problem with four different techniques. [ABSTRACT FROM AUTHOR]

In a discrete-event simulation, the information related to the events scheduled to occur in the future is kept in a data structure called the future event set (FES). In this paper, we study the interaction hold model a popular stochastic model for FES performance analysis, corresponding to the superposition of a (fixed) number of renewal processes. The general state-space Markov chain formed by the discrete-time process that keeps track, at event times, of the residual lifetimes is shown here to be recurrent in the sense of Harris, and its stationary distribution is obtained. Linked lists and indexed lists, two popular FESs, are investigated using this model. For the interaction hold model, we make rigorous certain published results as well as introduce new ones. For example, we derive the distribution of the relative position of the event to be inserted in the data structure. In the exponential case, our analytic and empirical results confirm that when events with relatively short lifetimes often get regenerated upon their occurrence, it is better to scan a list (or sublist) from its head rather than tail. In the same context and for indexed lists with sublists with constant sizes, our results suggest that subsequent sublists should be of larger sizes, i.e., the first sublist should contain the smallest number of records, the second sublist the second smallest number of records, etc. [ABSTRACT FROM AUTHOR]

A new concept is proposed for linking algebraic modeling languages with structure-exploiting solvers. SPI (Structure-Passing Interface) is a program that retrieves structure from an anonymous mathematical program built by an algebraic modeling language. SPI passes the special structure of the problem to an SES (Structure-Exploiting Solver). An integration of SPI and SES leads to SET (Structure-Exploiting Tool) and can be used with any algebraic modeling language. This approach relies on the idea that most exploitable block structures can be easily detected from the algebraic formulation of models. It should enable algebraic modeling languages to access the large body of algorithmic techniques which require problem structure. [ABSTRACT FROM AUTHOR]

We propose a new algorithm for solving integer programming (IF) problems that is based on ideas from algebraic geometry. The method provides a natural generalization of the Parkas lemma for IP, leads to a way of performing sensitivity analysis, offers a systematic enumeration of all feasible solutions, and gives structural information of the feasible set of a given IP. We provide several examples that offer insights on the algorithm and its properties. [ABSTRACT FROM AUTHOR]

The literature in the field of interior point methods for Linear Programming has been almost exclusively algorithmic oriented. Very few contributions have been made towards the theory of Linear Programming itself. In particular none of them offer a simple, self-contained introduction to the theory of Linear Programming and linear inequalities. The purpose of this paper is to show that the interior point methodology can be used to introduce the field of Linear Programming. Starting from scratch, and using only elementary results from calculus and linear algebra, we prove that for every value of the barrier parameter, the logarithmic barrier function for the primal-dual problem has a unique minimizer, and that the path of these minimizers (the central path) converges to a strictly complementary pair of optimal solutions. These results were proved more than a decade ago with advanced mathematical arguments. Our proofs are new: they are also simpler and often more natural than the ones currently known. They provide a new approach to the fundamental results of Linear Programming, including the existence of a strictly complementary solution, and the strong duality theorem. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new graph, the sequential decision diagram, to aid in modeling, formulation, and solution of sequential decision problems under uncertainty. While as compact as an influence diagram, the sequential diagram captures the asymmetric and sequential aspects of decision problems as effectively as decision trees. We show that a unified framework, consisting of a sequential diagram, an influence diagram, and a common formulation table for the problem's data, suffices for compact and consistent representation, economical formulation, and efficient solution of (asymmetric) decision problems. In addition to asymmetry, the framework exploits other sources of computational efficiency, such as conditional independence and value function decomposition, making it also useful in evaluating dynamic-programming problems. The formulation table and recursive algorithm can be readily implemented in computers for solving large-scale problems. Examples are provided to illustrate the methodology in both asymmetric and symmetric cases. [ABSTRACT FROM AUTHOR]

This paper is concerned with the general dynamic lot size model, or (generalized) Wagner-Whitin model. Let n denote the number of periods into which the planning horizon is divided. We describe a simple forward algorithm which solves the general model in 0(n log n) time and 0(n) space, as opposed to the well-known shortest path algorithm advocated over the last 30 years with 0(n[sup 2]) time. A linear, i.e., 0(n)-time and space algorithm is obtained for two important special cases: (a) models without speculative motives for carrying stock, i.e., where in each interval of time the per unit order cost increases by less than the cost of carrying a unit in stock; (b) models with non-decreasing setup costs. We also derive conditions for the existence of monotone optimal policies and relate these to known (planning horizon and other) results from the literature. [ABSTRACT FROM AUTHOR]

Wilson (1986) gives a backwards induction algorithm for sequentially obtaining the optimal next move in a repeated Bayesian game. In this paper we show how to identify the form of an optimal solution of such a game by a graphical procedure. By means of the Prisoner's Dilemma game, we illustrate how Wilson's algorithm can be enhanced using the derived analytic form of the solution to produce an explicit optimal strategy. We can then determine not only how P[sub 1] should play on all subsequent moves of the game, but also use ideas of Bayes rationality to discuss whether a given model of P[sub 2]'s reactions is realistic. [ABSTRACT FROM AUTHOR]

Copyright of Management Science is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented. The algorithm is based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions. Computational experiments (up to 2,000 operations) show that the algorithm not only finds shorter makespans than the best approximation approaches but also runs in shorter time. It solves the well-known 10 x 10 hard benchmark problem within 30 seconds on a personal computer. [ABSTRACT FROM AUTHOR]