Search

We review the past year and this Editor-in-Chief's editorship for the last six annual volumes in this issue's "From the Editors" column, which is coauthored with Managing Editor Kelly M. Kophazi, and then we preview this issue's research articles. Our first article, by Dorota Kurowicka is on "Conditionalization of Copula-Based Models." The next three papers address groups or teams. First is "A Note on a Group Preference Axiomatization with Cardinal Utility," by Luis C. Dias and Paula Sarabando. Next, Andrew Samuel and Seth D. Guikema address "Resource Allocation for Homeland Defense: Dealing with the Team Effect." Then, Arthur Carvalho and Kate Larson present a way for "Sharing Rewards Among Strangers Based on Peer Evaluations." Finally, Jeffrey M. Keisler and Patrick S. Noonan provide guidance for decision analysis practice in "Communicating Analytic Results: A Tutorial for Decision Consultants." [ABSTRACT FROM AUTHOR]

We give counterexamples for some statements of Borwein and sufficient conditions for the validity of these. [ABSTRACT FROM AUTHOR]

In Weighted Scoring Rules and Convex Risk Measures, Dr. Zachary J. Smith and Prof. J. Eric Bickel (both at the University of Texas at Austin) present a general connection between weighted proper scoring rules and investment decisions involving the minimization of a convex risk measure. Weighted scoring rules are quantitative tools for evaluating the accuracy of probabilistic forecasts relative to a baseline distribution. In their paper, the authors demonstrate that the relationship between convex risk measures and weighted scoring rules relates closely with previous economic characterizations of weighted scores based on expected utility maximization. As illustrative examples, the authors study two families of weighted scoring rules based on phi-divergences (generalizations of the Weighted Power and Weighted Pseudospherical Scoring rules) along with their corresponding risk measures. The paper will be of particular interest to the decision analysis and mathematical finance communities as well as those interested in the elicitation and evaluation of subjective probabilistic forecasts. This paper establishes a new relationship between proper scoring rules and convex risk measures. Specifically, we demonstrate that the entropy function associated with any weighted scoring rule is equal to the maximum value of an optimization problem where an investor maximizes a concave certainty equivalent (the negation of a convex risk measure). Using this connection, we construct two classes of proper weighted scoring rules with associated entropy functions based on ϕ-divergences. These rules are generalizations of the weighted power and weighted pseudospherical rules. [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [ABSTRACT FROM AUTHOR]

In this paper, we provide a flexible framework allowing for a unified study of time consistency of risk measures and performance measures (also known as acceptability indices). The proposed framework not only integrates existing forms of time consistency, but also provides a comprehensive toolbox for analysis and synthesis of the concept of time consistency in decision making. In particular, it allows for in-depth comparative analysis of (most of) the existing types of time consistency--a feat that has not been possible before and, which is done in the companion paper by the authors. In our approach, the time consistency is studied for a large class of maps that are postulated to satisfy only two properties--monotonicity and locality. We call these maps LM-measures. The time consistency is defined in terms of an update rule. The form of the update rule introduced here is novel, and is perfectly suited for developing the unifying framework that is worked out in this paper. As an illustration of the applicability of our approach, we show how to recover almost all concepts of weak time consistency by means of constructing appropriate update rules. [ABSTRACT FROM AUTHOR]

The technique of perturbation analysis has recently been introduced as an efficient way to compute parameter sensitivities for discrete event systems. Thus far, the statistical properties of perturbation analysis have been validated mainly through experiments. This paper considers, for an M/G/1 queueing system, the sensitivity of mean system time of a customer to a parameter of the arrival or service distribution. It shows analytically that (i) the steady state value of the perturbation analysis estimate of this sensitivity is unbiased, and (ii) a perturbation analysis algorithm implemented on a single sample path of the system gives asymptotically unbiased and strongly consistent estimates of this sensitivity. (No previous knowledge of peturbation analysis is assumed, so the paper also serves to introduce this technique to the unfamiliar reader.) Numerical extensions to GI/G/1 queues, and applications to optimization problems, are also illustrated. [ABSTRACT FROM AUTHOR]

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

This paper provides a mathematical and economic analysis of 'Incentives and Computing Systems for Team-Based Organizations' by A. Barua, C. H. Sophie Lee, and A. B. Whinston, which was published in Organization Science in 1995. Several points were not adequately stated in the original article and one of the key definitions is not clear, nor is it in keeping with the classical theory of production. Although the Cobb-Douglas production function is often used in the article, it does not comply with the article's definitions. The two main contributions of this paper are (1) to provide a word of caution to other readers who might try to extend Barua et al. (1995) and (2) to suggest alternative formulations and directions for future research. [ABSTRACT FROM AUTHOR]

This paper proposes a computationally efficient simulation-based optimization (SO) algorithm suitable to address large-scale generally constrained urban transportation problems. The algorithm is based on a novel metamodel formulation. We embed the metamodel within a derivative-free trust region algorithm and evaluate the performance of this SO approach considering tight computational budgets. We address a network-wide traffic signal control problem using a calibrated microscopic simulation model of evening peak period traffic of the full city of Lausanne, Switzerland, which consists of more than 600 links and 200 intersections. We control 99 signal phases of 17 intersections distributed throughout the entire network. This SO problem is a high-dimensional nonlinear constrained problem. It is considered large-scale and complex in the fields of derivative-free optimization, traffic signal optimization, and simulation-based optimization. We compare the performance of the proposed metamodel method to that of a traditional metamodel method and that of a widely used commercial signal control software. The proposed method systematically and efficiently identifies signal plans with improved average city-wide travel times. [ABSTRACT FROM AUTHOR]

This paper investigates equilibrium R&D investment strategies of firms endowed with different innovation potentials. To address this issue, this paper permits two stages of innovation and develops a simple stochastic game model involving two firms. It is shown that in equilibrium, a leader in the multiple stage innovation game invests more than a follower; firms compete more vigorously in the later stages of innovation than in the earlier stages; and a follower is more likely to choose a riskier innovation path than one requiring, on average, equivalent effort. It provides an explanation of how the expected benefits, the cost of R&D, and interactions between competing firms combine to determine dynamic R&D strategies over time. [ABSTRACT FROM AUTHOR]

This paper presents a class of utility functions (class A[sub ∞]) that contains all of the utility functions commonly used for mathematical modeling: the class consisting of those utility functions whose derivatives alternate in sign. A simple representation via mixtures of exponential utilities is provided for this class which is both mathematically convenient and conducive to functional operations. A connection with Laplace transforms and the resultant implications for preference relations, aggregation and utility assessment are discussed. [ABSTRACT FROM AUTHOR]

Queueing systems with interruptions serve as models for a variety of situations occurring in every day life. Usually, for each type of interruption, a separate queueing analysis is required. In this paper we present a single queueing model which can be used to analyze many such systems. The model is in the form of an approximation that is based upon several parameters, which reflect the particular queueing system under consideration. Applications to queueing systems with priorities and breakdowns are given in the paper. [ABSTRACT FROM AUTHOR]

This paper is based on the notion of discriminatory power of a pattern classifier acting over a feature space. Discriminant functions are normally used to trace out regions of the feature space corresponding to specific pattern classes. Indeterminate cases occur whenever a pattern lies on a class boundary. The number of occurrences of such indeterminacies measures the relative discriminatory power of a family of discriminant functions. In this paper these concepts are applied to majority voting decisions. It is first shown how regular majority voting leads to discriminant functions with insufficient discriminatory power whenever intransitive social ordering occurs. An (improved) family of discriminant functions is proposed to resolve such cases. [ABSTRACT FROM AUTHOR]

Intensive care unit (ICU) beds are valuable resources that are typically in short supply and therefore their effective and efficient use is essential particularly during periods when patient demand is high. In "Allocation of Intensive Care Unit Beds in Periods of High Demand," H. Ouyang, N.T. Argon, and S. Ziya provide insights into what kind of patient prioritization decisions are likely to improve patient health outcomes by analyzing stylized mathematical formulations that capture the fundamental trade-off involved in ICU bed management. They also propose simple policies that are likely to perform well in practice and test them with a simulation study. Findings suggest that even simple policies are likely to bring significant benefits, although more work is needed to investigate whether there could be benefits to using methods that aim to capture patient health condition in a manner that is more precise than assumed in the paper. The objective of this paper is to use mathematical modeling and analysis to develop insights into and policies for making bed allocation decisions in an intensive care unit (ICU) of a hospital during periods when patient demand is high. We first develop a stylized mathematical model in which patients' health conditions change over time according to a Markov chain. In this model, each patient is in one of two possible health stages, one representing the critical and the other representing the highly critical health stage. The ICU has limited bed availability and therefore when a patient arrives and no beds are available, a decision needs to be made as to whether the patient should be admitted to the ICU and if so, which patient in the ICU should be transferred to the general ward. With the objective of minimizing the long-run average mortality rate, we provide analytical characterizations of the optimal policy under certain conditions. Then, based on these analytical results, we propose heuristic methods, which can be used under assumptions that are more general than what is assumed for the mathematical model. Finally, we demonstrate that the proposed heuristic methods work well by a simulation study, which relaxes some of the restrictive assumptions of the mathematical model by considering a more complex transition structure for patient health and allowing for patients to be possibly queued for admission to the ICU and readmitted from the general ward after they are discharged. [ABSTRACT FROM AUTHOR]

This paper considers the problem of optimally terminating a number of stochastic processes when the time varying random rewards have distributions belonging to an exponential family with an unknown parameter. The problem is formulated as a Bayesian adaptive control model with the objective of minimizing the difference between the expected reward and the optimal reward when the parameter is known. The paper establishes an asymptotic lower bound on this difference and constructs policies based on a Kullback-Leibler index that obtains this lower bound. The results are applied to models of tree harvesting and destructive testing. A simulation study shows that these policies are efficient when the number of processes is large. [ABSTRACT FROM AUTHOR]

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases. [ABSTRACT FROM AUTHOR]

Recommendation stability measures the extent to which a recommendation algorithm provides predictions that are consistent with each other. Several approaches have been proposed in prior work to defining, measuring, and improving the stability of recommendation algorithms. Previous studies have focused primarily on understanding and evaluating recommendation stability in prediction-oriented settings, i.e., recommendation settings where it is crucial to provide the precise prediction of a user's preference rating for an item. However, the research literature has been largely silent on the topic of recommendation stability in other important types of settings, such as classification-oriented (i.e., where it is important to accurately classify the item as relevant versus irrelevant, without having to quantify the user's preference precisely), ranking-oriented (i.e., where it is important to provide accurate relative ranking of items to users), or top-K oriented (i.e., where it is important to suggest K items that are most appealing to the user). Therefore, this paper builds on prior work by generalizing the notion of stability to a broader set of recommendation settings and developing corresponding stability metrics. The paper also provides a comprehensive empirical analysis of classification, ranking, and top-K stability performance of popular recommender algorithms on real-world rating data sets under a variety of settings. [ABSTRACT FROM AUTHOR]

This paper discusses the application of the likelihood ratio gradient estimator to simulations of large Markovian models of highly dependable systems. Extensive empirical work, as well as some mathematical analysis of small dependability models, suggests that (in this model setting) the gradient estimators are not significantly more noisy than the estimates of the performance measures themselves. The paper also discusses implementation issues associated with likelihood ratio gradient estimation, as well as some theoretical complements associated with application of the technique to continuous-time Markov chains. [ABSTRACT FROM AUTHOR]

This paper describes a simple set of coordination structures that model certain kinds of information processing involved in organizations and markets. Four generic coordination structures are defined: product hierarchies, functional hierarchies, centralized markets, and decentralized markets. Then tradeoffs among these structures are analyzed in terms of production costs, coordination costs, and vulnerability costs. This model is unusual in that it includes detailed definitions of the structures at a micro-level and mathematical derivations of comparisons among them at a macro-level. In the final section of the paper, several connections are made between these formal results and previous work on organizational design. [ABSTRACT FROM AUTHOR]

The paradox involved in sequences of Prisoner's Dilemma games is due to the fact that game theoretic definitions of optimality rarely coincide with any natural meaning of the word. Decision makers should incorporate their beliefs and experience into any mathematical analysis of the games. Once this has been done, via subjective probabilites, use of the cooperative move in iterated Prisoner's Dilemma games can often be justified. The paper provides a simple algorithm for determining an optimal strategy, once the decision maker's subjective probabilities have been specified. [ABSTRACT FROM AUTHOR]

This paper extends recent work on finding the stochastic queue median (SQM) on a network. The SQM is the optimal location of a single mobile server, when idle, who travels to customers in response to requests for service. Customer demands are limited to the nodes of the network and their requests for service arrive according to a time homogeneous Poisson process, independently from each node. When a service request finds the server busy with a previous customer, it is entered into an M/G/1 queue that is depleted in a first-in, first-out (FIFO) manner. The SQM is the point on the network at which the sum of mean queueing delay and mean travel time is minimized. In this paper the transportation network is restricted to be a tree. By discovering and exploiting convex properties of the objective function and related functions, an efficient finite-step algorithm is found for locating the SQM on a tree. [ABSTRACT FROM AUTHOR]

It is well known that all betting systems applied to independent, repeated, and identically distributed trials will result in the same expected gain per average unit wagered as that which applies to a single trial. This paper develops the asymptotic and paradoxical manner in which that constant win rate is maintained for optimal proportional betting according to the Kelly criterion. The appropriateness of using this traditional measure of win rate for proportional betting is contrasted with that of various alternatives. [ABSTRACT FROM AUTHOR]

In a companion paper we developed a unified scheme for using poststratified sampling and control variables to improve the efficiency of regenerative queueing simulations. We adapted these variance reduction techniques to the estimation methods of replication analysis and regenerative analysis by exploiting the asymptotic joint normality of certain standardized concomitant variables that are defined on each input process sampled during a queueing simulation. In this paper we present an experimental evaluation of the reductions in point-estimator variance and confidence-interval width that can be achieved with each procedure in several closed and mixed machine-repair systems. For the analytically tractable model, nominal and actual confidence-interval coverage probabilities are also compared. Poststratification generally produced variance reductions ranging from 10% to 40% and confidence-interval reductions between 1% and 20%. The control-variates schemes yielded variance reductions ranging from 20% to 90% and confidence-interval reductions between 10% and 70%. In some instances where small sample sizes were used, the poststratification schemes produced confidence-interval width increases between 1% and 10%. With a small number of regenerative cycles, some loss of confidence-interval coverage was observed with both poststratified and controlled regenerative analysis. When larger sample sizes were used, all of the estimation schemes yielded fairly consistent efficiency gains. [ABSTRACT FROM AUTHOR]

This paper is a comprehensive study of methods for assessing unidimensional expected utility functions. The paper describes the utility assessment process in decision analysis and then reviews problem formulation, sources of bias in preference judgments, and the analysis of risk attitudes. Two dozen utility assessment methods of which half appear for the first time are critically examined. These methods are grouped into preference comparison methods, probability equivalence methods, value equivalence methods, certainty equivalence methods, hybrid methods, paired-gamble methods, and other approaches. The paper emphasizes the nature of judgmental biases in comparing different assessment procedures. Since most multiattribute utility functions are decomposed into single-attribute functions, this study should facilitate such applications. The paper concludes with several directions for further developmental, empirical, and applied research. [ABSTRACT FROM AUTHOR]

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]

The subject of this paper is a classification and discussion of algorithms for solution of nonlinear pure integer programming problems. The survey is organized by characterizing the mathematical form of the nonlinear optimization problems addressed by the various algorithms. If any method can be used without changes to solve mixed integer nonlinear programming problems that fact is mentioned in the description of the algorithm. However algorithms which must be applied only to mixed integer problems are not surveyed. [ABSTRACT FROM AUTHOR]

A question that recurs in the decision analysis literature is: What is the value of additional data gathering? We use a very general definition of data that includes subjective probability distributions provided by experts, calculations from models, and traditional experimental data. General expressions for the expected value of data have little practical use because they involve probability distributions whose arguments are themselves probability distributions. The traditional approach to alleviate the problem of dimensionality is to introduce arbitrary parameterization of the data. This paper shows that for an interesting class of decision problems, arbitrary parameterization is not necessary. For the class of decision problems in which the value function over outcomes is a quadratic function of the state and decision variables, the value of data depends on the state variables only through the prior covariances of the posterior means. To use this result in the calculation of the approximate value of data for practical problems, it is necessary to simplify the value function. The paper suggests simplifying the value function by expanding it in a Taylor series with respect to the state and decision variables. The resulting expressions for the approximate value of information should be useful and inexpensive to evaluate for practical decision problems. [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]

A newsvendor game allows the players to collaborate on inventory pooling and share the resulting total cost. There are several possible ways to allocate the cost. Previous studies have focused on the core of the game. It is known that the core of the newsvendor game is nonempty, and one can use duality theory in stochastic programming to construct an allocation—referred to as the dual-based allocation—belonging to the core. Yet, an allocation that lies in the core does not necessarily guarantee the unhindered formation of a coalition, as some existing members' allocated costs may increase when new members are added in the process. In this work, we use the concept of population monotonic allocation scheme (PMAS), which requires the cost allocated to every member of a coalition to decrease as the coalition grows, to study allocation schemes in a growing population. We show that when the demands faced by the newsvendors are independent, log-concavity of their distributions is sufficient to guarantee the existence of a PMAS. Specifically, for continuous demands, log-concavity ensures that the game is convex, which in turn implies a PMAS exists. We also show that under the same condition the dual-based allocation scheme is a PMAS. For discrete and log-concave demands, however, the game may no longer be convex, but we manage to show that, even so, the dual-based allocation scheme is a PMAS. When the demands are dependent, the game is in general not convex. We derive a sufficient condition based on the dependence structure, measured by the copula, to ensure that the dual-based allocation scheme is still a PMAS. We also include an example of a game with no PMAS. This paper was accepted by Yinyu Ye, optimization. The online appendix is available at https://doi.org/10.1287/mnsc.2018.3053. [ABSTRACT FROM AUTHOR]

In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. We present bounds on the ratio of optimal value of the LP relaxation after adding cuts and the optimal value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of single-scenario cuts for two-stage stochastic MILPs. [ABSTRACT FROM AUTHOR]

In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time. At the instant that a server becomes free, it selects the waiting customer with the highest accumulated priority, provided that the queue is nonempty. He developed a recursion for calculating the expected waiting time for each class. In 2014, Stanford, Taylor, and Ziedins reconsidered this queue, which they termed the accumulating priority queue (APQ), and derived the waiting time distribution for each class. Kleinrock and Finkelstein in 1967 also studied an accumulating priority system in which customers' priorities increase as a power-law function of their waiting time. They established that it is possible to associate a particular linear APQ with such a power-law APQ, so that the expected waiting times of customers from all classes are preserved. In this paper, we extend their analysis to characterise the class of nonlinear APQs for which an equivalent linear APQ can be found, in the sense that, for identical sample paths of the arrival and service processes, the ordering of all customers is identical at all times in both the linear and nonlinear systems. [ABSTRACT FROM AUTHOR]

We discuss two possible parallel strategies for randomized restart algorithms. Given a set of available algorithms, one can either choose the best performing algorithm and run its multiple copies in parallel (single algorithm portfolio) or choose some subset of algorithms to run in parallel (mixed algorithm portfolio). It has been previously shown that the latter approach may provide better results computationally. In this paper, we provide theoretical investigation of the extent of such improvement generalizing some of the known results from the literature. In particular, we estimate the computational value of mixing randomized restart algorithms with different properties. Under some mild assumptions, we prove that in the best case the mixed algorithm portfolio may perform approximately up to 1.58 times faster than the best single algorithm portfolio. We also show that the obtained upper bound is sharp. Furthermore, the constructive proof of the main result allows us to characterize algorithms that are likely to form an effective mixed algorithm portfolio. [ABSTRACT FROM AUTHOR]

Advances in information technology and telecommunications, together with ever-growing amounts of data, offer opportunities for transportation companies to improve the quality of the service that they provide to their customers. This paper compares two methods motivated by the opportunity that the availability of data and technology gives to improve on current practice. In particular, the two solution approaches are explored in the context of a dynamic and stochastic routing problem in which a single, uncapacitated vehicle serves a set of known customers locations. One approach, sample-scenario planning, offers the potential for higher-quality solutions, but at the expense of greater computational effort. On the other hand, anticipatory insertion offers reduced computation and increased managerial ease, but with the potential for reduced solution quality due to restrictions on solution structure. Our results show that anticipatory insertion can often match the quality of sample-scenario planning, particularly when the degree of dynamism is low. [ABSTRACT FROM AUTHOR]

This paper presents an data type (ADT) for producing higher-dimensional rectilinear packings using constructive methods, the Skyline ADT. Furthermore, a novel method and several approaches from the literature are presented in the form of concrete implementations of the presented ADT. Formal definitions of two three-dimensional packing problems are given, the concept of gaps is explained, and the polynomial growth worst-case behaviour of gaps is shown. The complexity of both the best-fit algorithm and implementations of the ADT are presented, and comparative runtime speeds are analysed over a range of data sets from the literature. [ABSTRACT FROM AUTHOR]

This paper considers the two-dimensional strip-packing problem (2SP) in which a set of rectangular items have to be orthogonally packed, without overlapping, into a strip of a given width and infinite height by minimizing the overall height of the packing. The 2SP is NP-hard in the strong sense and finds many practical applications. We propose reduction procedures, lower and upper bounds, and an exact algorithm for the 2SP. The new lower bounds are both combinatorial bounds and bounds derived from different relaxations of mathematical formulations of the 2SP. The new upper bounds are obtained by constructive heuristics based on different strategies to place the items into the strip. The new exact method is based on a branch-and-bound approach. Computational results on different sets of test problems derived from the literature show the effectiveness of the new lower and upper bounds and of the new exact algorithm. [ABSTRACT FROM AUTHOR]

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n=53. [ABSTRACT FROM AUTHOR]

This paper considers a dynamic and stochastic routing problem in which information about customer locations and probabilistic information about future service requests are used to maximize the expected number of customers served by a single uncapacitated vehicle. The problem is modeled as a Markov decision process, and analytical results on the structure of the optimal policy are derived. For the case of a single dynamic customer, we completely characterize the optimal policy. Using the analytical results, we propose a real-time heuristic and demonstrate its effectiveness compared with a series of other intuitively appealing heuristics. We also use computational tests to determine the heuristic value of knowing both customer locations and probabilistic information about future service requests. [ABSTRACT FROM AUTHOR]

This paper describes how static task-scheduling methods using stochastic search techniques can be applied to digital systems that are composed entirely of reconfigurable hardware. Such reconfigurable hardware is characterized by the property that its low-level logical functionality is not determined at the time of manufacture, but rather that this functionality becomes set only shortly before or during the invocation of the targeted application. The purpose of this paper is to introduce the basic framework for applying static scheduling theory to arbitrarily-structured task systems targeted to be implemented in prefabricated resource-constrained reconfigurable hardware. The paper also describes initial solutions to this heterogeneous task-scheduling problem that combine a distributed list-based scheduling technique with three probabilistic search strategies. The techniques introduced produce detailed task scheduling and high-level hardware configuration information that can serve as inputs to the software and reconfigurable hardware design automation tools used in the hardware/software codesign process. [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]

In this paper, we present a branch-and-price method to solve special structured multistage stochastic integer programming problems. We validate our method on two different versions of a multistage stochastic batch-sizing problem (SBSP). One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications. [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]

In a recent paper on semidefinite linear complementarity problems, Gowda and Song (2000) introduced and studied the P-property, P[sub 2]-property, GUS-property, and strong monotonicity property for linear transformation L: S[sup n] → S[sup n], where S[sup n] is the space of all symmetric and real n x n matrices. In an attempt to characterize the P[sub 2]-property, they raised the following two questions: (i) Does the strong monotonicity imply the P[sub 2]-property? (ii) Does the GUS-property imply the P[sub 2]-property? In this paper, we show that the strong monotonicity property implies the P[sub 2]-property for any linear transformation and describe an equivalence between these two properties for Lyapunov and other transformations. We show by means of an example that the GUS-property need not imply the P[sub 2]-property, even for Lyapunov transformations. [ABSTRACT FROM AUTHOR]

In this paper we examine a number of different definitions of strategic stability and the relations among them. In particular, we show that the stability requirement given by Hillas (1990) is weaker than the requirements involved in the various definitions of stability in Mertens' reformulation of stability (Mertens 1989,1991). To this end, we introduce a new definition of stability and show that it is equivalent to (a variant of ) the definition given by Hillas (1990). We also use the equivalence of our new definition with the definition of Hillas to provide correct proofs of some of the results that were originally claimed (and incorrectly 'proved') in Hillas (1990). [ABSTRACT FROM AUTHOR]

In this paper we investigate the properties of multimodular functions. In doing so we give elementary proofs for properties already established by Hajek and we generalize some of his results. In particular, we extend the relation between convexity and multimodularity to some convex subsets of Zm. We also obtain general optimization results for average costs related lo a sequence of multimodular functions rather than to a single function. Under this general context, we show that the expected average cost problem is optimized by using regular sequences. We finally illustrate the usefulness of this theory in admission control into a D/D/1 queue with fixed batch arrivals, with no state information. We show that the regular policy minimizes the average queue length for the case of an infinite queue, but not for the case of a finite queue. When further adding a constraint on the losses, it is shown that a regular policy is also optimal for the finite queue case. [ABSTRACT FROM AUTHOR]

This paper describes a computer program that accepts as input a symbolic mathematical statement of an arbitrary mathematical programming problem, placing the problem into none or at least one of the categories: linear, quadratic, separable, posynomial, signomial, or convex. This categorization program is intended to reveal properties that can be exploited by special-purpose numerical computer programs--properties that might easily be overlooked because of the size of the problem, the complexity of the problem, or the limited knowledge of a novice who wishes to solve an optimization problem. The paper includes a brief demonstration of the program, a discussion of the underlying techniques, and a summary of the performance for some large problems. [ABSTRACT FROM AUTHOR]

This paper is concerned with the problem of locating n new facilities in the plane when there are m facilities already located. The objective is to minimize the weighted sum of rectilinear distances. Necessary and sufficient conditions for optimality are established. We show that the optimum locations of the new facilities are dependent on the relative orderings of old facilities along the two coordinate axes but not on the distances between them. Based on these results an algorithm is presented that requires the solution of at most m-1 minimum cut problems on networks with at most n+2 vertices. All of these results are easily extended to the same location problem on a tree graph. [ABSTRACT FROM AUTHOR]

This paper presents a unified method for obtaining duality results for concave-convex fractional programs. We obtain these results by transforming the original nonconvex programming problem into an equivalent convex program. Known results by several authors are related to each other. Moreover, we prove additional duality theorems, in particular, converse duality theorems for nondifferentiable as well as quadratic fractional programs. [ABSTRACT FROM AUTHOR]

This paper presents a simpler proof for a result of Magazine, Nemhauser, and Trotter, which states recursive necessary and sufficient conditions for the optimality of a heuristic solution for a class of knapsack problems. [ABSTRACT FROM AUTHOR]

This paper describes a finite procedure for locating a global minimum of a problem with linear objective constraints except for one nonlinear constraint, which is of the 'reverse convex' variety; that is, the direction of the inequality is the opposite of that required for a convex constraint. Budget constraints in which the cost functions are subject to economies of scale are typically of this form. An illustrative example of the procedure is provided. [ABSTRACT FROM AUTHOR]