bluuebunny/crossref_metadata_2025 huggingface dataset:
Gradient‐Type Methods
Authors: Pajouh Foad Mahdavi , Balasundaram Balabhaskar
Published: February 2011

The gradient method
, which is also called
the method of steepest descent
, and
the Cauchy method
, is one of the most fundamental derivative‐based procedure for unconstrained minimization of a differentiable function. The performance of the method in terms of speed of convergence is lacking, and it tends to suffer from very slow convergence, especially as a stationary point is approached. However, it does guarantee global convergence under reasonable conditions and admits a thorough mathematical analysis of its behavior. For this reason, the gradient method has been used as a starting point in the development of more sophisticated, globally convergent algorithms with better convergence properties for unconstrained minimization. This article presents a cogent overview of this fundamental method and its convergence properties under various settings.
Graph Search Techniques
Authors: Yang Boting
Published: February 2011

Given a graph, suppose that there is a robber hiding on vertices or along edges. A graph searching problem is to find the minimum number of searchers required to capture the robber. In this article, we describe the main characteristics of graph searching problems. For undirected graphs, we consider the edge search, node search, mixed search, visible‐robber game, and inert‐robber game. For digraphs, we consider directed search, strong search, weak search, strong direct visible‐robber game, directed visible‐robber game, and directed inert‐robber game. We also deal with cops‐and‐robber games in which cops and the robber take turns to move. Most searching problems correspond to width parameters in graph theory. We describe the relationships between models and width parameters. We only survey the basic models, giving references to other variants.
Grasp: Greedy Randomized Adaptive Search Procedures
Authors: Resende Mauricio G. C. , Silva Ricardo M. A.
Published: February 2011

GRASP or greedy randomized adaptive search procedure, is a multistart metaheuristic that repeatedly applies local search starting from solutions constructed by a randomized greedy algorithm. In this article we review the basic building blocks of GRASP. We cover solution construction schemes, local search methods, and the use of path‐relinking as a memory mechanism in GRASP.
History of LP Development
Authors: Murty Katta G.
Published: February 2011

The linear programming (LP) model is the most commonly used mathematical model in decision‐making applications today. LP is the branch of mathematics dealing with methods for solving systems of linear constraints including linear inequalities, and possibly also linear equations. Its origin has its roots in the development of mathematics itself going back to ancient times. The first method developed over 2000 years ago can handle only systems of linear equations, leading to the branch of mathematics now known as linear algebra. After a very long gap, methods for handling LPs have been developed only in the twentieth century. In this article, we summarize the milestones in the fascinating history of LP.
Housing and Community Development
Authors: Johnson Michael P.
Published: February 2011

Researchers in housing and community develop, design, and evaluate policies to improve access to attractive, affordable, and sustainable housing and to support the social, physical, and economic infrastructure of communities. Practitioners in this field confront political considerations, administrative guidelines, and limited funding. Operations research and management science can increase the efficiency and effectiveness of policy responses to issues such as affordable housing, residential segregation, and inequalities in economic and social opportunities. This research spans systems modeling, urban economics, multicriteria decision modeling, stochastic models, and decision support systems and is often interdisciplinary and applied in nature. A common thread in this work is the need to explicitly address the needs of multiple stakeholders, to capture the public and private nature of housing, and to incorporate best‐available evidence regarding markets, policies, and impacts of housing and community development. In this article, we describe the policy context for decision modeling in housing and community development, review previous research through the lens of descriptive, prescriptive, and decision support analysis, and identify important limitations to this research. We then describe diverse opportunities to address current policy concerns such as sustainable development, post‐disaster reconstruction, and individual and group decision support.
Implementing the Simplex Method
Authors: Saltzman Matthew J.
Published: February 2011

The basic simplex method is a simple and straightforward algorithm, but modern efficient implementations represent a tour de force of algorithm engineering and numerical methods designed to exploit opportunities for efficiency wherever they arise. This article surveys the key techniques necessary to implement a robust, efficient simplex code. These techniques support the strategic design principles of minimizing the number of iterations and carrying out the computations in each iteration efficiently and accurately. The primal and dual bounded‐variable simplex algorithms are described. Efficient and robust advanced techniques for finding a starting solution, effective pricing, ratio tests and degeneracy management, and sparse linear algebra are covered.
Impossibility Theorems And Voting Paradoxes In Collective Choice Theory
Authors: Penn Elizabeth Maggie
Published: February 2011

This article provides an introduction to several of the most well known impossibility theorems in voting theory, including Arrow's theorem, May's theorem, Sen's liberal paradox, and the Gibbard–Satterthwaite theorem. It concludes with a discussion of various widely known voting paradoxes, including Condorect's paradox, Ostrogorski's paradox, and the Alabama paradox.
Inequalities from Group Relaxations
Authors: Richard Jean‐Philippe P.
Published: February 2011

This article provides a review of the group‐theoretic approach to the generation of cutting planes in mixed integer programming. After motivating the notion of corner relaxation graphically, we give a definition of master group problems. We then present a hierarchy of valid inequalities for master group problems that can be used as cutting planes for mixed integer programs. We describe next various procedures that can be used to obtain the “strongest” valid inequalities for master group problems. We conclude by commenting on the computational possibilities of group‐theoretic cuts in mixed integer programming.
Integer Programming Duality
Authors: Guzelsoy Menal , Ralphs Ted K.
Published: February 2011

This article surveys what is known about the theory of duality for integer programs and describes methods for obtaining dual solutions.
Two‐Stage Stochastic Programs: Introduction and Basic Properties
Authors: Birge John R.
Published: February 2011

This article introduces the two‐stage form of stochastic programs that describe decision situations in which an action is taken, followed by observation of a random event and subsequent follow‐on action. The article describes the basic formulation of these problems as optimization models and then describes basic properties of solution existence, optimality conditions, and equivalent formulations that exploit problem structure for computational efficiency.
Introduction to Facility Location
Authors: Snyder Lawrence V.
Published: February 2011

This article provides a broad overview of facility location problems, one of the oldest and most widely studied fields of applied optimization. The article presents a standard taxonomy of location models and discusses key dimensions along which they are classified. Mathematical programming formulations and common solution methods for several classical models are described. A variety of extensions that build upon these models and their application to richer and more complex settings are also discussed. The article covers discrete and network location problems and, to a lesser extent, continuous problems.
An Introduction to Linear Programming
Authors: Cochran James J.
Published: February 2011

This article provides an overview of linear programming. Constrained and unconstrained optimization are first explained and contrasted, and the assumptions of linear programming are explained. An example problem is formulated and solved both graphically and by enumeration, and the example is used as the basis for an explanation of the simplex algorithm. Special cases are discussed, and the relationship between primal and dual formulations is explained.
Introduction to Point Processes
Authors: Schoenberg Frederic Paik
Published: February 2011

Point process models are useful for describing phenomena occurring at random locations and/or times. Following a review of basic concepts, some important models are surveyed including Poisson processes, renewal processes, Hawkes processes, and Markovian point processes. Techniques for estimation, simulation, and residual analysis for point processes are also briefly discussed.
Introduction to Polynomial Time Algorithms forLP
Authors: Terlaky Tamás
Published: February 2011

The first polynomial time algorithm for linear programming (LP), the so‐called ellipsoid method, was proposed by Leonid Khachiyan in 1979. Then the 1984 paper of Narenda Karmarkar launched the age of interior point methods (IPMs). Several variants of the ellipsoid method, and hundreds of polynomial time IPMs were designed in the past decades. Interior point software implementations have challenged simplex method implementations, and frequently surpassed their performance.

The goal of this article is to give a brief introduction to polynomial time algorithms for LP.
Introduction To Robust Optimization
Authors: Smith J. Cole , Ahmed Shabbir
Published: February 2011

Robust optimization models are used to address optimization problems with uncertain data. These models enforce the condition that a feasible solution should satisfy all constraints under any possible realization of constraint data. Furthermore, the optimization process should provide a worst‐case guarantee on the quality of the solution, for any possible realization of objective data. Thus, for a minimization problem, the objective minimizes the maximum objective that could result from uncertain data. This article provides an overview of robust optimization models and properties, with an emphasis on robust linear optimization.
Presolving Mixed–Integer Linear Programs
Authors: Mahajan Ashutosh
Published: February 2011

We survey the techniques used for presolving mixed‐integer linear programs (MILPs). Presolving is an important component of all modern MILP solvers. It is used for simplifying a given instance, for detecting any obvious problems or errors, and for identifying structures and characteristics that are useful for solving an instance.
Efficient Iterative Combinatorial Auctions
Authors: Mishra Debasis
Published: February 2011

This survey considers the following setting. A seller wants to sell a set of indivisible goods. A set of buyers are interested in buying the goods. Buyers have private values for bundles of goods they are interested in buying. The seller's objective is to allocate the goods to the buyers efficiently (maximizing the total utility of buyers). Since the values of buyers are private information, this creates an incentive problem. Economic theory prescribes the Vickrey–Clarke–Groves (VCG) mechanism to solve this problem. However, the VCG suffers from various drawbacks because of its centralized implementation. An alternative decentralized way of implementing the VCG is the iterative combinatorial auctions. We survey the foundations of iterative combinatorial auctions that implement the VCG mechanism. We also describe a particular iterative combinatorial auction that implements the VCG mechanism.
Jackson Networks (Open and Closed)
Authors: Daduna Hans
Published: February 2011

We describe the classical exponential networks of Jackson and Gordon and Newell and their successor networks and extensions in network theory. The characterizing feature of these networks is the product form steady‐state distribution for the joint queue length process, which we evaluate in detail.

We characterize passage time behavior for customers traversing the networks or parts of it. This relies on finding the distributions, which characterizes the situation when such a passage commences.

We sketch typical algorithmic methods to efficiently compute performance indices for the networks in steady state.

Finally, we describe some networks with additional features that broaden the range of applicability of the networks.
The Knowledge Gradient for Optimal Learning
Authors: Powell Warren B.
Published: February 2011

Optimal learning addresses the problem of how to collect information so that it benefits future decisions. For off‐line problems, we have to make a series of measurements or observations before choosing a final design or set of parameters; for on‐line problems, we learn from rewards we are receiving, and we want to strike a balance between rewards earned now and better decisions in the future. This article reviews these problems, describes optimal and heuristic policies, and shows how to compare competing policies. Then, the presentation focuses on the concept of the knowledge gradient, which guides information collection by maximizing the marginal value of information. We show how this idea can be applied to both on‐line and off‐line problems, as well as a broad range of other applications which have not previously yielded to formal techniques.
Lagrangian Optimization for LP
Authors: Desai Jitamitra
Published: February 2011

In this article, we present a methodological framework for solving large‐scale
linear programming
(LP) problems via a Lagrangian optimization approach. Beginning with a formulation of the Lagrangian dual problem, we relate this approach to standard LP theory in two steps: first, we demonstrate that the optimal objective function value obtained by solving the Lagrangian dual is optimal to the original linear program; and second, we include theorems and propositions that characterize the mathematical properties of the Lagrangian dual and establish the equivalence of this approach to classical LP duality. Recognizing that the Lagrangian dual formulation is a nondifferentiable optimization problem, a subgradient algorithm is prescribed for solving this problem, and computational results for an illustrative example are presented. A brief extension of this approach for solving integer programs can also be found in this article.
Lifting Techniques For Mixed Integer Programming
Authors: Richard Jean‐Philippe P.
Published: February 2011

This article provides a review of lifting techniques for the generation of cutting planes in mixed integer programming. After motivating the notion of lifting graphically, four key steps in the derivation of lifted inequalities are described: (i) variables fixing, (ii) derivation of seed inequalities, (iii) (re‐)computation of lifting functions, and (iv) derivation of lifting coefficients. Practical considerations that are relevant to each of these steps are discussed and is emphasized the importance of superadditivity in designing efficient lifting procedures. This concluded with a description of the strength of lifted cuts. Throughout, concepts on a simple example are illustrated.
Limit Theorems for Renewal Processes
Authors: Liu Nan
Published: February 2011

This article describes the key renewal theorem and the Blackwell's renewal theorem. These two limit theorems for renewal processes are equivalent but of different forms. They are particularly useful for characterizing the asymptotic behavior of a probabilistic quantity of interest in a renewal process. We present two classical applications of these limit theorems: the limiting distributions of recurrence times in a renewal process and the asymptotic expansion of a renewal function. Further readings on the theoretical development of these limit theorems and their applications in different areas are also provided.
Linear Programming and Two‐Person Zero‐Sum Games
Authors: Zafra Pablo
Published: February 2011

The equivalence between linear programming (LP) and two‐person zero‐sum games (also commonly referred to asmatrix games) was established when the minimax theorem in game theory proved to be equivalent to the duality concept in LP. The equivalence is discussed as follows: Given a general matrix game, the associated primal‐dual LP problems will be formulated, and, conversely, given an LP problem with a minimization objective function, a skew‐symmetric payoff matrix of the equivalent symmetric game will be constructed. In either case, once the solutions to the equivalent problem are found, it is a simple task to retrieve the solutions to the original problem. Examples are provided to illustrate the transformation procedures, and different types of constraints for the given LP problem are also considered (normal, standard and mixed).
Constraint Programming Links with Math Programming
Authors: Milano Michela
Published: February 2011

Although operations research (OR) and constraint programming (CP) have different roots, the links between the two communities have grown stronger in recent years. For solving combinatorial optimization problems, the techniques of CP and OR will become so interdependent that the two research communities could eventually merge. In this article, we first describe CP basic concepts, and then we show different ways of integrating CP and mathematical programming (MP). This article presents a CP perspective: MP is seen as a support to the CP decision process, even if existing approaches from the OR literatures consider a cooperation of CP and MP on an equal basis, but they are out of the scope of this article.
L
ittle's Law and Related Results
Authors: Wolff Ronald W.
Published: February 2011

For queues, and similar systems, Little's Law, often written
L
 = λ
w
, states that the time average of the number of customers in system is the product of the arrival rate and the customer average of their waiting times. We treat
sample‐path
and
stationary
versions of this result and extensions, including
H
 = λ
G
, and a distributional Little's Law. We illustrate how these results are applied and treat the connection between these results and a rate conservation law.
Lot‐Sizing
Authors: van den Heuvel Wilco
Published: February 2011

Lot‐sizing deals with the optimal timing and level of procurement in production and inventory management. This article introduces some basic continuous‐ and discrete‐time lot‐sizing models with associated mathematical formulations. Furthermore, we describe the directions in which the basic models can be extended.
Lovász‐Schrijver Reformulation
Authors: Tulsiani Madhur
Published: February 2011

We discuss the hierarchies of linear and semidefinite programs defined by Lovász and Schrijver. We describe recent progress on these hierarchies in the contexts of algorithm design, computational complexity, and proof complexity.
LP
Duality and
KKT
Conditions for
LP
Authors: Clausen Jens
Published: February 2011

Duality is one of the most central concepts in connection with Linear Programming (LP), both from a theoretical and an algorithmic point of view. LP problems always appear in pairs with a primal problem and a corresponding dual problem—a fact which is intimately related to the concept of relaxation and to the necessary and sufficient optimality conditions known as
Karush‐Kuhn‐Tucker (KKT)‐conditions
for nonlinear programs (NLPs).

This article first introduces the concept of LP duality and discusses various ways of presenting duality. The fundamental theorems of Weak and Strong Duality are stated and proven. The Complementary Slackness Conditions for optimality of a set of primal and dual solutions to a set of dual LPs are then introduced, and finally it is demonstrated that these conditions are the Karush‐Kuhn‐Tucker (KKT) conditions known from NLP restated in a linear setting.
Linear Programming Projection Algorithms
Authors: Evtushenko Yury , Golikov Alexander
Published: February 2011

Fast linear programming projection methods for solving primal and dual linear programming problems are described. These methods find the projection of given points on the solution sets of primal or dual LP problems by reducing LP to a single maximization of an auxiliary function, which is solved by globally convergent finitely terminating generalized Newton method. Some results of uniprocessor and multiprocessor computations are presented.
Management Science/Operations Research Society of Malaysia
Authors: Mamat Ilias
Published: February 2011

This article introduces the background of the Management Science/Operations Research Society of Malaysia (MSORSM) as a professional association. The objective is to promote, foster, and generate participative communities for the advancement of management science/operations research as an interdisciplinary field. The membership categories and activities are being highlighted to achieve the objects through several strategies.
Managing Perishable Inventory
Authors: Baron Opher
Published: February 2011

This article provides an introduction to the management of perishable items. We first highlight some key differences between inventory models for nonperishable items and models for perishable ones. Next, several models for inventory management of perishable items are discussed. An important observation from this discussion is the need for finding effective heuristics for the optimal control of inventory for perishables. Therefore, we demonstrate the development of one such heuristic. The article ends with a list of future research directions on the management of inventory of perishables.
Managing A Portfolio of Risks
Authors: Keisler Jeffrey M. , Linkov Igor I.
Published: February 2011

Managers and stakeholders concerned about all sorts of entities often face a complex mixture of threats originating from multiple sources. Traditional management approaches that deal with multiple decisions, such as project portfolio management and risk assessment, are focused on single sources of risk or they integrate risks using simplified assumptions (e.g., simple addition). Current challenges—including emergency response to natural disasters, homeland security threats, emerging materials, and correlated events—and an uncertain future with respect to societal concerns—for example, climate change, economic development, and social/religious instabilities—require integrated application of these methods. This article describes a range of risk approaches that enable a flexible approach to risk portfolio management. Decision quality serves as an integrating framework for applying a mix of analytic methods to facilitate successful risk portfolio management. Methods including portfolio decision analysis and risk management, as well as other tools from risk analysis, utility theory, and modern portfolio theory from finance, help to address complexities of current risk portfolio management challenges.
Markov and Hidden Markov Models
Authors: Soyer Refik
Published: February 2011

In this article we give an overview of Markov models that are used for describing dynamics of operating environments in reliability analysis. We present both continuous‐ and discrete‐time Markov chains as well as diffusion processes. We also consider Markov modulated stochastic processes that are known ashidden Markov modelsand discuss their properties. More specifically, we give an overview of Markov modulated Poisson and Markov modulated Bernoulli processes.
Matrix‐Geometric Distributions
Authors: Baum Dieter
Published: February 2011

Matrix‐geometric distributions are explained by emphasizing the role of structure. The derivation is based on probabilistic arguments gained from the theory of terminating renewal processes. Ergodicity properties and computational aspects are discussed only briefly; thefurther readingsection gives references to more detailed treatment.
Maximum Flow Algorithms
Authors: Sargut Zeynep , Ahuja Ravindra K.
Published: February 2011

In this article, we will explain the maximum flow problem and the solution algorithms classified under augmenting path, blocking flow, preflow‐push, and other algorithms. For the first three classes, we first present the generic version of the algorithm and then present some elaborate versions in the literature. We also give other approaches and the more efficient algorithms for unit capacity, bipartite, and planar networks. Although the binary blocking flow algorithm has the best theoretical worst‐case running time, the preflow‐push type algorithms are shown to be the most efficient algorithms in practice.
Methods For Large‐Scale Unconstrained Optimization
Authors: Fasano Giovanni
Published: February 2011

In this article, we review methods for the solution of unconstrained optimization problems, where the number of unknowns is large. We first describe the basics of unconstrained optimization, then we consider the iterative methods that are commonly used within large‐scale optimization. The techniques described here explicitly use information on the objective function and some of its derivatives. Extensions to effective quasi‐Newton methods for partially separable optimization are detailed.
Minimum Prediction Error Models and Causal Relations between Multiple Time Series
Authors: Zhang Jicong , Xanthopoulos Petros , Chien Jui‐Hong , Tomaino Vera , Pardalos Panos M.
Published: February 2011

Prediction is widely used in economics, finance, weather forecasting, earthquake monitoring, and other social and scientific fields. Though difficult, it is important to know what will happen in the future. Least square error (LSE) model and minimum mean square (MMSE) model are the fundamental models of a large group of minimum prediction error models in deterministic and stochastic senses respectively. The key in the minimum prediction error model is the principle of orthogonality to reach global optimum. Further, the MMSE model can be considered a special case of ARMA/ARIMA models. Besides LSE and MMSE, the causal relations between two, three, and multiple variables are reviewed and explored, and the principle of orthogonality is again part of the intrinsic mathematics. Finally, other prediction methods such as the Box–Jenkins prediction are discussed briefly.
Mixing Sets
Authors: Wolsey Laurence A.
Published: February 2011

A mixing set is a simple mixed integer set that has a rich structure and has turned out to provide very effective relaxations for a variety of lot‐sizing problems. Here we describe some applications, some of the basic results on valid inequalities and extended formulations. We then present several of the generalizations that have been studied, and indicate the major results obtained for these general mixing sets.
Modeling and Forecasting by Manifold Learning
Authors: Ni Xuelei (Sherry)
Published: February 2011

Forecasting can benefit from recently emerged manifold learning algorithms. We describe the connection between manifold learning and forecasting. Moreover, we study the properties of different manifold learning methods and their reconstruction. These will be the technical core of the forecasting. Because manifold‐based forecasting is model‐free and totally nonlinear, it is promising in dealing with complex data.
Structured Optimal Policies forMarkov Decision Processes: Lattice Programming Techniques
Authors: Dragut Andreea
Published: February 2011

The structure (monotonicity, convexity, multimodularity, directional convexity and K‐convexity) of optimal policies is used to reduce the exponential growth with respect to the size of a sequential decision process and to compare different control systems.

Monotonicity can be derived using Tattice programming techniques, sample path analysis or discrete events dynamic programming.

We cover the discrete and continuous‐time MDP and POMDP models with Borel, countable‐and finite‐state and action spaces, as well nonstationary ones.

Applications include admission/control of (networks of) queues, maintenance, inventory, production and innovation.
Multiechelon Multiproduct Inventory Management
Authors: Parker Rodney P.
Published: February 2011

This article summarizes the inventory management literature within the context of multiechelon systems. The optimal inventory policies for the single‐installation under discrete‐time and continuous‐time are described, followed by the optimal inventory policies for the serial multiechelon system, with the interpretation of the associated induced penalty cost functions. The assembly system's optimal policy translation to an “equivalent” serial system is demonstrated and discussed. Although the optimal inventory policies of distribution systems are generally not known, the performance of various simple heuristics are then discussed.
Multistage (Stochastic) Games
Authors: Krishnamurthy Nagarajan , Parthasarathy Thiruvenkatachari
Published: February 2011

We define two‐person zero‐sum and nonzero‐sum stochastic games with finite state space and finite action space. We discuss the case of β‐discounted payoffs as well as that of undiscounted or limiting time average payoffs. We look at certain classes of stochastic games that possess the orderfield property, that is, given rational inputs, such games have a rational solution. To solve such classes exactly, there is hope for finding finite arithmetic‐step algorithms. We discuss algorithms for some such classes. We also briefly discuss determinacy of stochastic games with countable state space and Borel payoffs. Furthermore, we outline some applications of stochastic games as well as some recent work.
Network‐Based Data Mining: Operations Research Techniques and Applications
Authors: Boginski Vladimir
Published: February 2011

We discuss concepts and applications arising in the area of network‐based techniques in data mining. The approach of representing real‐world data sets as large‐scale graphs has become widely used during recent years. The purpose of this article is to briefly review the graph‐theoretic and network optimization concepts that are important in the context of data mining and discuss the interpretation of these concepts in data mining problems from the operations research perspective.
Software For Nonlinearly Constrained Optimization
Authors: Leyffer Sven , Mahajan Ashutosh
Published: February 2011

We categorize and survey software packages for solving constrained nonlinear optimization problems, including interior‐point methods, sequential linear/quadratic programming methods, and augmented Lagrangian methods. In each case, we highlight the main methodological components and provide a brief summary of interfaces and availability.
Operations Research in Data Mining
Authors: Wang Shouyi , Chaovalitwongse Wanpracha Art , Seref Onur
Published: February 2011

Data mining (DM) and operations research (OR) are two largely independent paradigms of science. DM involves data driven methods that are aimed at extracting meaningful patterns from data instances, whereas OR employs mathematical models and analytical techniques to achieve optimal solutions for complex decision‐making problems. DM and OR are also two overlapping disciplines. There is a growing interest in applying OR techniques to determine the optimal underlying fitting data structures in DM problems. This article provides a description of the basic concepts and methodologies of influential DM techniques, and discusses how OR can be applied to these techniques.
F
ritz–
J
ohn and
KKT
Optimality Conditions for Constrained Optimization
Authors: Andreas April
Published: February 2011

Optimality conditions for Fritz–John and Karush Kuhn Tucker (KKT) points provide one strategy for solving nonlinear optimization problems. In fact, KKT conditions are necessary, if not sufficient, for proving optimality. In this article, we introduce Fritz–John and KKT optimality conditions for constrained optimization. We begin by reviewing some essential definitions for completing the logic, including Gordon's and Farkas' Lemmas. We derive the Fritz–John conditions and show when these conditions are necessary to show optimality. We then derive the necessary and sufficient KKT conditions for optimality. The article concludes with two simple numerical examples illustrating Fritz–John and KKT theory.
Matrix Analytic Method: Overview and History
Authors: Alfa Attahiru S. , Ramaswami Vaidyanathan
Published: February 2011

This article provides an overview of matrix analytic methods in probability along with a historical account of major milestones along their development.
Parallel Systems
Authors: Park Minjae , Pham Hoang
Published: February 2011

This paper presents a cost analysis of parallel systems based on the altered quasi‐renewal process with random parameter and a mixed quasi‐renewal process considering replacements and repairs. A numerical example is discussed to demonstrate the applicability of the proposed cost models.
Penalty and Barrier Methods
Authors: Nash Stephen G.
Published: February 2011

Penalty and barrier methods solve a constrained optimization problem via a sequence of unconstrained problems. Under appropriate assumptions, the solutions of the unconstrained problems are guaranteed to converge to the solution of the original constrained problem. However, to obtain an accurate solution, the unconstrained problems will typically become ever more ill‐conditioned, and special algorithmic techniques are needed to ensure good performance. Penalty and barrier methods were important during the 1960s, but lost favor because of the difficulties associated with ill‐conditioning (even though remedies were known at that time). However, interest in barrier methods revived in the 1980s in connection with the development of interior‐point methods for linear programming. Penalty and barrier methods are useful methods in their own right, but they also form the theoretical and practical underpinning to other important and widely used methods. They can be grouped together under the label of penalization methods. Penalty methods impose a penalty for violating a constraint, and barrier methods impose a penalty for approaching the boundary of an inequality constraint.
Percolation Theory
Authors: Wierman John
Published: February 2011

Percolation theory is a collection of mathematical models for phenomena such as fluid flow and clustering behavior in random media. This article emphasizes three major aspects of the theory: (i) The percolation threshold is a critical point at which the properties of the model exhibit a substantial change. The threshold depends on the detailed structure of the lattice graph used to model the medium, and various approaches for finding exact values, bounds, and estimates of percolation threshold of different lattices are discussed. (ii) The behavior of a model at and near the percolation threshold is believed to be independent of the detailed structure of the graph, described by power laws, which depend only on the dimension in the case of lattice graphs. (iii) The variety of extensions and generalizations of the classical percolation models allow a wide range of phenomena to be modeled. A selection of different percolation models are mentioned to illustrate the possible range of applications.
Performance Bounds in Queueing Networks
Authors: Veatch Michael H.
Published: February 2011

Optimal controls for many multiclass queueing networks are complex and intractable to compute. This paper surveys computable performance bounds. The primary focus is sequencing and scheduling control in open networks to minimize the long run average number of customers, or a weighted average over different customer classes. Lower bounds are given for any policy and, in some cases, upper bounds for a class of policies. Closed networks are considered briefly. Many of these bounds require only solving a linear program. Some pathwise bounds are also discussed.
Phase‐Type (PH) Distributions
Authors: Pérez‐Ocón Rafael
Published: February 2011

The phase‐type (PH) distributions were introduced by Neuts (1981). They are playing an important role in modeling random phenomena due to their interesting properties, and it has a widespread use in applied probability. A continuous PH distribution is the distribution of the absorption time in a Markov chain in continuous time with a finite‐state space and one absorbent state. The cumulative distribution function (CDF) has exponential form, and it is deduced from the underlying Markov process. The class of PH distributions has important closure properties which make it very versatile in applications; it is closed for finite convolution, finite mixture, formation of coherent systems, and order statistics. On the other hand, it has interesting properties of approximation. This class is dense, in the sense of distributions, in the class of distribution functions defined on the positive real half line, so it is possible to approach general distributions by elements of this class. The use of PH distributions in stochastic modeling leads to results that can be presented in algorithmic form and the results are susceptible to computational implementation. The PH distributions together with the Markovian arrival processes are the basic elements in what is known as matrix‐analytic methods.
Power Indices
Authors: Freixas Josep
Published: February 2011

This paper deals with simple games, that is a voting situation in which a single alternative, such as a bill or amendment, is pitted against the status quo. In these systems, each voter responds with a vote “yea” or “nay.” A simple game is simply a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. After studying a little the mathematical structure of simple games, we proceed to introduce power, which is a central concept in political sciences. We revise some well‐known power indices as well as some existent background known in the literature.
Probabilistic Distance Clustering
Authors: Iyigun Cem
Published: February 2011

Probabilistic distance clustering is an iterative method for probabilistic clustering of data. Given clusters, theircenters, and thedistancesof data points from these centers, theprobabilityof cluster membership at any point is assumed to be inversely proportional to the distance from (the center of) the cluster in question. This assumption is the workingprinciple.

The method is a generalization, to several centers, of theWeiszfeld methodfor solving the Fermat–Weber location problem. At each iteration, the distances (Euclidean, Mahalanobis, etc.) from the cluster centers are computed for all data points, and the centers are updated as convex combinations of these points, with weights determined by the above principle. Computations stop when the centers stop moving.

Progress is monitored by thejoint distance function, a measure of distance from all cluster centers, which evolves during the iterations and captures the data in its low contours.

The method is simple, fast (requiring a small number of cheap iterations), and insensitive to outliers.
An Introduction to Probabilistic Risk Analysis for Engineered Systems
Authors: Paté‐Cornell Elisabeth
Published: February 2011

The risk of failure of a system can sometimes be simply characterized by the probability of system failure per time unit or operation. More often, it include both the probabilities and the consequences of the different failure scenarios, in which case the risk can be described by the probability distribution of the losses in a given time frame. Risk management, in turn, involves finding and fixing a system's weaknesses by asking the following questions. How does it work? How can it fail? What can be done about it given that we are not infinitely rich and time is limited? For a complex engineered system, one may not have a sufficient statistical database to assess a failure probability at the system level. In that case, one can use systems analysis and Bayesian probability to assess the risk. Probabilistic risk analysis (PRA) has been developed in engineering, in particular in the nuclear power industry to quantify the risk of system failures. The method relies in part on event trees and fault trees, or, similarly, on Bayesian networks. It involves first, identification of failure scenarios, then computation of their probabilities by combining the probabilities of events and the distributions of random variables involved, accounting for dependencies and rare occurrences. The next step is the evalution of the consequences of the failure scenarios. The results can then be used as input into a risk management problem with two objectives: to optimize resource allocation (e.g., to minimize the probability of system failure given budget and system failure given budget and schedule constraints) and to check that in the end the failure risk is tolerable. This article describes and illustrates the PRA method and some of its extensions.
Operations Research in the Visual Arts
Authors: Kaplan Craig S. , Bosch Robert
Published: February 2011

This article explores applications of optimization algorithms to the computer‐based synthesis of art. The presentation covers title‐based methods, freeform arrangement of elements, and line art.
Queueing Notation
Authors: Cooper Robert B.
Published: February 2011

The notation and conventions used in specifying queueing models are described.
Random Variate Generation
Authors: Leemis Lawrence M.
Published: February 2011

This article outlines (i) techniques for the generation of random variates using density‐based and hazard‐based methods, (ii) techniques for the generation of certain stochastic point processes that are useful in stochastic modeling, and (iii) further reading in the area of generation of random objects. The accurate modeling of failure time distributions is critical for the development of valid Monte Carlo and discrete‐event simulation models. Once an accurate model has been established, it is oftentimes the case that the complexity of the model requires an analysis by simulation. The associated variate generation algorithms for common stochastic models are introduced in this article.
Recycling
Authors: Akçali Elif
Published: February 2011

With changes in consumption patterns, complex industrial products (e.g., automobiles, cellular phones, and computers) are beginning to account for an increased fraction of the solid waste generated. Hence, the scope of the recycling industry, which was limited to simple products that are made of steel, glass, and some types of plastics in the past, has been expanding to include the recycling of such complex industrial products. With the expanding scope and size of the recycling industry, operations research (OR) tools and techniques are increasingly being utilized for the optimization of recycling operations and the underlying reverse supply chain (RSC) systems.

This article begins by highlighting some of the practical issues encountered in recycling practice that create unique modeling challenges for the design and operation of underlying RSC systems. Then, a brief review of the related OR literature on important planning and control problems that are encountered in the context of RSC systems is presented. By focusing on a pricing problem that arises in the context of end‐of‐life vehicle recycling, the article demonstrates how OR models can be used to assess the economic and environmental efficiency of RSC systems for recycling and to provide support for decision making.
Reflected
B
rownian Motion
Authors: Dieker A. B.
Published: February 2011

Reflected Brownian motion is a continuous‐time continuous‐state Markov process, which is constrained to its finite‐dimensional state space
S
by a pushing mechanism on the boundary ∂
S
of
S
. In the context of Operations Research and Management Science, the state space
S
is typically the nonnegative orthant. This article reviews several aspects of reflected Brownian motion on this orthant: its construction, its positive recurrence, and its stationary distribution.
Reformulation‐Linearization Technique for
MIPs
Authors: Sherali Hanif D.
Published: February 2011

The reformulation‐linearization technique (RLT) for mixed‐integer programs is an automatic model enhancement approach that generates a hierarchy of relaxations spanning the spectrum from the continuous linear programming (LP) relaxation to the convex hull of feasible solutions. This process is applicable to both 0‐1 as well as general discrete programs, and can be further augmented through the use of classes of semidefinite cuts. Often, the first‐level relaxation itself provides a sufficiently tight model reformulation that significantly improves problem solvability. The RLT procedure also offers a unifying framework for solving continuous nonconvex factorable optimization problems to global optimality.
Reinforcement Learning Algorithms forMDPs
Authors: Szepesvári Csaba
Published: February 2011

Reinforcement learning is a learning paradigm concerned with learning to control a system so as to maximize a numerical performance measure that expresses a long‐term objective. The goal in reinforcement learning is to develop efficient learning algorithms, as well as to understand the algorithms' merits and limitations. In this article we focus on a few selected algorithms of reinforcement learning which build on the powerful theory of dynamic programming.
Relationship among
B
enders,
D
antzig–
W
olfe, and
L
agrangian Optimization
Authors: Lim Churlzu
Published: February 2011

In this article, we present the equivalence of Benders, Dantzig–Wolfe, and Lagrangian optimization methods for solving linear programs. In particular, we illustrate that applying Dantzig–Wolfe decomposition for solving a linear program is equivalent to employing Benders decomposition to solve its dual linear program, which is in turn equivalent to implementing a cutting plane method to solve its Lagrangian dual problem. We first demonstrate this equivalence when solving a simply structured linear program having a bounded feasible region, and then extend the results to more general cases such as an unbounded feasible region and block diagonal structure.
Retrial Queues
Authors: Artalejo Jesús R.
Published: February 2011

This article surveys the main results and methods for retrial queueing systems. Since the closed‐form results are reduced to a few particular models, this article distinguish between explicit analytical methods and approximate and computational solutions. Although the main focus on the
M
/
M
/
c
and
M
/
G
/1 retrial queues, many other retrial models are also presented. Emphasis is on the limiting distribution of the system state and the waiting time, but other interesting performance descriptors are also discussed.
Revenue Management with Incomplete Demand Information
Authors: Araman Victor F. , Caldentey René
Published: February 2011

Consider a seller who is endowed with a fixed number of units of a product that he/she can sell to a price‐sensitive and stochastically arriving stream of consumers during a finite time horizon. The seller has incomplete demand information, that is, there are some characteristics of the demand process (e.g., the arrival rate or the price elasticity) that he/she does not know with certainty. The seller's problem is to dynamically adjust the product's price to maximize the expected revenues he/she can collect if no replenishment is possible during the selling season.