Search

Because public systems problems are frequently ill-defined and have fuzzy constraints and vague multiple objectives, their solution by means of formal optimization models is not widely accepted. This paper will explore the modes (both useful and otherwise) in which optimization has been applied to such problems. The need for optimization models which somehow "fit" the decision-makers' methods and backgrounds will be discussed. Several other aspects of public systems optimization will be considered, in a somewhat random fashion. This paper will raise more questions than answers. [ABSTRACT FROM AUTHOR]

Due to the complexity of optimum replacement problems over finite time horizons various asymptotic criteria based upon fixed age replacement policies have been employed in the literature and in practice. In this paper the relationships between the optimum policies under three alternative cost criteria are considered. An ordering of the accounting costs under two of these is obtained, and for distributions with Increasing Hazard Rate an ordering of the optimum replacement time is derived. For a finite time horizon the policies are compared to the optimal sequential and fixed-age replacement polices through the example of a gamma distribution previously investigated by Barlow and Proschan (1962, 1965). [ABSTRACT FROM AUTHOR]

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]

The single-sink, fixed-charge transportation problem has a variety of applications, including supplier selection, product distribution/fleet selection, and process selection. In this paper we present a dynamic programming algorithm for solving this important problem that is very easy to implement and that improves considerably in terms of computational attractiveness on the best methods in the literature. [ABSTRACT FROM AUTHOR]

Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instance in two-or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial structure, instead of having to consider one packing at a time. In addition, we can make use of elegant algorithmic properties of certain classes of graphs. This allows our characterization to be the basis for a successful branch-and-bound framework. This is the first in a series of papers describing new approaches to higher-dimensional packing. [ABSTRACT FROM AUTHOR]

Recent studies have demonstrated the effectiveness of applying adaptive memory tabu search procedures to combinatorial optimization problems. In this paper we describe the development and use of such an approach to solve binary quadratic programs. Computational experience is reported, showing that the approach optimally solves the most difficult problems reported in the literature. For challenging problems of limited size, which are capable of being approached by exact procedures, we find optimal solutions considerably faster than the best reported exact method. Moreover, we demonstrate that our approach is significantly more efficient and yields better solutions than the best heuristic method reported to date. Finally, we give outcomes for larger problems that are considerably more challenging than any currently reported in the literature. [ABSTRACT FROM AUTHOR]

Traditional sensitivity analysis of linear programming objective function coefficients concerns itself with variations in single parameters. In a recent book, Gal developed a theoretical framework to determine the effect of mutliple variations in the parameters. In this paper, we develop a methodology to implement and extend the theoretical results in the earlier work for interval variations of objective function coefficients. This methodology uses necessary and sufficient conditions to determine all optimal solutions to the linear programming problem for objective function coefficients within given intervals. The resulting procedure has been coded for computer use and tested on various types of test problems. Computational results and an example are presented. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to take stock of what is known and to suggest some conceptual foundations for future progress in the areas of postoptimality analysis and parametric optimization techniques for integer programming. [ABSTRACT FROM AUTHOR]

In 1970, abortion on demand was legalized in several sections of the United States. Due to increased demand for abortions, free standing abortion clinics came into existence. This paper develops a methodology for determining the optimal design of a free standing abortion clinic, in order to maximize its profits. An example of a clinic which was actually designed employing the methodology is presented, and the results suggest that the methodology is relevant and useful. [ABSTRACT FROM AUTHOR]

The paper presents a means of attempting to account for overhead, as well as function evaluations, in evaluating unconstrained optimization techniques. Criteria are established which compare techniques on classes of algorithms. While not completely machine independent, and certainly not programmer independent, the new method eliminates much of the machine dependency of earlier criteria. The criteria are applied to three known and one new quasi-Newton algorithm, with interesting results. [ABSTRACT FROM AUTHOR]

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) interactions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to 30 facilities. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988. [ABSTRACT FROM AUTHOR]

Assembly line balancing problems are concerned with the optimization of manufacturing processes. In this paper we consider the so-called simple assembly line balancing problem with the objective of minimizing the number of used workstations. This problem is denoted by SALB-1 in the literature. For tackling this problem, we present a so-called Beam-ACO approach. This technique results from hybridizing the metaheuristic ant colony optimization with beam search. The experimental results show that our algorithm is a state-of-the-art method for this problem. It can solve 263 of 269 existing benchmark instances to optimality. [ABSTRACT FROM AUTHOR]

In this paper, we propose a model of intertemporal choice that explicitly incorporates satiation due to previous consumption in the evaluation of the utility of current consumption. In the discounted utility (DU) model, the utility of consumption is evaluated afresh in each time period. In our model, the utility of current consumption represents an incremental utility from the past level. When the time interval between consumption periods is large, and there are, therefore, no carryover effects, our model coincides with the DU model. For short time intervals between consumption periods, the satiation due to previous consumption lowers the utility of current consumption. Several implications of our model are examined, and comparisons with the DU model and the habituation model are made. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: ... to the more general nonconic format: ... where P is any closed convex set, not necessarily a cone, which we call the ground-set. Although any convex problem can be transformed to conic form, such transformations are neither unique nor natural given the natural description of many problems, thereby diminishing the relevance of data-based condition number theory. Herein we extend the modern theory of condition numbers to the problem format (GPd). As a byproduct, we are able to state and prove natural extensions of many theorems from the conic-based theory of condition numbers to this broader problem format. [ABSTRACT FROM AUTHOR]

This paper is the first to consider general multiarmed bandit problems on parallel machines working at different speeds. Block allocation policies make a once-for-all allocation of bandits to machines at time zero. In this class we describe how to achieve Blackwell optimality under given conditions. The block allocation policy identified allocates the bandits with the largest guaranteed reward rates to the machines operating at greatest speed. This policy is shown to be average-reward optimal in the class of general (nonanticipative, nonidling) policies. [ABSTRACT FROM AUTHOR]

We consider the scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The objective functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs, and total weighted completion times.We obtain different scenarios, depending on the objective function of each agent, and on the structure of the processing system (single machine or shop). For each scenario, we address the complexity of various problems, namely, finding the optimal solution for one agent with a constraint on the other agent's cost function, finding single nondominated schedules (i.e., such that a better schedule for one of the two agents necessarily results in a worse schedule for the other agent), and generating all nondominated schedules. [ABSTRACT FROM AUTHOR]

The linear independence constraint qualifications (LICQ) plays an important role in the analysis of mathematical programs with complementarity constraints (MPCCs)and is a vital ingredient to convergence analyses of SQP-type or smoothing methods, cf., e.g., Fukushima and Pang (1999), Luo et al. (1996), Scholtes and Stöhr (1999), Scholtes (2001), Stöhr (2000). We will argue in this paper that LICQ is not a particularly stringent assumption for MPCCs. Our arguments are based on an extension of Jongen's (1977) genericity analysis to MPCCs. His definitions of nondegenerate critical points and regular programs extend naturally to MPCCs and his genericity results generalize straightforwardly to MPCCs in standard form. An extension is not as straightforward for MPCCs with the particular structure induced by lower-level stationarity conditions for variational inequalities or optimization problems. We show that LICQ remains a generic property for this class of MPCCs. [ABSTRACT FROM AUTHOR]

The issue of equivalence between chance-constrained programming problems (CCPP's) and Bayesian utility-maximization problems (BUMP's), and the anomalous evaluation of information in CCPP's, are re-examined in light of a recent paper by Jagannathan and the ensuing exchange between Jagannathan and LaValle. Difficulties in "explaining" value of information within the framework of chance-constrained programming are illustrated in a numerical example due to Jagannathan. [ABSTRACT FROM AUTHOR]

Planning languages and spreadsheet systems are very popular, and the number of new users is increasing dramatically. On larger computers, IFPS, System W, and FCS-EPS are among the most widely used systems; while on personal computers, Multiplan and 1-2-3 enjoy great popularity. Currently, such languages operate mainly as simulators, evaluating specific cases. In this paper, we propose methodology which is useful in designing an optimization capability for these languages. This capability permits the user to designate certain model variables as decisions, constraints, and the objective. Upper and lower limits on the decisions and constraints are also specified. The optimization interface then diagnoses the problem as linear or nonlinear, computes first partial derivatives needed by the solution algorithms, and invokes the appropriate "solver." Information regarding the optimal solution is obtained using the reporting and graphics capabilities of the planning language. Sensitivity analysis and "what if" features permit easy modification of the problem for further analysis. These ideas have been implemented in a system called IFPS/OPTIMUM, which provides an optimization capability to users of the widely-used planning language IFPS. A simple IFPS/OPTIMUM example is presented, and two applications are described. Endowing planning languages with an optimization capability promises to increase dramatically the use of optimization. There are already hundreds of thousands of users of planning languages and spreadsheet systems, most of whom are unfamiliar with optimization models or methods. Making optimization a natural extension of systems they understand and find very useful holds great promise, both for applications and for teaching optimization concepts. [ABSTRACT FROM AUTHOR]

This paper applies the test of operational meaningfulness to the many detection laws that have been formulated and used in the mathematical optimization of search, and given as generalizations of those first developed in the United States Navy during and immediately following World War II. The word "operational" is used both in the sense of practical O.R. and in that of P. W. Bridgman's well-known requirement: that in applying mathematics to the material world, the physical preconditions implied in the quantities used, the operations for measuring them, and their laws of consistency must be set forth explicitly. It is submitted that this criterion will orient O.R. work toward useful developments in the search theory and may serve to identify as such those theories that are of chief interest as developments in pure mathematics. Finally, we note that the requirement that every numerical assumption of probability distributions in a study of the outside world must be based on objective evidence is perfectly consistent with the "subjective" conception of probability, viz., that its meaning is apprehended intuitively--the former measures what the latter defines. [ABSTRACT FROM AUTHOR]

The problem considered in this paper is to find a layout of a given number of identical facilities so that the total (or average) rectilinear distance between facilities is minimized. The potential locations for the facilities are lattice points in the plane, which are points whose coordinates are integers. A set of geometric properties and necessary conditions for an optimal layout configuration is derived. Based on a symmetry assumption, an implicit enumeration procedure is developed that will yield all optimal configurations together with the least total distance between facilities. [ABSTRACT FROM AUTHOR]

We consider a general parallel server system model with multiple customer classes and several flexible multiserver pools, in the many-server asymptotic regime where the input rates and server pool sizes are scaled up linearly to infinity. Service of a customer brings a constant reward, which depends on its class. The objective is to maximize the long-run reward rate. Our primary focus is on overloaded systems. Unlike in the case when the system is not overloaded, where the main decision is how to allocate resources to incoming customers, in this case it is also crucial to determine which customers will be admitted to the system. We propose a real-time, parsimonious, robust routing policy, SHADOW-RM, which does not require the knowledge of customer input rates and does not solve any optimization problem explicitly, and we prove its asymptotic optimality. Then, by combining SHADOW-RM with another policy, SHADOW-LB, proposed in our previous work for systems that are not overloaded, we suggest policy SHADOW-TANDEM, which automatically and seamlessly detects overload and reduces to one of the schemes, SHADOW-RM or SHADOW-LB, accordingly. Extensive simulations demonstrate a remarkably good performance of proposed policies. [ABSTRACT FROM AUTHOR]

The paper studies the problem of determining the measurements of a given number of sizes of apparel so as to maximize expected sales or minimize an index of discomfort. It develops general necessary conditions for optimization in one control body dimension and calculates optimal sizes for the special case where the population distribution is normal. [ABSTRACT FROM AUTHOR]

The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications (including triangulation of input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences). In a former paper, we have investigated the facet structure of the 0/1-polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular, we could triangulate all input-output matrices, of size up to 60 x 60, available to us within acceptable time bounds. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for solving the assignment problem. The algorithm is based on a scheme of relaxing the given problem into a series of simple network flow (transportation) problems for each of which an optimal solution can be easily obtained The algorithm is thus seen to be able to take advantage of the nice properties in both the primal and the dual approaches for the assignment problem. The computational bound for the algorithm is shown to be O(n[sup 3]) and the average computation time is better than most of the specialized assignment algorithms. [ABSTRACT FROM AUTHOR]

This paper generalizes the problems of optimal selection considered by Roth, Kadane and DeGroot by allowing a set of J items to be chosen by two decision makers, the first of whom has A challenges and the second has B challenges The two decision makers each have an opportunity to challenge each item before it is accepted, in some arbitrary fixed order. We assume that the decision makers know the utility function of the other side as well as their own over sets of J items, and that they know the subjective distribution, assigned by the other side, of characteristics of potential items that will be observed, as well as their own. Under these conditions the other side's response to each potential item can be predicted with certainty, and backward reduction defines an optimal strategy. We study an important special case we call regular, and show that it is never disadvantageous to go first in the regular case. The use of peremptory challenges in jury trials motivates our model. The basic model in which jurors are challenged one at a time is extended to a more general class of problems that includes the group system and the struck jury system. [ABSTRACT FROM AUTHOR]

A new strategy is presented for large-scale optimization. The BOXSTEP method creates an algorithmic continuum between feasible-directions methods and cutting-plane methods. Several specific applications are described and computational results are reported. [ABSTRACT FROM AUTHOR]

When scheduling n jobs on in identical machines in parallel, two performance criteria are of particular interest: the makespan (the completion time of the last job) and the flowtime (the sum of the completion times of all n jobs). Whereas minimizing makespan is NP-hard, many schedules minimize flowtime, and they are easy to characterize. This paper considers the problem of minimizing the makespan among flowtime-optimal schedules. Heuristics have appeared in the literature that result in flowtime-optimal schedules with makespans which are always less than or equal to 5/4 times the minimum flowtime-optimal makespan. In this note, we present new heuristics for this problem, one of which yields a worst-case bound of 28/27 for the two-machine case. The new heuristics have a running time of O(n log n). Extensions are discussed for general in. [ABSTRACT FROM AUTHOR]

Over the past decade, optimization models have been widely used to help select bond portfolios. Several different formulations are popular. The purposes of this paper are to clarify the basic structures of the models, to explain the relationships among them, and to assess their strengths and weaknesses. [ABSTRACT FROM AUTHOR]

One measure of the effectiveness of institutional trauma and burn management based on collected patient data involves the computation of a standard normal AZ statistic. A potential weakness of the measure arises from incomplete patient data. In this paper, we apply methods of fractional programming and global optimization to efficiently calculate bounds on the computed effectiveness of an institution. The measure of effectiveness (i.e., the trauma outcome function) is briefly described, the optimization problems associated with its upper and lower bounds are defined and characterized, and appropriate solution procedures are developed. We solve an example problem to illustrate the method. [ABSTRACT FROM AUTHOR]

A fundamental issue in the use of optimization models is the tradeoff between the level of detail and the ease of using and solving the model. Aggregation and disaggregation techniques have proven to be valuable tools for manipulating data and determining the appropriate policies to employ for this tradeoff. Furthermore, aggregation and disaggregation techniques offer promise for solving large-scale optimization models, supply a set of promising methodologies for studying the underlying structure of both univariate and multivariate data sets, and provide a set of tools for manipulating data for different levels of decision makers. In this paper, we develop a general framework for aggreation and disaggregation methodology, survey previous work regarding aggregation and disaggregation techniques for optimization problems, illuminate the appropriate role of aggregation and disaggregation methodology for optimization applications, and propose future research directions. [ABSTRACT FROM AUTHOR]

Consider a complete graph G = (K, E) in which each node is present with probability p,. We are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. We introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. We consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. We discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. We characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, we use the TSP as an example to find practical solutions based on ideas of local optimality. [ABSTRACT FROM AUTHOR]

Dinkelbach's algorithm [2] solving the parametric equivalent of a fractional program is investigated. It is shown that the algorithm converges superlinearly and often (locally) quadratically. A priori and a posteriori error estimates are derived. Using those estimates and duality as introduced in Part I, a revised version of the algorithm is proposed. In addition, a similar algorithm is presented where, in contrast to Dinkelbach's procedure, the rate of convergence is still controllable. Error estimates are derived also for this algorithm. [ABSTRACT FROM AUTHOR]

Studies of the convergence of algorithms often revolve around the existence of a function with respect to which monotonic descent is required. In this paper, we show that under relatively lenient conditions, "stage-dependent descent" (not necessarily monotonic) is sufficient to guarantee convergence. This development also provides the impetus to examine optimization algorithms. We show that one of the important avenues in the study of convergence, namely, the theory of epi-convergence imposes stronger conditions than are necessary to establish the convergence of an optimization algorithm. Working from a relaxation of epi-convergence, we introduce the notion of ∂-compatibility, and prove several results that permit relaxations of conditions imposed by previous approaches to algorithmic convergence. Finally, to illustrate the usefulness of the concepts, we combine stage-dependent descent with results derivable from ∂-compatibility to provide a basis for the convergence of a general algorithmic statement that might be used for stochastic and nondifferentiable optimization. [ABSTRACT FROM AUTHOR]

One of the central trends in the optimization community over the past several years has been the steady improvement of general-purpose solvers. A logical next step in this evolution is to combine mixed-integer linear programming, constraint programming, and global optimization in a single system. Recent research in the area of integrated problem solving suggests that the right combination of different technologies can simplify modeling and speed up computation substantially. Nevertheless, integration often requires special-purpose coding, which is time consuming and error prone. We present a general-purpose solver, SIMPL, that allows its user to replicate (and sometimes improve on) the results of custom implementations with concise models written in a high-level language. We apply SIMPL to production planning, product configuration, machine scheduling, and truss structure design problems on which customized integrated methods have shown significant computational advantage. We obtain results that either match or surpass the original codes at a fraction of the implementation effort. [ABSTRACT FROM AUTHOR]

We present a new deflected subgradient scheme for generating good quality dual solutions for linear programming (LP) problems and utilize this within the context of large-scale airline crew planning problems that arise inpractice. The motivationfor the development of this method came from the failure of a black-boxtype approach implemented at United Airlines for solving such problems using column generation in concert with a commercial LP solver, where the software was observed to stall while yet remote from optimality. We identify a phenomenon called dual noise to explain this stalling behavior and present an analysis of the desirable properties of dual solutions in this context. The proposed deflected subgradient approach has been embedded within the crew pairing solver at United Airlines and tested using historical data sets. Our computational experience suggests a strong correlation between the dual noise phenomenon and the quality of the final solution produced, as well as with the accompanying algorithmic performance. Although we observed that our deflected subgradient scheme yielded anaverage speed-up factor of 10 for the columngen erationscheme over the commercial solver, the average reductionin the optimality gap over the same number of iterations was better by a factor of 26, along with anaverage reduction in the dual noise by a factor of 30. The results from the column generation implementation suggest that significant benefits can be obtained by using the deflected subgradient-based scheme instead of a black-box-type or standard solver approach to solve the intermediate linear programs that arise with in the columngen erationscheme. [ABSTRACT FROM AUTHOR]

We consider a class of the subset selection problem in ranking and selection. The objective is to identify the top m out of k designs based on simulated output. Traditional procedures are conservative and inefficient. Using the optimal computing budget allocation framework, we formulate the problem as that of maximizing the probability of correctly selecting all of the top-m designs subject to a constraint on the total number of samples available. For an approximation of this correct selection probability, we derive an asymptotically optimal allocation and propose an easy-to-implement heuristic sequential allocation procedure. Numerical experiments indicate that the resulting allocations are superior to other methods in the literature that we tested, and the relative efficiency increases for larger problems. In addition, preliminary numerical results indicate that the proposed new procedure has the potential to enhance computational efficiency for simulation optimization. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for integrated logistics problems that combine elements of facility location and transport network design. We first study the problem where opening facilities incurs opening costs and transportation from the clients to the facilities incurs buy-at-bulk costs, and provide a combinatorial approximation algorithm. We also show that the integer-programming formulation of this problem has small integrality gap. We extend the model to the version when there is a bound on the number of facilities that may be opened. [ABSTRACT FROM AUTHOR]

We consider a power portfolio optimization model that is intended as a decision aid for scheduling and hedging (DASH) in the wholesale power market. Our multiscale model integrates the unit commitment model with financial decision making by including the forwards and spot market activity within the scheduling decision model. The methodology is based on a multiscale stochastic programming model that selects portfolio positions that perform well on a variety of scenarios generated through statistical modeling and optimization. When compared with several commonly used fixed-mix policies, our experiments demonstrate that the DASH model provides significant advantages. [ABSTRACT FROM AUTHOR]

We investigate network design under volatile conditions of link failures and trafic overload. Our model is a nonsimultaneous 2-commodity problem. We characterize the feasible solutions and, using this characterization, we reduce the size of the linear program. For 0/1 requirements we present a closed fractional optimal solution, a closed integer-capacities optimal solution, and 7/6-approximation for the case in which integer 2-commodity flows are required. [ABSTRACT FROM AUTHOR]

Investigates the repair/replacement problem for a single unit system with random repair cost. When the unit fails, the repair cost is observed and a decision is made whether to replace the unit or repair it. Although the model in this article is formulated as a model of a single unit system, it can also be used as a suitable representation of a complex, multi-unit repairable system. If only a small part of the system is repaired or replaced upon failure, this would not affect considerably the failure rate and the minimal repair assumption is acceptable. For such systems, the repair cost typically depends on the operating age and may depend also on the number of failures since the last replacement or overhaul of the system.

The article investigates the complexity of problems concerned with partially-observable Markov decision processes which are run for a finite number of steps under small policies. Partially-observable Markov decision processes (POMDP) model sequential decision-making when outcomes are uncertain and the state of the system cannot be completely observed. The optimal performance of a POMDP under any small policy of a given size can be calculated using a binary search method. This involves creating a series of new POMDPs from the given one by appending an initial state such that any action from that state yields a positive or negative reward equal to the shift from the last value considered. All classes contain polynomial time and are contained in polynomial space. Other classes that the authors mention are nondeterministic logarithmic space and probabilistic logarithmic space, which are defined like NP and complexity class PP, but the polynomial time bound is replaced by a logarithmic space bound.

When the Nelder-Mead method is used to optimize the expected response of a stochastic system (e.g., an output of a discrete-event simulation model), the simplex-resizing steps of the method introduce risks of inappropriate termination. We give analytical and empirical results describing the performance of Nelder-Mead when it is applied to a response function that incorporates an additive white-noise error, and we use these results to develop new modifications of Nelder-Mead that yield improved estimates of the optimal expected response. Compared to Nelder-Mead, the best performance was obtained by a modified method, RS + S9, in which (a) the best point in the simplex is reevaluated at each shrink, step and (b) the simplex is reintroduced by 10% (rather than 50%) at each shrink step. In a suite of 18 test problems that were adapted from the MINPACK collection of NETLIB, the expected response at the estimated optimal point, at an average cost of three times as many function evaluations. Two well-known existing modifications for stochastic responses, the (n + 3)-rule and the next-to-worst rule, were found to be inferior to the new modification RS + S9. [ABSTRACT FROM AUTHOR]

We present a new algorithm for the optimal solution of the 0-1 Knapsack problem, which is particularly effective for large-size problems. The algorithm is based on determination of an appropriate small subset of items and the solution of the corresponding "core problem": from this we derive a heuristic solution for the original problem which, with high probability, can be proved to be optimal. The algorithm incorporates a new method of computation of upper bounds and efficient implementations of reduction procedures. The corresponding Fortran code is available. We report computational experiments on small-size and large-size random problems, comparing the proposed code with all those available in the literature. [ABSTRACT FROM AUTHOR]

Recently Kornbluth and Steuer have developed a simplex-based algorithm for finding all weakly-efficient vertices of an augmented feasible region of a multiple objective linear fractional programming problem. As part of this algorithm, they presented a method for detecting certain weakly-efficient vertices called break points. In this note we show that the procedure used by Kornbluth and Steuer in this method for computing the numbers needed to find these break points may sometimes fail. We also propose a fail-safe method for computing these numbers and give some computational results with this method. [ABSTRACT FROM AUTHOR]

A school may be viewed as an enterprise in which the professional staff provide the operating conditions for converting quantifiable resources or inputs into pupil learning (outputs). The resources are determined by budgets, teacher assignments, and student assignmerits while learning is determined by various outputs scored according to standardized tests such as the Iowa Test of Basic Skills. Following the work of Charnes, Cooper, and Rhodes [11], we use a ratio definition of efficiency that takes account of all outputs and inputs without requiring a priori specification of weights. Instead a series of mathematical programs are applied to determine "virtual multipliers" from actual data. The multipliers produce values that can be regarded as the "most favorable weights" for each school being evaluated. If the resulting optimum virtual multipliers for a given school yield an efficiency ratio of one, then that school is said to be efficient. If the ratio is less than one then that school is said to be inefficient relative to the other schools in the analysis. The ratio is also accorded operational significance--it is not merely an index number--so that the resulting values and the associated virtual multipliers make it possible to locate where improvements may be made along with their relative magnitudes. This analysis was applied to 167 elementary schools in the Houston Independent School District. Of these schools, 78 were found to be inefficiently utilizing their resources as compared to the 89 efficient schools. Based on this pilot study, an Educational Productivity Council has been formed at the University of Texas at Austin to provide an annual analysis for all of its member schools. At present 285 Texas schools in 22 districts are scheduled for participation in the annual analysis as described in this investigation. [ABSTRACT FROM AUTHOR]

We consider a single repairman who maintains a coherent system of n components. Each component works for and is repaired in random periods of time with exponential distribution independent of the behavior of other components. We try to find a policy for assignment of the repairman which maximizes the long run probability that the system functions. Although the general problem is quite complicated, highly reliable and highly unreliable systems can be solved easily by asymptotic techniques. These techniques express ergodic probabilities and expected passage times between states in power series of an asymptotic parameter when the policy employed is in a class of potentially optimal policies. As an example, the highly reliable optimal actions are obtained for the k of n system which includes both series and parallel systems. [ABSTRACT FROM AUTHOR]

The generalized linear programming algorithm allows an arbitrary mathematical programming minimization problem to be analyzed as a sequence of linear programming approximations. Under fairly general assumptions, it is demonstrated that any limit point of the sequence of optimal linear programming dual prices produced by the algorithm is optimal in a concave maximization problem that is dual to the arbitrary primal problem. This result holds even if the generalized linear programming problem does not solve the primal problem. The result is a consequence of the equivalence that exists between the operations of convexification and dualization of a primal problem. The exact mathematical nature of this equivalence is given. [ABSTRACT FROM AUTHOR]

Charnes [2] has established the equivalence between the linear programming and the constrained rectangular game. An attempt is made here to establish a similar equivalence between the linear programming and a more general class of decision problems which may be referred to as the "minimax (or maximin) programming problems." This class includes as its special cases the constrained rectangular games and the goal programming [3]. The generalized equivalence theorems are shown to imply the theorem due to Goldman and Tucker [5] on the mutually dual linear programming problems. A brief proof of the existence of a saddle point to the constrained rectangular game is also given as a corollary to these theorems. [ABSTRACT FROM AUTHOR]

Given a concave program, consider its optimal objective value as a function of the right-hand side. The behavior of this optimal response function reflects the sensitivity of the objective value to changes in the right-hand side. A scheme involving the optimization of a penalty function is developed for determining the value and gradient of the optimal response function at points within a region of interest. This scheme is then applied to a simple example to illustrate its potential usefulness. [ABSTRACT FROM AUTHOR]