bluuebunny/crossref_metadata_2025 huggingface dataset:
Selective Support Vector Machines
Authors: Seref Onur
Published: February 2011

Selective support vector machines are a generalization of support vector machine (SVM) classifiers. In the selective SVM classification, there arenmutually exclusive setsXi,i = 1, …,n, of positive and negative labeled pattern vectors of dimensiond, such that all pattern vectorsxi,k,k = 1, …, |Xi| have the same class labelyi ∈ {1,  − 1}. Only one pattern vector from each set is to be chosen such that the margin between the selected positive and negative pattern vectors is maximized. This problem can be formulated as a quadratic mixed 0‐1 programming problem, which is a generalization of the standard SVM classification formulation and it is NP‐hard. An alternative convex quadratic programming formulation based on the restricted free slack concept can be used to find good solutions. The alternative formulation provides flexibility to the separating hyperplane and helps identify the pattern vectors with a large margin. This formulation can be used in an iterative elimination or a direct selection method with applications for simulated and real‐life data.
Self‐Dual Embedding Technique for Linear Optimization
Authors: Roos Kees
Published: February 2011

In the article titled

Central Path and Barrier Algorithms for Linear Programs

in this encyclopedia, the main ideas underlying the modern interior‐point methods are presented. In these methods the central path plays a crucial role. To start these methods one needs a starting point on or close to the central path. Given such a point, a variant of Newton's method is used to generate a sequence of iterates that converges to an optimal solution of the problem. In this section, we show how to get into the situation that a starting point on the central path is known. This goes via the construction of an artificial problem whose solution either yields an optimal solution for a given problem, or detects that no such solution exists.
Semidefinite Optimization Applications
Authors: Man–Cho So Anthony
Published: February 2011

Owing to its versatile model power and wide applicability, semidefinite programming (SDP) has received a lot of attention of late in many communities. In this article, we will survey some recent applications of SDP, with a particular emphasis on semidefinite relaxations of hard optimization problems. We will also provide pointers to the literature, for further reading.
Sensitivity Analysis of Simulation Models
Authors: Kleijnen Jack P.C.
Published: February 2011

This contribution presents an overview of sensitivity analysis of simulation models, including the estimation of gradients. It covers classic designs and their corresponding metamodels, namely, resolution‐III designs including fractional‐factorial two‐level designs for first‐order polynomial metamodels, resolution‐IV and resolution‐V designs for metamodels augmented with two‐factor interactions, and designs for second‐degree polynomial metamodels including central composite designs. It also reviews factor screening for simulation models with very many factors, focusing on the so‐calledsequential bifurcationmethod. Furthermore, it reviews Kriging metamodels and their designs. It points out that sensitivity analysis may also aim at the optimization of the simulated system, allowing multiple random simulation outputs.
Service Outsourcing
Authors: Zhou Yong‐Pin , Ren Zhong Justin
Published: February 2011

This article reviews the operations management (OM) research on service outsourcing, a common practice among current businesses. We focus on recent literature in three areas: capacity planning and supplier coordination, service outsourcing under information asymmetry, and quality concerns. Additionally, a mathematical framework is presented that can be used to analyze service outsourcing supply chains. We conclude with discussions on some promising future research areas.
Shipper And Carrier Collaboration
Authors: Ergun Özlem , Gui Luyi , Houghtalen Lori , Özener Okan Örsan
Published: February 2011

Collaboration among shippers and carriers in the transportation industry facilitates more efficient and cost‐effective business solutions that cannot be accomplished by companies operating alone, due to the economies of scope and scale. This article surveys the problem of designing and managing collaborative initiatives to promote both the overall efficiency and the stability of a transportation alliance. We discuss three management mechanisms, each requiring different levels of central coordination and information sharing among the participating entities, and yielding different levels of guaranteed social efficiency and coalition stability. We show that by taking into account the economies of scope and scale that arise in collaboration, a fair and efficient mechanism with limited central intervention can be designed based on analytical tools, such as those in network optimization theory, cooperative game theory, and algorithmic mechanism design. We provide an overview of the existing literature on the topic and discuss the business implications of the results, as well as point out some future research directions.
Simplex‐BasedLPSolvers
Authors: Maros István
Published: February 2011

The simplex method is widely used to solve linear programming problems in diverse application areas. It is used as a stand‐alone solver and also as the computational engine of the solution of other optimization problems. The emerging problems tend to be large to very large. Practical solution of such problems requires sophisticated implementation of the simplex method. This article gives an account of the most important developments that have enabled the simplex method to become a reliable, efficient, and flexible solver.
Simulated Annealing
Authors: Wierzchoń Sławomir T.
Published: February 2011

Simulated annealing (SA) is a popular metaheuristic proposed for finding global minimum of a function possessing many local minima. It was inspired by the annealing technique used in metallurgy. In the article, both the theoretical and implementational aspects of SA are discussed. First, main notions from the field of Markov chains are reviewed and the Metropolis sampling algorithm is precisely described. This algorithm, implementing “annealing” at fixed temperature, is the main building block of the SA algorithm. Variants of SA devoted to combinatorial and continuous optimization problems are discussed. Further modifications based on Lévy distributions and their extensions with so‐calledq‐normal distribution are mentioned. Lastly, the specializations of SA to multiobjective and stochastic optimization are briefly reviewed.
Decision‐Theoretic Foundations of Simulation Optimization
Authors: Frazier Peter I.
Published: February 2011

In simulation optimization, a task appearing frequently in applications, we wish to find a set of inputs to a simulator that causes its output to be maximal in some sense. Within any simulation optimization algorithm, we must make a sequence of decisions about which input to test at each point in time. The problem of making this sequence of decisions so as to discover a near‐optimal point as quickly as possible may be understood within a decision‐theoretic framework. We describe this decision‐theoretic framework in the context of two problems: ranking and selection and Bayesian global optimization. This decision‐theoretic framework provides both a way of better understanding existing algorithms, and a path to developing new algorithms.
Single Machine Scheduling
Authors: Geismar Neil
Published: February 2011

The single machine scheduling problem is foundational to the study of production scheduling in general. This article describes four basic problems and their solution methods: total weighted completion time, maximum of nondecreasing cost functions (which includes the maximum lateness problem and the problem with precedence constraints), weighted number of tardy jobs, and total weighted tardiness. Additional problems considered include those with both earliness and tardiness penalties, and those with release dates and preemptions.
Soccer/World Football
Authors: Brillinger David R.
Published: February 2011

This article constitutes a review of magagement science, operations research, and statistics as they arise in the study of data arising from the world of soccer/football. The data may have been collected during a game, may be summaries after games, or after a season, or after a tournament, or over many years. The main sections of the article include Data Collection and Descriptive Analyses, Stochastic Modeling (with subsections Between Game Modeling and Within Game Modeling), Ranking, Tournaments and Scheduling, Game Theory, and Economics and Management. The reference list contains 167 books and articles. The analytic study of the field has reached maturity following the contributions of many individuals and institutions.
Software for Solving Noncooperative Strategic form Games
Authors: Turocy Theodore L.
Published: February 2011

The problem of finding Nash equilibria in noncooperative strategic form games can be expressed using several equivalent formulations. These formulations admit a variety of algorithmic approaches. This article summarizes the current state of available software implementations for solving the Nash equilibrium problem, and outlines general advice for approaching the analysis of any given game.
Solving Influence Diagrams: Exact Algorithms
Authors: Shachter Ross D. , Bhattacharjya Debarun
Published: February 2011

Influence diagrams were developed as a graphical representation for formulating a decision analysis model, facilitating communication between the decision maker and the analyst. We show several approaches for evaluating influence diagrams, determining the optimal strategy for the decision maker and the value or certain equivalent of the decision situation when that optimal strategy is applied. They can be converted into decision trees, evaluated directly as influence diagrams, or converted into another graphical model, a rooted cluster tree, for analysis.
Standby Redundant Systems
Authors: Distefano Salvatore
Published: February 2011

In order to conjugate the increasing demand of reliability, dependability, and safety with the costs of redundancy, several efforts have been made. The most promising and effective solution, guaranteeing the desired trade‐offs among quality and cost requirements, is the standby redundancy. The main goal of standby redundancy is to improve system reliability and availability by exploiting standby components. Standby redundant systems are the technical implementation of the standby redundancy view.

This article provides an overview of the concepts related to standby redundant systems. The reliability of standby redundant systems is evaluated obtaining specific formulas, and an overview of possible standby redundant systems management techniques, issues, and challenges is provided.
Statistical Process Control
Authors: Fogliatto Flavio Sanson , Anzanello Michel J.
Published: February 2011

Production processes aimed at meeting customers' requirements need to be stable or repeatable. More specifically, the process must yield outputs around the target or nominal specifications of the product's quality characteristics with little or no variability. Statistical process control (SPC), or Statistical quality control (SQC), act as a set of powerful tools for improving process performance and achieving process stability. In this article we briefly present the fundamentals of some of these tools, namely Control charts and capability indices.
Stochastic Network Interdiction
Authors: Morton David P.
Published: February 2011

We describe discrete stochastic network interdiction of shortest‐path, and maximum‐reliability‐path, networks. A nested “max–min” model is reformulated using duality and, if necessary, an equivalent penalty‐based model. The resulting mixed‐integer program is then amenable to solution by standard solvers. Special‐purpose decomposition algorithms, and accompanying valid inequalities, are also developed, which permit solution of larger scale problem instances. Throughout the article, we point to important models that arise when key assumptions in our formulations are modified.
Subjective Probability
Authors: Al‐Najjar Nabil I. , de Castro Luciano
Published: February 2011

We provide an overview of the idea of subjective probability and its foundational role in decision making and modern management sciences. We highlight the role of Savage's theory as an organizing methodology to guide and constrain our modeling of choice under uncertainty, rather than a substantive statement subject to refutations by experimental or psychological evidence.
Supply Chain Risk Management
Authors: Sodhi ManMohan S. , Tang Christopher S.
Published: February 2011

We present different aspects of supply chain risk management. In doing so, we bring together different strands in the literature from supply chain management, enterprise risk management, and crisis management/business continuity, areas that are themselves multidisciplinary. As such, supply chain management is still an emerging area and we present these diverse strands from an enterprise risk management perspective in four categories: (i) identifying risk, (ii) assessing risk (iii) mitigating risk, and (iv) responding to risk incidents, including communication.
Support Vector Machines for Classification
Authors: Gilbert Robin C. , Trafalis Theodore B. , Adrianto Indra
Published: February 2011

In this article, we introduce the subject of support vector machines (SVMs), describing their applications to binary and multiclass classification as well as different SVM formulations that are used in such supervised learning problems. This article is not exhaustive and many approaches have not been considered. More detailed treatments are discussed in the books by Abe, Cristianini and Shawe‐Taylor, Schölkopf, and Smola and Vapnik.
Symmetry Handling in Mixed‐Integer Programming
Authors: Ostrowski Jim
Published: February 2011

This article focuses on solving integer programs whose feasible regions are highly symmetric. Symmetry has long been considered a curse in integer programming, and auxiliary (often extended) formulations are sought to reduce the amount of symmetry in an integer linear programming (ILP) formulation. The approach taken in this article describes methods that seek toexploitthe symmetry, not avoid it by reformulation.

A standard method for solving integer programs isbranch‐and‐bound. In branch‐and‐bound, the set of feasible solutions is partitioned, forming more easily solved subproblems. The presence of symmetry means that many of these subproblems are equivalent in a sense we describe later. Only one member of each collection of equivalent subproblems needs to be solved. Failure to recognize that many subproblems are equivalent results in a waste of computational effort that can render an instance unsolvable by branch‐and‐bound. In this article, we describe methods that use the symmetry of the problem formulation to reduce the size of the feasible region.
System Availability
Authors: Gaver Donald P. , Jacobs Patricia A.
Published: February 2011

Availability
describes and quantifies the propensity of a system to be functionally operative upon demand. Example systems include a missile, torpedo, aircraft, or wheeled or tracked vehicles, civilian as well as military, but also an entire computer communication system, as in “cloud computing.” It increases if failure‐free operating times between failures (“up times”) become long, and decreases if following failure or anticipatory removal, logistics delays and repair (“down times”) are protracted. This article summarizes the general availability concept and discusses the limitation of
operational availability
(defined as the probability of being operational at a particular time) suggesting that
mission availability
(probability of being operational at a time and throughout a subsequent mission) is often more useful and appropriate. The important distinction between these is treated later in this chapter.
The Condition‐Based Paradigm
Authors: Meeker William Q. , Hong Yili , Escobar Luis A.
Published: February 2011

The objective of this article is to introduce the condition‐based paradigm for reliability and the use of condition information to assess and maintain product reliability. Repeated measurement of product condition parameters, also known as degradation data, can be used to assess the product reliability and make decisions about product maintenance. After describing several examples of degradation data, we introduce some statistical models and methods, including random effects models and stochastic models, for analyzing degradation data. These methods are illustrated with real examples. We conclude the article with a discussion of continuous monitoring of product condition and system health. Suggestions for further reading are also given.
The Failure‐Based Paradigm
Authors: Meeker William Q. , Hong Yili , Escobar Luis A.
Published: February 2011

The objective of this article is to describe the failure‐based paradigm for reliability and explain the use of failure‐time data to assess product reliability. After discussing the main sources and characteristics of failure‐time data, we introduce some basic reliability metrics such as failure probability and hazard rate and the nonparametric and parametric estimation of these or related metrics. We present a brief introduction to regression methods to incorporate explanatory variables in the analysis of reliability data. The analysis of data with multiple failure modes (competing risks) is illustrated with an example. The article concludes with a discussion of some trends in the next generation of failure‐time reliability data. Materials for further reading are provided.
The
M
/
G
/1 Queue
Authors: Boxma Onno J.
Published: February 2011

The
M
/
G
/1 queue is a single‐server queue, to which customers arrive according to a Poisson process, requiring generally distributed service times. It is one of the most classical and best‐understood queueing systems. We review some of its key properties, focusing on queue lengths, on waiting and sojourn times, and on the busy period. We mainly consider the First Come First Served service discipline, but some other disciplines are also briefly discussed.
The
M
/
G
/∞ Queue
Authors: Gautam Natarajan
Published: February 2011

The objective of this article is to describe the
M
/
G
/∞ system, where the arrivals are according to a Poisson process, the service times are independent and identically distributed, and there are an infinite number of servers. We analyze the number in the system under both transient and steady‐state conditions. We describe results for the busy period distribution of as well as departure from an
M
/
G
/∞ queue. We finally study an extension in terms of considering time‐varying arrivals.
The

M

/

M

/∞ Queue
Authors: D'Auria Bernardo
Published: February 2011

In this article, we describe the
M
/
M
/∞ queueing system, the simplest example of an infinite server queue in which the customers arrive according to a homogeneous Poisson process and get served immediately. The system has no waiting line and its customers are served in an exponential time and leave the system as soon as their service demand is fully met. Applications of this model can be found in many different fields such as physics, telecommunications, and vehicle traffic. The main advantage of the model, thanks to the independence of customers' behavior across the whole queueing process, is the simplicity of its mathematical description. The
M
/
M
/∞ queue is always stable and the stationary distribution of the number of customers in the system is a Poisson random variable. We summarize the main characteristic measures associated with the queue.
Total Expected Discounted Reward
MDPS
: Policy Iteration Algorithm
Authors: Icten Z. Gozde , Karademir Serdar , Maillart Lisa M.
Published: February 2011

This article presents the steps and discusses properties of the policy iteration algorithm and the modified policy iteration algorithm for discounted infinite horizon Markov decision processes. Two small numerical examples are included to demonstrate how to implement the algorithms.
Total Expected Discounted RewardMDPs: Value Iteration Algorithm
Authors: Bountourelis Theologos
Published: February 2011

In this article, we discuss the total expected discounted reward Markov decision problem and its popular algorithmic solution, the value iteration algorithm. We formally state the problem, characterize the optimal policy, and describe the algorithm in its simplest form. We conclude with a discussion on the problem assumptions, the more advanced versions of the algorithm, and highlight the relevant literature.
Search Games
Authors: Gal Shmuel
Published: February 2011

This article surveys the area of search games with immobile and mobile hider. The search space is either a graph, a bounded domain or an unbounded set. The search process is presented as a two‐player zero‐sum game between the searcher and the hider. The searcher moves along a continuous trajectory and the cost function is the time needed to find the hider. An overview is presented with emphasis on general results concerning minimax search trajectories and optimal search strategies.
TPZS
Applications: Blotto Games
Authors: Washburn Alan R.
Published: February 2011

Blotto games are a class of two‐person zero–sum game where each player must allocate a budget of some kind among several independent areas. In each area, the payoff depends only on the two allocations to that area, and the total payoff is the sum of the individual area payoffs. The class has properties that permit the solution of large games and includes numerous military applications. This article discusses applications and solution methods.
Traffic Network Analysis and Design
Authors: Boyles Stephen D. , Waller S. Travis
Published: February 2011

This article provides an overview of basic traffic network analysis methods, focusing on the central traffic assignment problem. Formulations of the user‐optimal and system‐optimal assignment problems are given and link‐based, path‐based, and origin‐based solution methods are presented. Congestion pricing and network design are then presented as two applications of these models. Finally, a brief treatment is given to extensions of the basic model: stochastic user equilibrium, elastic demand, uncertain costs, and dynamic traffic assignment. A discussion of seminal papers in the field is provided for historical context and further reference.
Transportation Algorithms
Authors: Altner Douglas S. , Brooks J. Paul
Published: February 2011

The transportation problem requires, given a set of suppliers and a set of customers, finding a minimum cost plan to determine how many goods each supplier should send to each customer. Each customer's minimum requirements must be satisfied without exceeding the supply of any supplier. This problem has a plethora of industrial and military applications including applications beyond modeling the physical transporting of goods. In this article, we present the transportation problem; discuss its early history, properties, and relationship to other problems; describe the well‐known transportation simplex method; and survey the literature on transportation algorithms.
Transportation Resource Management
Authors: Kunnumkal Sumit , Topaloglu Huseyin
Published: February 2011

In this article, we describe a variety of modeling and solution approaches for transportation resource management problems. The solution approaches that we propose either build on deterministic linear programming formulations, or formulate the problem as a dynamic program and use tractable approximations to the value functions. We describe two classes of methods to construct approximations to the value functions. The first class of methods relax certain constraints in the dynamic programming formulation of the problem by associating Lagrange multipliers with them, in which case, we can solve the relaxed dynamic program by concentrating on one location at a time. The second class of methods use a stochastic approximation idea along with sampled trajectories of the system to iteratively update and improve the value function approximations. After describing several solution approaches, we provide a flexible paradigm that is useful for modeling and communicating complex resource management problems. Our numerical experiments demonstrate the benefits from using models that explicitly address the randomness in resource management problems.
Treewidth, Tree Decompositions, and Brambles
Authors: Koster Arie M.C.A.
Published: February 2011

The notions of tree decomposition and treewidth play an important role in the design and analysis of algorithms for combinatorial optimization problems. The notion of a bramble can be used to find a lower bound on the treewidth of a graph. In this article we review the most important results for treewidth, tree decompositions, and brambles, both from a theoretical and practical point of view.
Triage in the Aftermath of Mass‐Casualty Incidents
Authors: Argon Nilay Tanik , Ziya Serhan , Winslow James E.
Published: February 2011

Mass‐casualty incidents, such as plane crashes and terrorist attacks, take place rarely but when they happen they may result in a massive number of casualties with severe injuries requiring immediate medical attention. In the aftermath of such an event, medical resources are typically overwhelmed by the sudden jump in demand and hence they need to be rationed in some way to minimize the number of deaths and permanent injuries. This rationing process that determines the priorities according to which patients are given access to the limited resources is calledtriage. This chapter provides a review of the operations research literature on patient triage and prioritization decisions in the aftermath of mass‐casualty incidents. In the literature, there are two lines of research that take two different approaches to the problem but with similar conclusions. The most important conclusion is that mass‐casualty triage systems should take into account the number of casualties and the capacity of resources to save the maximum number of lives possible. Furthermore, an effective rule that categorizes the patients based on their service requirements, chances of survival, and patterns of health deterioration is essential for the success of the emergency response effort.
Interior Point Methods for Nonlinear Programs
Authors: Peng Jiming , Salahi Maziar
Published: February 2011

In the past decades, there has been substantial progress in the study of interior point methods for solving linear and nonlinear programming problems arising from various real‐world applications. Several powerful software packages have been developed that are now widely used as one of the working horses by many practitioners. In this article, we give a brief overview of interior point algorithms for solving nonlinear programming problems (NLPs).
Heuristics for the Traveling Salesman Problem
Authors: Kurz Mary E.
Published: February 2011

The article considers heuristics (methods to create feasible solutions) for the traveling salesman problem (TSP). We differentiate between
constructive
heuristics which create feasible solutions from no solution, and
improvement
heuristics which potentially create new feasible solutions from existing feasible solutions. While the list of published heuristics and variants of the TSP is nearly unlimited, this article focuses on an overview of the most enduring methods for the TSP with an unrestricted distance matrix.
Bilevel Network Interdiction Models: Formulations and Solutions
Authors: Wood R. Kevin
Published: February 2011

Thebilevel network‐interdiction problem(BNI) models the effective use of limited resources, by an “interdictor,” to attack a network that an “enemy” may use to the interdictor's disadvantage. BNI is a two‐person, zero‐sum, sequential‐play (Stackelberg) game with two stages: in the first stage, the interdictor attacks components of his enemy's network, that is, nodes and or/arcs; and in the second stage the enemy observes the damage caused by the attack and operates the damaged network so as to optimize a measure of functionality such as throughput, output or cost. For example, using a limited number of aerial sorties to attack and destroy production and distribution assets, an interdictor may wish to minimize the maximum “flow” of munitions that his enemy can produce and move to a battlefront. This article models interdictions with binary variables and simple constraints; solution of an optimization model, often a linear program, represents optimal network operation by the enemy. Simple models can be converted mixed‐integer programs, but solution methods based on decomposition may be preferred for efficiency and generality.
Optimization of Public Transportation Systems
Authors: Carlos Muñoz Juan , Giesen Ricardo
Published: February 2011

Public transportation systems are intrinsically associated with a more sustainable motorized urban mobility. However, many cities struggle to offer their citizens a system providing high level of service. This article introduces the complexity involved with designing and operating a transit system going from the high‐level strategic decisions to the low‐level control mechanisms.
Variational Inequalities
Authors: Konnov Igor V.
Published: February 2011

We consider variational inequality problems in a finite‐dimensional space setting. We first describe existence and uniqueness results under norm monotonicity assumptions. Relations to some other general nonlinear problems are discussed. Then we describe basic solution methods utilizing the above monotonicity concepts and their convergence properties. Some extensions for the multivalued case are also discussed.
Variants ofBrownian Motion
Authors: Bhamidi Shankar , Greenwood Priscilla E.
Published: February 2011

Variants of Brownian motion and related processes arise in diverse contexts. Examples include scaling limits of discrete models like queueing networks, combinatorial structures such as random trees, physical models of particles diffusing through disordered media, and the evolution of stock process in finance. Here, we describe some of these variants, including reflected Brownian motion, geometric Brownian motion, the Brownian sheet, Brownian excursions, and fractional Brownian motion.
Vendor‐Managed Inventory
Authors: Fry Michael J.
Published: February 2011

Vendor‐managed inventory (VMI) programs transfer inventory control decisions from the retailer to the supplier. VMI programs rely on information sharing to transmit customer demand and current inventory information to the supplier. The supplier is then in charge of determining the timing and quantity of inventory deliveries to retailers. Most VMI programs contain an initiating contract that specifies elements of the agreement including performance metrics and payment terms. VMI programs have been shown to reduce supply chain costs through shipment consolidation and incentive alignment of decentralized supply chain agents. However, not all VMI programs result in supply chain savings. Even in those cases where VMI can result in system‐wide savings, care must be taken to create agreements that are preferable to both suppliers and retailers.
Very Large‐Scale Neighborhood Search
Authors: Altner Douglas S. , Ahuja Ravindra K. , Ergun Özlem , Orlin James B.
Published: February 2011

Many optimization problems that model the essential issues of important real‐world decision making are computationally intractable. Therefore, a practical approach for solving such problems is to employ heuristic techniques that find nearly optimal solutions within a reasonable amount of computation time.Improvement algorithmsgenerally start with a feasible solution and iteratively try to obtain a better solution. Neighborhood search algorithms, which are alternatively calledlocal search algorithms, are a wide class of improvement algorithms where at each iteration an improving solution is found by searching a “neighborhood” of the current solution. A critical issue in the design of a neighborhood search algorithm is defining what solutions constitute the neighborhood of a solution. As a rule of thumb, the larger the neighborhood, the better is the quality of the locally optimal solutions, including the final solution selected upon termination. Similarly, the larger the neighborhood, the longer it takes to search the neighborhood. Thus, a larger neighborhood does not necessarily produce a more effective heuristic unless one can search the larger neighborhood efficiently. This article concentrates on neighborhood search algorithms where the size of the neighborhood is “very large” with respect to the size of the input data and the neighborhood can be searched efficiently. We survey three broad classes of very large‐scale neighborhood (VLSN) search algorithms: variable‐depth methods in which large neighborhoods are searched heuristically, large neighborhoods that are searched by solving a constrained minimum–cost flow problem, and other situations that give rise to efficiently searchable large neighborhoods.
Cognitive Mapping and Strategic Options Development and Analysis (SODA)
Authors: Georgiou Ion
Published: February 2011

Strategic options development and analysis (SODA) is a problem structuring method that incorporates a particular approach to cognitive mapping that draws from the psychological theory of personal constructs. What differentiates it from all other cognitive mapping approaches is its use of bipolar constructs that enable the clarification of meaning. Besides their qualitative content, the structure of SODA maps allow for a range of quantitative analyses, especially through the use of graph theory. This article describes the contemporary context of cognitive mapping, introduces the design and analysis of SODA maps, and concludes with a critical appreciation that identifies three significant areas for further research.
Constraint Qualifications
Authors: Solodov Mikhail V.
Published: February 2011

We discuss assumptions on the constraint functions that allow constructive description of the geometry of a given set around a given point in terms of the constraints derivatives. Consequences for characterizing solutions of variational and optimization problems are discussed. In the optimization case, these include primal and primal‐dual first‐ and second‐order necessary optimality conditions.
Lagrangian Optimization Methods for Nonlinear Programming
Authors: Nedić Angelia
Published: February 2011

This article provides an overview of Lagrangian relaxation and its duality theory as applied to nonlinear optimization problems. Basic duality properties and Lagrangian saddle point results are discussed. Also, the algorithms for solving saddle point problems and dual problems are surveyed.
Subgradient Optimization
Authors: Nesterov Yurii
Published: February 2011

We discuss the numerical schemes and complexity of nonsmooth optimization problems, both in convex and nonconvex variants. For nonconvex problems, we present the concepts of Clarke subdifferential and lexicographic differentiation. The main computational approaches are given. On the other hand, we show NP‐hardness of the simplest nonsmooth and nonconvex optimization problem. For convex problems, we describe the primal and dual subgradient methods, the ellipsoid method, and other cutting plane schemes. Corresponding complexity bound are also presented.
Primal–Dual Methods for Nonlinear Constrained Optimization
Authors: Griva Igor , Polyak Roman A.
Published: February 2011

The article describes interior‐ and exterior‐point primal–dual methods. The interior‐point methods are related to sequential unconstrained minimization techniques, while the exterior‐point methods are based on nonlinear rescaling and augmented Lagrangian theory. One of the main advantages of the primal–dual methods described in the article is their asymptotic quadratic convergence under the standard second‐order optimality conditions.
Strategic Customer Behavior in a Single Server Queue
Authors: Haviv Moshe
Published: February 2011

The purpose of this article is to introduce the reader to the topic of strategic behavior of customers in queues. We assume that customers individually decide on issues such as whether or not to join the queue, whether or not to renege from a queue after waiting for a while, or whether or not to pay some fee in order to belong to a higher priority class. For some examples, we define the appropriate noncooperative games and look for their Nash equilibria. We restrict ourselves to M/M/1 queues with homogeneous customers (with respect to their cost/reward parameters).
Optimizing the Aviation Checkpoint Process to Enhance Security and Expedite Screening
Authors: Lee Adrian J. , Jacobson Sheldon H.
Published: February 2011

A queueing analysis is used to model the sequential screening of passengers at an airport security checkpoint. A multiobjective, nonlinear optimization problem is then formulated to balance the expected number of true alarms with the expected amount of time a passenger spends in the security system, thereby enhancing security operations, while also improving passenger throughput. Both multilevel security systems and those comprising primary and secondary levels of screening are analyzed to demonstrate the benefits from implementing each security system structure. Applying optimization techniques to the design of aviation passenger screening policies provides the means to both increase security and expedite screening by efficiently and effectively utilizing available screening resources.
Analytics in Retail
Authors: Klabjan Diego , Jiang Yan , Williams Loren
Published: February 2011

Retailing has always been an active research area for OR/MS researchers. Nowadays, the collaboration between retail practitioners and academic researchers yield more and more useful analytical models and solution algorithms to tackle complicated retail problems. This article illustrates two types of commonly‐used analytic in retail practice, namely forecasting and optimization, using two models that are in production use or development in retail business settings.
Uncertainty in Forest Production Planning
Authors: Alonso‐Ayuso Antonio , Escudero Laureano F. , Guignard Monique , Quinteros Martin , Weintraub Andres
Published: February 2011

The forest harvest and road construction planning problem consists fundamentally of managing land designated for timber production and divided into harvest cells. For each time period, the planner must decide which cells to cut and what access roads to build in order to maximize expected net profit under uncertainty in the timber price. By introducing a multistage stochastic mixed 0–1 programming model, the planner is able to make more robust decisions based on a range of timber price scenarios over time, maximizing the expected value subject to the satisfaction of the constraints in all scenarios and satisfying the so‐called nonanticipativity constraints, instead of merely analyzing a single average scenario. A case study is presented based on the Chilean forest property Los Copihues as a proof of concept.
Using Operations Research to Plan Natural Gas Production and Transportation on the
N
orwegian Continental Shelf
Authors: Nørstebø Vibeke Stærkebye , Schütz Peter , Fodstad Marte , Hellemo Lars , Midthun Kjetil , Rømo Frode , Tomasgard Asgeir
Published: February 2011

Decisions regarding natural gas production, processing, and transportation in interconnected networks depend on each other. Changes in the system affect both its capacity and flexibility. We discuss the main elements of the GassOpt model, an application developed to ensure optimal operation of this network by considering the complete system, its integration, and to provide valuable insights in the dependencies between the different system elements. The objective of GassOpt is to maximize the total flow of natural gas from the North Sea to the customers. The model determines the optimal routing, processing, and blending of natural gas ensuring that demand and quality constraints are satisfied. The application is used by natural gas producers and network operators to plan their activities, to evaluate the operational consequences of plans and investment decisions, and to maximize the value of their operations.
Procurement Contracts
Authors: Bassok Yehuda
Published: February 2011

In this article, we discuss supply contracts. We consider environments in which some type of uncertainty plays an important role. In general, the main objective of supply contracts is to coordinate the supply chain and to (i) ensure that buyers are able to meet their customers' uncertain and changing demand, (ii) provide mechanisms so that suppliers (manufacturers) and buyer share system's risks and costs (more specifically, ensure that suppliers do not assume the entire risk of buffering raw materials and finished goods to meet the final demand for goods), and (iii) provide incentives for suppliers (manufacturers) to build enough capacity.

We discuss several different supply contracts. All contracts balance between the flexibility of the buyer adapting to changing market conditions and the stability of the production environment. These contracts differ in their assumptions and complexities. The main differences between these supply contracts are that some are single‐period contracts; the Buy Back contract is a good example of the above. Others are multiperiod contracts and they capture the dynamics of a long horizon. The Periodical Commitments and Flexibility contract is a good example of the multiperiod models. The different contracts consider different mechanism to balance flexibility and stability: Fixed delivery contracts ensure that the sellers deliver a fixed quantity every period, while the option contracts use options to achieve the same objective. The Periodical Commitments and Flexibility contract provides buyers with limited flexibility to change previously made commitments.
Stochastic Search Methods for Global Optimization
Authors: Zabinsky Zelda B.
Published: February 2011

Stochastic search methods, also known as random search algorithms, are popular for ill‐structured global optimization problems because they are straightforward to implement and usually find a relatively good solution quickly. These algorithms have been inspired by physics, such as simulated annealing and interacting particle algorithms, as well as by biology, including genetic algorithms, evolutionary programming, particle swarm, and ant colony optimization. This article highlights the use of a Markov chain Monte Carlo sampling method called Hit‐and‐Run in random search algorithms for global optimization.
Backtrack Search Techniques And Heuristics
Authors: Lecoutre Christophe
Published: February 2011

Satisfying a set of constraints is known as an instance of the constraint satisfaction problem (CSP), which is the subject of intense research in both artificial intelligence and operations research. Practical solution of CSP instances usually involves backtrack search. This is a complete approach that performs an exhaustive exploration of the search space of the instance to be solved. There have been considerable efforts during the last three decades to maximize the practical efficiency of backtrack search, relying on the concepts of constraint propagation, intelligent backtracking, restarting policy, variable (and value) ordering heuristic, and so on. In particular, the development of general‐purpose adaptive heuristics has shown impressive progress in guiding search.
Forecasting Approaches for the High‐Tech Industry
Authors: Gilliland Michael
Published: February 2011

Challenges in the high‐tech industry, such as long supply chain lead times, short product lifecycles, and frequent new product introductions, make it unrealistic to expect highly accurate forecasting. However, there are methods to help high‐tech organizations deal with this extra uncertainty, and this article focuses on two such methods: the “structured analogy” approach to new product forecasting, and forecast value added (FVA) analysis. The structured analogy approach utilizes data visualization and analytical software to augment “forecasting by analogy” (i.e., like items) with structured judgment. FVA analysis is a method adopted across a broad range of industries for identifying wasteful and bad practices in the forecasting process and is consistent with the “lean” approach to supply chain management. While neither method can guarantee highly accurate forecasts (nothing can do that), these methods help high‐tech organizations forecast more efficiently (in less time, at less cost), more effectively (by eliminating process steps that just make the forecast worse), and to better understand and deal with the uncertainties and risks.
Allocation Games
Authors: Roberson Brian
Published: February 2011

There are a number of important applications in the economic, military, and political sciences that may be characterized as resource allocation games in which budget‐constrained players strategically allocate resources across multiple simultaneous contests. Partly because it is a foundational problem that is well suited for abstract theoretical modeling, multidimensional strategic resource allocation was one of the first problems examined in modern game theory. Borel (1921) formulates this problem as a constant‐sum game involving two symmetric players who each allocate a fixed amount of resources across a finite number of contests. Each player must distribute their resources without knowing their opponent's distribution of resources. In each of the component contests, the player who allocates the higher level of resources wins the contest, and each player maximizes the sum of the wins across the individual contests. This chapter provides an introduction to this class of games (known asColonel Blotto games) with a focus on the intuition for the key results and briefly summarizes several of the recent developments in this literature including: non‐constant‐sum formulations of the Colonel Blotto game, additional restrictions on the strategy space, a simplified form of the Colonel Blotto game, and alternative objectives for the players.
Quality and Pricing Decisions
Authors: Chambers Chester
Published: February 2011

When firms decide to offer a product or service, they make integrated decisions regarding the characteristics of the product to be offered and the price that will be charged. These interrelated decisions are often referred to as
product positioning
. In this article, the topic within the contexts of several different settings are introduced. Research in this field can be parsed into groups based upon whether the focus is on a single firm acting as a monopolist or on multiple firms non‐cooperatively competing among themselves. The relevant works can also be grouped depending on how they handle the subject of production/delivery costs. Some works ignore all cost components. Another set of works includes only fixed costs, while a different set includes variable costs in an economic model. This note provides introductory illustrations regarding each of these settings and outlines major results in each problem category. While this work is not intended to be exhaustive, it does introduce seminal works in the field and explains several major findings. These findings include (i) a monopolist in settings in which costs are negligible or sunk will offer only the highest quality product possible and there is no need to offer a menu of items; (ii) a monopolist facing production costs is motivated to offer a menu of offerings to achieve some measure of price discrimination, and the range of offerings is wider than would be seen under perfect competition; (iii) duopolists sharing a market in the absence of cost will strive for maximum product differentiation; (iv) when only fixed costs are relevant the provider of the higher quality good makes the greater profit; and (v) when only variable costs are considered the provider of the lower quality good often makes the greater profit. This work also discusses several recent extensions of the seminal works, which relax key assumptions of earlier efforts. Finally, we end this article with a discussion of open questions in the field.