bluuebunny/crossref_metadata_2025_split huggingface dataset:
Stochastic Gradient Methods For Simulation Optimization
Authors: Fu Michael C. 
Published: February 2011

AbstractThis article presents an overview of the two most well‐known techniques for estimating gradients from stochastic simulation: perturbation analysis and the likelihood ratio (or score function) method. The primary motivation is to derive efficient estimators for use in simulation optimization algorithms. Simple examples are used to illustrate the approaches, practical guidelines are provided for implementation, and applications in queueing, inventory, and finance are discussed.
Scenario Generation
Authors: Römisch Werner 
Published: February 2011

Abstract
Stability‐based methods for scenario generation in stochastic programming are reviewed. In particular, we briefly discuss Monte Carlo sampling, Quasi–Monte Carlo methods, quadrature rules based on sparse grids, and optimal quantization. In addition, we provide some convergence results based on recent developments in multivariate integration. The method of optimal scenario reduction and techniques for scenario trees generation are also reviewed.
Semi‐
M
arkov Processes
Authors: Serin Yasemin 
Published: February 2011

Abstract
A semi‐Markov process is a generalization of continuous‐time Markov chain, so that the sojourn times come from general distributions. In this article, after some basic definitions, some results related to the transient and limiting properties of the semi‐Markov processes are given. Some results are demonstrated with examples.
Sensitivity Analysis and Dynamic Programming
Authors: Tan Chin Hon , Hartman Joseph C. 
Published: February 2011

Abstract
The validity of any dynamic programming solution depends on the accuracy of the model and the data for a given instance. However, the parameters of the model are often uncertain and estimated in practice. In this paper, we discuss various concepts of sensitivity analysis and survey the work on sensitivity analysis in the dynamic programming literature. In addition, we highlight the relationship between dynamic programming and linear programming and how the approaches and results from the latter can be applied to dynamic programs. A list of promising areas of future research is provided.
Sensitivity Analysis in Linear Programming
Authors: Filippi Carlo 
Published: February 2011

Abstract
Sensitivity analysis in linear programming studies the stability of optimal solutions and the optimal objective value with respect to perturbations in the input data. This analysis is often relevant in practical applications. We discuss the main approaches to sensitivity analysis, including ordinary sensitivity, the 100% rule, and the tolerance approach, giving special attention to degeneracy issues. We focus on the effects of perturbations in the right‐hand side and objective vectors.
The Shapley Value and Related Solution Concepts
Authors: Vlach Milan 
Published: February 2011

Abstract
The Shapley value not only belongs to the most important solution concepts of cooperative game theory but it is also an easily tractable mathematical object with a remarkably wide range of applications. After necessary preliminaries, we introduce basic properties and characterizations of the Shapley value for cooperative games with transferable utility. Then we deal with some of its extensions appearing frequently in the literature. In particular, we present the Aumann–Drèze and Owen generalizations to games with a coalition structure, and the Myerson extension to games with a graph structure. We conclude with the probabilistic values and a brief discussion of application to cost allocation problems.
Shortest Path Problem Algorithms
Authors: Nemani Ashish K. , Ahuja Ravindra K. 
Published: February 2011

AbstractTheshortest path problem(SPP) is a fundamental combinatorial optimization problem that concerns finding the shortest paths between a source and a destination; it is also referred to as asingle‐source shortest path problem(SSPP). In some problem settings, shortest paths between all pairs of nodes are desired; these are referred to as all‐pairs shortest path problems (ASPP). The SPP arises in a number of applications, both as a stand‐alone problem and as a subproblem in more complex scenarios. Several applications have been described in the last chapter. In this article, we describe algorithmic methods to solve the SSPP, as well as the ASPP. In real‐life applications, networks vary in their characteristics such as in the presence of negative arcs, directed cycles, and so forth. We present both customized and the most extensively studied algorithms for each scenario, with an analysis of their individual complexities.
Simultaneous Perturbation and Finite Difference Methods
Authors: Bhatnagar Shalabh 
Published: February 2011

AbstractThis article presents a survey of simultaneous perturbation and finite difference algorithms. One of the most important in this category of algorithms is the simultaneous perturbation stochastic approximation (SPSA) algorithm that has been used in a wide range of settings. The article presents an overview of the theory behind SPSA as well as the recent development of other finite‐difference algorithms along the lines of SPSA. The article also gives an overview of the applications of SPSA and SPSA‐type algorithms in various disciplines of engineering and science.
Single‐Search‐Based Heuristics for Multiobjective Optimization
Authors: Ehrgott Matthias 
Published: February 2011

AbstractThis article explains the single‐search‐based heuristics for multiobjective optimization. The most prominent heuristics of multiobjective simulated annealing, multiobjective tabu search, and Pareto local search are each explained with a detailed pseudocode and further summaries of algorithmic ideas. This is followed by a brief review of hybrid heuristics combining features of single search and population‐based heuristics. The article ends with brief conclusions and suggestions for further reading.
Nonlinear Multiobjective Programming
Authors: Engau Alexander 
Published: February 2011

AbstractThis introductory treatment of the theory and methodology of nonlinear multiobjective programming offers an annotated bibliographic overview of various concepts and approaches to solve continuous deterministic multicriteria optimization problems. First, the notions of Pareto optimality, efficiency, and nondominance are discussed and then related to approximate, epsilon, and proper efficiency. Second, after highlighting similarities and pointing out differences to first‐ and second‐order optimality conditions in classical nonlinear programming, several other topics including duality and sensitivity are also mentioned. Third, a number of solution approaches and generating methods are described with a particular focus on scalarizations using objective aggregation, prioritization, and norm or distance minimization to some utopian reference point.
Solving Stochastic Programs
Authors: Bayraksan Güzİn 
Published: February 2011

AbstractThis article reviews solution methods for stochastic programs. First, decomposition methods that exploit the special structure of stochastic programs are discussed. Then, approximate solution methods based on Monte Carlo sampling and bounding techniques are introduced. The algorithmic ideas are presented with a focus on two‐stage stochastic programs with recourse. Extensions to other class of stochastic programs are pointed out.
Minimum Spanning Trees
Authors: Nemani Ashish K. , Ahuja Ravindra K. 
Published: February 2011

AbstractTheminimum spanning tree(MST) problem is one of the simplest and most studied classical optimization problems. It is concerned with finding a spanning tree of an undirected, connected graph such that the sum of the weight of selected arcs is at a minimum and, therefore, sometimes it is also referred to as theminimum weight spanning tree problem. The importance of MSTs can be derived from its wide range of both direct and indirect applications, some of which are described in this article. Several efficient solution techniques have been used effectively for many years, playing a central role in generating important ideas for designing algorithms for other combinatorial problems. We discuss two classical algorithms:Prim's algorithmandKruskal's algorithm, followed by recent developments that improve the asymptotic time bounds using advanced data structures.
Split Cuts
Authors: Andersen Kent 
Published: February 2011

Abstract

Split cuts were introduced by Cook and his colleagues in the 1990s. Split cuts are based on the following simple Observation. Given an integer vector π ∈ ℤ

n

, and an integer π
0
∈ ℤ, every integer point
x
∈ ℤ

n

satisfies the
split disjunction
: either π
T
x
≤ π
0
or π
T
x
≥ π
0
+ 1. Split cuts are a special case of the
disjunctive cuts
introduced by Balas . The set obtained by adding all split cuts to the linear program (LP) relaxation of a mixed integer program (MIP) is called the
split closure
. We show how split cuts can be obtained from a basis of the LP relaxation of a mixed integer program, and we describe the structure of the split closure. Furthermore, we give a summary of the computational results that have been obtained in the literature on the strength of the split closure as a relaxation of a MIP.
Statistical Methods for Optimization
Authors: Hong L. Jeff 
Published: February 2011

AbstractMany statistical methods have been proposed to solve stochastic optimization problems where the objective functions are expected values of some random performances. In this article, we consider only ranking and selection: a collection of statistical procedures that intend to select the best solution from a finite (and often small) set of solutions, where the solutions can only be evaluated by running random computer experiments. We review two basic formulations of the problem and summarize how statistically valid procedures are designed to take into consideration the unique features of computer experiments.
Stochastic Hazard Process
Authors: Özekici Süleyman 
Published: February 2011

AbstractThe hazard function describes the probabilistic structure of failures in reliability models. It therefore plays a crucial role in reliability and maintenance of systems that are subject to failures. It is generally assumed to be some deterministic and increasing function of time that explains how a system deteriorates or ages as it is used. In this article, we consider hazard functions that are in fact stochastic. The aim is to demonstrate a variety of cases where this is true and to discuss issues related to computation of system reliability. Most of our discussions focus on stochastic hazard processes generated through modulation via random environments.
Continuous‐Time Control under Stochastic Uncertainty
Authors: Marti Kurt 
Published: February 2011

AbstractControl problems from engineering and economics can be represented by a continuous‐time optimal control problem with a convex cost criterion, a nonlinear random differential equation, a stochastic initial state and deterministic or stochastic controls. Thus, the existence and uniqueness of a solution of systems of first‐order differential equations with random parameters is considered first. Then the most important control laws are discussed, such as open‐loop (OL), closed‐loop (CL) as well as the open‐loop feedback (OLF) controls. Since feedback controls can be approximated very efficiently by OLF controls, for practical applications one can confine to the construction of optimal OL controls.Convex approximations of the underlying control problem are obtained then by “inner” linearization of the given control problem, that is, by a linearization of the dynamic equation. Considering the necessary and sufficient optimality condition for the convex approximation of the original problem, stochastic optimal controls may be represented by means of stochastic optimal control laws obtained by solving certain finite‐dimensional stochastic optimization problems. Using then a stochastic version of the Hamilton–Jacobi theory, stochastic optimal controls may be obtained by solving the related canonical or Hamiltonian system of first‐order differential equations, which is a two‐point boundary value problem with random parameters. Approximate solutions of the two‐point boundary value problem are constructed then by (i) discretization of the underlying probability distribution or (ii) by evaluations of the occurring expectations by means of Taylor expansions with respect to the vector of model parameters. The method is applied to the feedback control of mechanical systems (robots) under stochastic uncertainty.
Supply Chain Coordination
Authors: Zhang Fuqiang 
Published: February 2011

Abstract
Supply chain coordination is among the central issues in supply chain management. A supply chain is coordinated if all supply chain members adopt the actions that optimize the entire system's performance. However, in most cases, supply chain firms are independent, self‐interested entities that may deviate from the system‐optimal actions. This article provides an introductory review on how firms can use various contractual schemes to achieve supply chain coordination. Discussions on additional issues and potential research directions are also provided.
TheG/G/1 Queue
Authors: Foss Sergey 
Published: February 2011

AbstractThe article contains a summary of basic results for a single‐server queue. For the case where interarrival and service times are i.i.d., one can find results on stability and continuity, regenerative structure, moments of stationary waiting times, Little's laws, heavy‐traffic limits, and tail asymptotics (both for light and heavy tails). In the case of stationary and ergodic driving sequences, the key stability result is given.
TheG/G/sQueue
Authors: Breuer Lothar 
Published: February 2011

AbstractThis article provides a literature survey on results for the G/G/s multiserver queue with general interarrival and service time distributions. It further presents two fundamental aspects in a concise yet relatively self‐sufficient form. These are results on the waiting time vectors, derived by Kiefer and Wolfowitz, and the special case of the G/M/s queue with exponential service time distributions, first analyzed by Kendall.
The

G

/

M

/1 Queue
Authors: Perry David 
Published: February 2011

Abstract

The
M
/
G
/1 queue and the
G
/
M
/1 queue represent the mainstay of the single server queueing models. Both models are obtained as special cases of the
G
/
G
/1 queue for which most of the relevant measures and functionals cannot be expressed in closed form formulas. This review is a direct continuation of the encyclopedia entry “The
M
/
G
/1 queue”, and the spirit follows the same direction of that article in the sense that we focus on the same measure and functionals. The approach here is based on the special duality between the
M
/
G
/1 queue and the
G
/
M
/1 queue so that one can use known results of the
M
/
G
/1 queue to derive properties into the
G
/
M
/1 queue.
The Global Replenishment Problem
Authors: Bradley James R. , Guerrero Héctor H. 
Published: February 2011

AbstractLong transit lead times in supply chains and the uncertainty of demand during the replenishment lead time present a difficult problem of how best to provide the correct assortment of goods at the right time to each destination in a distribution network. However, goods in global supply chains can follow any one of a number of routes from any overseas origin to a particular final destination (retail store or manufacturing site). These alternative routes, and also the choice of how to load shipments in highly assorted loads or in containers with only a small number of products, provide flexibility, which, if properly exercised, can reduce global supply chain costs. We describe replenishment in global supply chains in detail, and we also present a formulation of that replenishment decision problem. We relate that problem to existing literature and describe various simplifications and extensions to the problem.
TheM/G/sQueue
Authors: Kimura Toshikazu 
Published: February 2011

AbstractThis article provides a brief review of exact and approximate results for theM/G/squeue. The principal focus is on the standardM/G/squeue with homogeneous servers, unlimited waiting spaces, and the FCFS (first‐come first‐served) service discipline. According to some asymptotic properties, previously established approximations for the mean waiting time and the queue length distribution in steady state are classified in a unified way. As an application of theM/G/squeue with finite capacity, a buffer design problem is considered to obtain simple approximations for the optimal buffer capacity.
The
M
/
M
/1 Queue
Authors: Hlynka Myron 
Published: February 2011

Abstract
The M/M/1 queueing system is discussed. Key properties are stated, many with proofs. Steady state and transient probabilities are presented along with many other well‐known properties. A variety of analytical techniques are used in the presentation. Graphs are used to illustrate several aspects of this system.
The
M
/
M
/

s

Queue
Authors: Ulukus M. Yasin 
Published: February 2011

Abstract

This article describes the
M
/
M
/
s
queueing system, or Erlang delay model, which is a stochastic service system with a Poisson arrival process and
s
(1 ≤
s
< ∞) independent and identical servers, each of which serves customers in an exponentially distributed amount of time. Arriving customers join an infinite queue if they find all of the
s
servers busy. The main purpose of this article is to summarize the characteristics of the
M
/
M
/
s
system, namely the steady‐state probability distribution of the number of customers in the system, the steady‐state performance parameters, and steady‐state delay probability which is computed using the well‐known Erlang C formula. As a special case of the
M
/
M
/
s
system, we also discuss the
M
/
M
/
s
/
c
queue. Computational issues and some structural properties of the Erlang C formula are also discussed.
Transient Behavior of
CTMCs
Authors: Distefano Salvatore , Trivedi Kishor S. 
Published: February 2011

Abstract
Since their first specification, Markov models have been widely used for modeling many kinds of systems, in different environments, in application fields, and with different purposes. The success of the formalism of Markov chains is due to the simplicity and the effectiveness in (analytically) evaluating discrete state‐space systems, providing both transient and steady‐state analyses. But the Markovian assumption often limits the applicability of Markov chains. This limitation can be overcome by nonhomogeneous Markov chains and phase type distributions, allowing us to model more general behaviors. This further enhances the importance and the effectiveness of Markov chains and related formalisms. In this article, we focus on the transient behavior of Markov models, providing an overview of their solution techniques.
Transient Behavior of
DTMCs
Authors: Gautam Natarajan 
Published: February 2011

Abstract
The objective of this article is to describe the transient behavior of discrete‐time Markov chains (DTMC). We first provide some notation and terminology necessary for transient analysis. Then we provide a procedure for analyzing a DTMC and predicting the state after a finite number of jumps. Finally, we provide algorithms to efficiently perform transient analysis for DTMCs and obtain performance measures.
Understanding and Managing Variability
Authors: Ahn Hyun‐Soo 
Published: February 2011

Abstract
Variability exists in almost all production and manufacturing systems. Demand and product mix may vary over time, as may the processing capacity of the system and the availability of raw materials and components. Variability in demand or manufacturing processes makes seamless alignment of demand and supply impossible and degrades system performance. Understanding the effects of variability and how to effectively manage them are critical elements to the design and control of production and service systems. This article discusses the sources and types of variability, the effect of variability in manufacturing systems, and managerial tools to mitigate the adverse effects of variability.
Uniformization in
M
arkov Decision Processes
Authors: Alagoz Oguzhan , Ayvaci Mehmet U.S. 
Published: February 2011

Abstract
Continuous‐time Markov decision processes (CTMDP) may be viewed as a special case of semi‐Markov decision processes (SMDP) where the intertransition times are exponentially distributed and the decision maker is allowed to choose actions whenever the system state changes. When the transition rates are identical for each state and action pair, one can convert a CTMDP into an equivalent discrete‐time Markov decision process (DTMDP), which is easier to analyze and solve. In this article, we describe uniformization that uses fictitious transitions from a state to itself and hence enables the conversion of a CTMDP with nonidentical transition rates into an equivalent DTMDP. We first demonstrate the use of uniformization in converting a continuous‐time Markov chain into an equivalent discrete‐time Markov chain, and then describe how it is used in the context of CTMDPs with discounted reward criterion. We also present examples for the use of uniformization in continuous‐time Markov models.
Use ofLagrange Interpolating Polynomials in theRLT
Authors: Adams Warren P. 
Published: February 2011

AbstractThis article examines the use of Lagrange interpolating polynomials (LIPs) in constructing polyhedral outer‐approximations and convex hull representations of mixed‐discrete sets. The LIPs provide the theoretical foundation for extending the reformulation‐linearization technique (RLT), used for automatically computing tight relaxations of mixed‐binary programs, to handle discrete variables that can realize values within finite sets. The LIPs operate by generalizing the idempotent property of binary variablesxthatx2 = x, thereby promoting a hierarchy of progressively tighter forms that culminates in an explicit algebraic characterization of the convex hull of feasible solutions at the highest level. The methods of proof, which employ Kronecker products of transposes of Vandermonde matrices, both subsume and provide insight into the mixed‐binary RLT.
Exact Solution of the Capacitated Vehicle Routing Problem
Authors: Baldacci Roberto , Vigo Daniele , Toth Paolo 
Published: February 2011

Abstract
Vehicle routing problem (VRP) is a generic name given to a whole class of problems concerning the optimal design of routes to be used by a fleet of vehicles to serve a set of customers. The VRP generalizes one of the most famous and important combinatorial optimization problems: the traveling salesman problem (TSP). Since it was first proposed by Dantzig and Ramser in 1959, hundreds of papers in the areas of operations research were devoted to the exact and approximate solution of a member of the VRP class, known as the capacitated vehicle routing problem (CVRP), where a homogeneous fleet of vehicles is available and the only constraint considered is the vehicle capacity constraint. Real‐world applications of the VRP are, for instance, delivery and collection of goods, solid waste collection, street cleaning, school bus routing, dial‐a‐ride systems, transportation of handicapped persons, and routing of salesmen and of maintenance units. This article provides a review of the developments that had a major impact in the current state‐of‐the‐art of exact algorithms for the CVRP. The paper also reports a comparison of the computational performances of the recent exact methods.