bluuebunny/crossref_metadata_2025_split huggingface dataset:
A Structural Clustering Algorithm for Large Networks
Authors: Xu Xiaowei 
Published: February 2011

AbstractNetworks such as the World Wide Web, social networks, and metabolic networks, which contain valuable information, draw increasing attention in scientific communities. Network clustering (or graph partitioning) is the discovery of underlying clusters of related vertices in networks. But, beyond organizing vertices into clusters of peers is the question of what role each vertex plays in the network. This article presents some new ways of uncovering underlying structures, including the roles that vertices play in the network. Identifying vertex roles is useful for applications such as viral marketing and epidemiology. For example, hubs are responsible for spreading ideas or disease. We applied our algorithm to analyze some real networks. The results demonstrate a superior performance over other methods such as modularity‐based algorithms.
Decomposition Algorithms for Two‐Stage Recourse Problems
Authors: Mayer János 
Published: February 2011

Abstract
In this article, decomposition methods for two‐stage linear recourse problems with a finite discrete distribution are discussed. First, we cover the L‐shaped decomposition method which represents a breakthrough concerning numerically efficient methods for solving two‐stage recourse problems. This algorithm was the basis for the development of several other decomposition methods. After giving an overview of these algorithms, we present regularized decomposition and stochastic decomposition in a more detailed fashion. Variance for recourse‐constrained problems and special cases including simple recourse with a random technology matrix are also considered. With reference to stochastic decomposition, the scope of which is not restricted to finite discrete distributions, algorithms for the continuous‐distribution case are discussed briefly with references to the literature.
Decomposition Methods for Integer Programming
Authors: Ralphs Ted K. , Galati Matthew V. 
Published: February 2011

Abstract
This article reviews both traditional and integrated decomposition methods for solving mixed‐integer linear programs. These methods attempt to exploit tractable substructures of the problem in order to obtain improved solution procedures. The goal is to derive improved methods of bounding the optimal solution value, which can then be used to drive a branch‐and‐bound algorithm. Such methods are the preferred solution approaches for a wide range of important models. To expose the desired substructure, a common approach is to relax a set of complicating constraints. This is the approach taken by the Dantzig–Wolfe decomposition, Lagrangian relaxation, and cutting‐plane methods. Substructure can also be exposed by relaxing the values of a set of variables, that is, considering restrictions of the original problem. This is the approach taken by Benders' decomposition. This article reviews decomposition methodologies based on relaxation of constraints and examines how they are used to solve mixed‐integer linear programs.
Definition and Examples of Continuous‐Time
M
arkov Chains
Authors: Uzun Evin 
Published: February 2011

Abstract
This article consists of definitions and examples of continuous‐time Markov chains (CTMCs). We first define a CTMC as a continuous‐time stochastic process that has a countable state space and the Markov property. Then, we restrict our attention to time‐homogenous CTMCs, for which we define the transition probability matrix. We further restrict our attention to regular CTMCs and provide an alternative definition of a CTMC. Next, we define the embedded discrete‐time Markov chain and the generator matrix of a CTMC and investigate the possible ways of characterizing a CTMC. We complete the definitions by defining the transition rate diagram of a CTMC. Finally, we conclude the article by providing examples of CTMCs.
Definition and Examples of
DTMCs
Authors: Gautam Natarajan 
Published: February 2011

Abstract

The objective of this article is to describe a special type of stochastic process called
discrete‐time Markov chain (DTMC)
. We first provide definitions for DTMCs using simple language as well as mathematics. Then, we describe a systematic technique to model a system as a DTMC. Finally, we provide examples to both illustrate the modeling technique and motivate the breadth of real‐world applications where DTMCs can be used.
Demand Responsive Transportation
Authors: Parragh Sophie N. , Doerner Karl F. , Hartl Richard F. 
Published: February 2011

AbstractDemand responsive transportation systems are flexible public transportation services in which vehicle routes and schedules are generated on the basis of user requests. User requests consist of pickup and delivery location pairs. Problems of this kind are known asdial‐a‐ride problems. Since people are subject to transportation, the consideration of user inconvenience plays a central role. User inconvenience can either be limited by constraints or it can be considered in the objective function. It is usually expressed in terms of time windows, taking care of punctual service and maximum user ride time constraints, limiting the time a user should spend on a vehicle. In this article we review and discuss modeling aspects and solution methods for static and dynamic variants of the dial‐a‐ride problem.
Design for Network Resiliency
Authors: Tortorella Michael 
Published: February 2011

Abstract“Network resiliency” has been used in common language for many years in a variety of contexts. The intent of the usage seems to always have included the notions that a resilient network is one that continues to deliver services in a satisfactory manner, despite possible disruptions in the network infrastructure and/or one that returns to normal operation quickly after a disturbance. In this article, we consider the former interpretation in detail. The notion of “satisfactory” obviously involves a matter of degree, so a consistent quantitative framework for network resiliency is proposed for the first interpretation. This article organizes and subsumes current streams of network resiliency thought by providing a generalization of the various notions that have been used in the past to describe network resiliency, and uses this generalization to create a quantitative framework for resiliency characterization. The key concepts are the notions of a network with associated delivery function and are of delivery importance. We discuss various design principles that promote greater network resiliency in the context of this framework. We introduce a network resiliency optimization scheme and briefly show how the network interdiction problem can be solved using the proposed network resiliency framework.
Disjunctive Programming
Authors: Balas Egon 
Published: February 2011

AbstractDisjunctive programming, founded in the early 1970s, extends linear programming from optimization over polyhedra to optimization over disjunctive sets, which are equivalent to unions of polyhedra. It provides the tools for dealing with this particular class of nonconvex problems, of which integer programs are a special case. A central result is that optimizing over a union ofqpolyhedra inn‐space is equivalent to solving a linear program inO(q * n)‐space. The key idea that a higher‐dimensional reformulation of a difficult optimization problem may yield a more manageable model is by now commonplace, but its first systematic application goes back to disjunctive programming. Another basic result is that an important class of disjunctive sets, including the feasible sets of mixed 0–1 programs (but not of general mixed integer programs), can be convexified sequentially, that is, their convex hull can be generated by imposing the disjunctions one by one at each step, generating the convex hull of the current set. These and related results have led to the development of numerous classes of cutting planes for mixed integer programs, among them lift‐and‐project cuts, which played a crucial role in revolutionizing the state of the art of integer programming during the 1990s.
Domination Problems
Authors: Shen Siqian 
Published: February 2011

AbstractIn this article, we focus on dominating set problems in graphs. We review the literature that analyzes domination from different aspects, including bounds for the domination number, the algorithmic complexity, and valid inequality chains associated with each domination variant. In particular, we discuss the relationship between domination, independence, and irredundance, and reveal the well‐known domination chain and its properties. As many domination‐related problems can be solved in polynomial time for certain types of graphs (e.g., trees), we summarize start‐of‐the‐art results of polynomial algorithms regarding the domination‐related parameters of graphs. We also describe applications such as wireless ad hoc networks, social networks, and broadcast domination in which domination or its variants can be suitably implemented, as well as associated approximation algorithms, in order to emphasize the importance of the domination in graphs from a practical perspective.
Dynamic Models for Robust Optimization
Authors: Düzgün Ruken , Thiele Aurélie 
Published: February 2011

AbstractThis article discusses recent developments in robust optimization, with a focus on dynamic models. Traditional techniques such as stochastic programming and dynamic programming face dimensionality issues as the size of the problem increases; furthermore, probability distributions are often difficult to accurately estimate. After robust optimization emerged as a tractable modeling framework in static optimization, researchers investigated its applicability to dynamic decision making under uncertainty. We provide an overview and discussion of their findings.
Learning with Dynamic Programming
Authors: Frazier Peter I. 
Published: February 2011

AbstractWe consider the role of dynamic programming in sequential learning problems. These problems require deciding which information to collect in order to best support later actions. Such problems are ubiquitous, appearing in simulation, global optimization, revenue management, and many other areas. Dynamic programming offers a coherent framework for understanding and solving Bayesian formulations of these problems. We present the dynamic programming formulation applied to a canonical problem, Bernoulli ranking and selection. We then review other sequential learning problems from the literature and the role of dynamic programming in their analysis.
Edgeworth Market Games: Price‐Taking and Efficiency
Authors: Chowdhury Prabal Roy 
Published: February 2011

AbstractThis article surveys the Edgeworth market game literature, which formalizes multiagent trading as a game. The key issues are two fold, whether, as the economy becomes large, (i) price‐taking emerges, and (ii) whether efficiency is obtained. The focus here is on production economies under partial equilibrium, where the two questions converge to a single one, that is if the equilibrium approximates the competitive one in the limit. We however also discuss related approaches to market games, in particular (i) the cooperative approach, (ii) the trading post literature, and (iii) Cournot competition under general equilibrium.
Multivariate Elicitation: Association, Copulae, and Graphical Models
Authors: Daneshkhah Alireza , Bedford Tim 
Published: February 2011

Abstract
In practical elicitation problems, we very often wish to elicit from the expert her knowledge about more than one uncertain quantity. When these are considered independent, the uncertainty about them is characterized simply by their marginal distributions; so it is sufficient to elicit the expert's knowledge about the quantities separately. When the independence assumption between the uncertain quantities of interest is not reasonable or has to be explored, the elicitation process becomes more complex. This is where we need to elicit information about the association between the variables in some way. Unfortunately, despite the growing literature about elicitation, this is an area where there is very little guidance to be found. In this article, we present some methods proposed in the literature to specify a multivariate distribution. We focus on the methods that use copulae and vines to construct a joint probability distribution. They enable us to build a multivariate distribution based on the elicited marginal distributions and their dependencies.
Ellipsoidal Algorithms
Authors: Takahashi Ricardo H. C. 
Published: February 2011

AbstractThis article reviews the ellipsoidal algorithms (EAs), starting from its working principles, and then presenting the basic EA and some deep cut variations in a constructive manner. The classes of problems for which the EAs are guaranteed to converge to the exact solutions (linear problems, convex problems, and quasi‐convex problems) are stated in first place. The general principle ofcutting‐plane branch‐and‐cutoperation, that is valid for such classes of problems, is presented. The basic EA is stated, as an instance of such principles, and the convergence properties of this version of EA are discussed. The basic EA is then reformulated, with the inclusion of thedeep cuts, which accelerate the convergence. Specific forms of deep cuts that can be applied to linear‐ and convex problems are presented. Some further implementation issues in EAs are briefly discussed, and some references are indicated.
Forecasting NonStationary Processes
Authors: Chien Jui‐Hong , Xanthopoulos Petros , Pardalos Panos M. , Tomaino Vera 
Published: February 2011

Abstract
Preprocessing and forecasting nonstationary time series has always been a difficult task. Depending on the methods and tools used, we extract different features from a process, and these features provide us with some routes for forecasting the evolution of a process. Forecasting has extensively and successfully been done for stationary processes. However, nonstationarity smears many convenient properties of stationarity. For forecasting, the conceptual gap between stationary and nonstationary processes must be bridged. Besides, more robust methods which are not easily influenced by the evolution of nonstationary characteristics should be used. In this article, we first familiarize the readers with the concept of local stationarity as the bridge between stationarity and nonstationarity, and then present both parametric and nonparametric methods for nonstationary process preprocessing. Finally, prediction algorithms based on parametric and nonparametric concepts are introduced.
Formulating GoodMILPModels
Authors: Hooker John N. 
Published: February 2011

AbstractWriting good models is essential to harnessing MILP solution technology. Due to an underlying theorem that characterizes MILP representability, MILP modeling involves identifying two types of structures in a problem: knapsack constraints and choices between discrete alternatives. This article illustrates the modeling process with a series of examples. They include capital budgeting, freight transport, set packing/covering/partitioning, airline crew rostering, facility location, fixed charges, lot sizing, and package delivery. Piecewise linear modeling, logical conditions, symmetry, special ordered sets, indicator constraints, and semicontinuous variables are also discussed.
Geometric Programming
Authors: Rajgopal Jayant 
Published: February 2011

AbstractGeometric programming (GP) constitutes a special class of nonlinear optimization problems involving objective and constraint functions that are stated in the form of generalized polynomials. While the field is only about 50 years old, it has been studied extensively. This article reviews the important theoretical and computational aspects of GP and also discusses extensions to the original form that have been developed over the years.
Heuristics in Mixed Integer Programming
Authors: Fischetti Matteo , Lodi Andrea 
Published: February 2011

Abstract
MILP heuristics aim at finding a feasible (and hopefully good) solution of the problem above, which is an NP‐hard problem by itself. We present the main ideas underlying some of the heuristics proposed in the literature. In particular, in this article we focus on those algorithms developed with the aim of being tightly integrated within MILP solvers.
Improving Public Health In Developing Countries Through Operations Research
Authors: Yadav Prashant 
Published: February 2011

AbstractAcross the developing world, thousands of people many of them children die each day from malaria, tuberculosis, HIV/AIDS, and other infectious diseases. Many of these conditions are preventable and treatable through well known public health interventions. Operations research (OR) can be a key tool to allocate the scarce resources to cost‐effective interventions that can alleviate the health status in developing countries. This article provides an introduction to the application of OR to public health problems in developing countries for OR/MS practitioners, advanced undergraduate students in OR/MS and graduate researchers initiating work in this field. It explains commonly used public health metrics such as quality‐adjusted life year (QALY), disability‐adjusted life year (DALY), and Gini coefficient. Simple models to understand disease transmission along with a few illustrative applications of OR to solve public health problems are presented.
Integrated Supply Chain Design Models
Authors: Mak Ho‐Yin , Shen Zuo‐Jun Max 
Published: February 2011

AbstractTraditional facility location models tend to focus on the trade‐off between some measure of budget, often measured by fixed location costs, and some measure of convenience to customers, usually measured by the distance between customers and the respective nearest facilities. This simple setup, although proven to be effective in many other applications, fails to cover potential effects of tactical and operational issues on the strategic design decisions in supply chain settings. For example, inventory sharing and delivery vehicle consolidation lead to economies of scale in the operations of the facilities and thus affect the optimal distribution network configuration. Recently, researchers began to study integrated supply chain design models that take into account important tactical and operational issues when making strategic decisions on facility location and network design. In this article, we review some recent work that belongs to this new research stream. We discuss various modeling issues and the potential benefits of using integrated models over using traditional location models.
Introduction to Diffusion Processes
Authors: Ghosh Arka P. 
Published: February 2011

Abstract
In this section we describe a class of stochastic processes called the diffusion processes. These are continuous‐time, continuous state‐space processes and their sample paths are continuous everywhere but differentiable nowhere. Since diffusions are defined through stochastic differential equations, we give a brief introduction to stochastic differential equations (which include a discussion on stochastic integration as well). Diffusion processes are defined in terms of these differential equations. Finally we conclude the section with some specific example of diffusion processes.
Dynamic Programming: Introductory Concepts
Authors: Sniedovich Moshe 
Published: February 2011

Abstract
Dynamic programming (DP) is a general purpose problem solving methodology based on problem decomposition. The idea is to decompose a “difficult” problem into a family of “related problems”—which are often, but not always, “easier” subproblems of the “difficult” problem. Its plan of attack is then to embed the “difficult” problem of interest—the target problem—in a family of modified problems, and to use a functional equation to relate the solutions to these modified problems to one another. The solution obtained for this functional equation yields the solution to the modified problems as well as to the target problem. This approach has an extremely wide scope of application, but in operations research, DP is used primarily as a framework for the modeling, analysis, and, solution of optimization problems. The evolution of DP has entrenched the convention that DP treats problems as sequential decision problems. This fact is reflected in the DP terminology, notably in the central roles that the concepts “state” and “state transition” play in the theory. The subtle modeling issues associated with this approach have earned DP its reputation (perhaps notoriety) of being an “art.” Although DP's scope of operation is extremely wide‐ranging, in practice its use is often hampered by the curse of dimensionality. This difficulty has spawned the development of a host of methods and techniques aimed at dealing with the computational aspects of DP. This ongoing effort provides challenges and opportunities, especially in the development of general‐purpose DP software.
Large Deviations in Queueing Systems
Authors: Ganesh Ayalvadi J. 
Published: February 2011

AbstractLarge deviations theory deals with fluctuations of random variables from their mean values on larger scales than the central limit scaling. When applied to queueing systems, it provides an elegant unified framework for estimating the probability distributions of queue sizes and waiting times or, more precisely, their tail decay rates. This article provides a brief introduction to large deviation theory as well as its application to some simple queueing models.
Introduction to Large‐Scale Linear Programming and Applications
Authors: Stoyan Stephen J. , Dessouky Maged M. , Wang Xiaoqing 
Published: February 2011

Abstract
Linear programming (LP) has been used as an effective tool to solve a number of applications in manufacturing, transportation, military, health care, and finance. In a number of these applications, the problem size in terms of the number of variables and constraints can become rather large in order to accurately represent the system. For this reason, a number of specialized procedures such as column generation and cutting‐plane methods have been developed to effectively solve these large‐scale linear programs. In other cases, the problem may have a special structure, where decomposition methods can also be used. This article provides an overview of these specialized solution procedures. We conclude the article with an example of a large‐scale linear program developed to balance routes for street sweepers in Southern California.
Level‐Dependent Quasi‐Birth‐and‐Death Processes
Authors: Kharoufeh Jeffrey P. 
Published: February 2011

AbstractThis article defines and describes the level‐dependent quasi‐birth‐and‐death (LDQBD) process, a generalization of the homogeneous (or level‐independent) quasi‐birth‐and‐death (QBD) process. Like its level‐independent counterpart, the LDQBD process is a bivariate Markov process whose transition probability matrix (or infinitesimal generator matrix) exhibits a block tridiagonal structure. However, unlike the level‐independent QBD, its transitions are explicitly dependent on the level. This article defines discrete‐ and continuous‐time versions of the LDQBD process, discusses necessary and sufficient conditions for positive recurrence, and describes the limiting distribution for each case. Algorithmic approaches, extensions of the basic models, and suggestions for further reading are also provided.
Lift‐and‐Project Inequalities
Authors: Louveaux Quentin 
Published: February 2011

AbstractThe lift‐and‐project technique is a systematic way to generate valid inequalities for a mixed binary program. The technique is interesting both on the theoretical and on the practical point of view. On the theoretical side it allows one to construct the inequality description of the convex hull of all mixed‐{0, 1} solutions of a binary mixed‐integer program (MIP) innrepeated applications of the technique, wherenis the number of binary variables. On the practical side, a variant of the method allows one to derive some cutting planes from the simplex tableau rather efficiently.