JournalTOCs

[12 followers] Follow
Full-text available via subscription

Subscription journal
ISSN (Print) 0030-364X - ISSN (Online) 1526-5463
Published by Institute for Operations Research and the Management Sciences (INFORMS)

[12 journals]

In This Issue
- Pages: iii - vi
  Abstract: Mining and Searching. The application of operations research in the mining industry dates back to the beginning of operations research as an applied science. In "Mining Coal or Finding Terrorists: The Expanding Search Paradigm," S. Alpern and T. Lidbetter examine the decision problem faced by a coal mining company that must choose where to mine in a network of coal seams with known densities of coal, in order to maximize the coal extraction rate. To analyze this problem, the authors define "expanding search," a search model based on the assumption that the time required to move mining equipment to a nearby site is negligible compared to the time spent digging. They solve the decision problem for a certain class of networks, then consider the analogous problem in which the distribution of densities of the coal seams is unknown. The same principles apply to a search for a hidden object, terrorist, or "hider" in a network by a team of searchers. Improving Supplier Effort Through Performance-Based Business Share Allocations. To thrive, many firms need healthy long-term relationships with critical suppliers. Can a firm prevent its suppliers from getting "too comfortable" to improve? In "Dynamic Business Share Allocation in a Supply Chain with Competing Suppliers," H. Li, H. Zhang, and C. H. Fine examine the use of performance-based business share allocations as incentives for driving continuous supplier effort in a dual-sourcing supply chain. They propose a two-agent repeated moral hazard model and characterize the optimal contract through a fixed-point analysis. Optimal dynamic contracts can drive suppliers into either a stable status quo or ongoing fierce competition over the long run, illustrating, respectively, the "carrot" and "stick" of supplier incentives. The results and the discussion underscore the value of using quantitative supplier assessment systems in practice. Solving the Two-Echelon Capacitated Vehicle Routing Problem. The two-echelon vehicle routing problem (2E-VRP) represents the core problem of all multiechelon distribution networks. In the 2E-VRP, deliveries from a central depot to customers follow two levels of delivery. The first level consists of vehicle routes between the central depot and a subset of intermediate depots, or satellites; the second consists of vehicle routes from a single satellite to a group of customers. The objective is to service each customer exactly once with the second-level routes, while minimizing the total routing cost. In "An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem," R. Baldacci, A. Mingozzi, R. Roberti, and R. Wolfler Calvo develop an exact approach for solving the 2E-VRP. Their method outperforms the current best-known exact methods, both for the quality of the lower bounds achieved and the number and dimensions of the instances solved to optimality. Medium-size real-world instances involving 100 customers and six satellites were solved to optimality. Applications of a Capacitated Arc Routing Problem with Deadheading Demand. Capacitated arc routing problems involve finding a set of lowest cost routes for a fleet of capacitated vehicles to provide service to a subset of links in a given network. In "An Exact Algorithm for the Capacitated Arc Routing Problem with Deadheading Demand," E. Bartolini, J.-F. Cordeau, and G. Laporte consider a generalization called the capacitated arc routing problem with deadheading demand (CARPDD), in which a resource such as time or energy is consumed each time a link is traversed, but the consumption level depends on the activity performed. They describe practical applications of the CARPDD and propose a set partitioning (SP) formulation strengthened by a new class of valid inequalities. They develop an exact algorithm based on the SP formulation that solves both the CARPDD and the classical capacitated arc routing problem (CARP). This algorithm is computationally tested on a large set of CARPDD and CARP instances. Managing a New Type of Customer Contact Center. Companies increasingly communicate with their customers through instant messaging (IM) over the Internet, which lets service agents serve multiple customers simultaneously. In "Staffing and Control of Instant Messaging Contact Centers," J. Luo and J. Zhang consider a new type of queueing model to capture the queueing dynamics of IM contact centers. The model shares the features of a many-server queue as well as a processor-sharing queue. Under a heavy-traffic regime, the number of servers increases while the service rate for each server remains unscaled but depends on the number of customers who are sharing it. Fluid approximation involving a stochastic averaging principle is established to study the performance and optimal control of such systems. Coordinating Routing and Allocation for Parallel Queues Serving Different Customers. In "Flexible Server Allocation and Customer Routing Policies for Two Parallel Queues When Service Rates Are Not Additive," H.-S. Ahn and M. E. Lewis consider how routing and allocation can be coordinated to meet the challenge of demand variability in a parallel queueing system serving two types of customers. A decision maker decides whether to keep customers at the station where they arrived or to reroute them to the other station. At the same time, the decision maker has two servers and must decide where to allocate their effort. The authors analyze this joint decision-making scenario, but with two added important twists: they all...
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.2013.1177|hwp:resource-id:opres;61/2/iii
  Issue No: Vol. 61, No. 2 (2013)
Mining Coal or Finding Terrorists: The Expanding Search Paradigm
- Authors: Alpern, S; Lidbetter, T.
  Pages: 265 - 279
  Abstract: We show how to optimize the search for a hidden object, terrorist, or simply Hider, located at a point H according to a known or unknown distribution on a rooted network Q. We modify the traditional "pathwise search" approach to a more general notion of "expanding search." When the Hider is restricted to the nodes of Q, an expanding search S consists of an ordering $(a_{1},a_{2},\ldots)$ of the arcs of a spanning subtree such that the root node is in a 1 and every arc ai is adjacent to a previous arc aj , j < i. If ak contains H, the search time T is $\lambda (a_{1}) +\cdots +\lambda (a_{k})$, where is length measure on Q. For more general distributions , an expanding search S is described by the nested family of connected sets S(t) that specify the area of Q that has been covered by time t. S(0) is the root, $\lambda (S(t) ) =t$, and $T=\min \{ t: H \in S(t)\}$. For a known Hider distribution on a tree Q, the expected time minimizing strategy $\bar{S}$ begins with the rooted subtree Q' maximizing the "density" (Q')/ (Q'). (For arbitrary networks, we use this criterion on all spanning subtrees.) The search $\bar{S}$ can be interpreted as the optimal method of mining known coal seams, when the time to move miners or machines is negligible compared to digging time. When the Hider distribution is unknown, we consider the zero-sum search game where the Hider picks H, the Searcher S, and the payoff is T. For trees Q, the value is V = ( (Q) + D)/2, where D is a mean distance from root to leaf nodes. If Q is 2-arc connected, V = (Q)/2. Applications and interpretations of the expanding search paradigm are given, particularly to multiple agent search.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1134|hwp:master-id:opres;opre.1120.1134
  Issue No: Vol. 61, No. 2 (2013)
Dynamic Business Share Allocation in a Supply Chain with Competing Suppliers
- Authors: Li, H; Zhang, H, Fine, C. H.
  Pages: 280 - 297
  Abstract: This paper studies a repeated game between a manufacturer and two competing suppliers with imperfect monitoring. We present a principal-agent model for managing long-term supplier relationships using a unique form of measurement and incentive scheme. We measure a supplier's overall performance with a rating equivalent to its continuation utility (the expected total discounted utility of its future payoffs), and incentivize supplier effort with larger allocations of future business. We obtain the vector of the two suppliers' ratings as the state of a Markov decision process, and we solve an infinite horizon contracting problem in which the manufacturer allocates business volume between the two suppliers and updates their ratings dynamically based on their current ratings and the current performance outcome. Our contributions are both theoretical and managerial: we propose a repeated principal-agent model with a novel incentive scheme to tackle a common, but challenging, incentive problem in a multiperiod supply chain setting. Assuming binary effort choices and performance outcomes by the suppliers, we characterize the structure of the optimal contract through a novel fixed-point analysis. Our results provide a theoretical foundation for the emergence of "business-as-usual" (low effort) trapping states and tournament competition (high effort) recurrent states as the long-run incentive drivers for motivating critical suppliers.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1155|hwp:resource-id:opres;61/2/280
  Issue No: Vol. 61, No. 2 (2013)
An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem
- Authors: Baldacci, R; Mingozzi, A, Roberti, R, Calvo, R. W.
  Pages: 298 - 314
  Abstract: In the two-echelon capacitated vehicle routing problem (2E-CVRP), the delivery to customers from a depot uses intermediate depots, called satellites. The 2E-CVRP involves two levels of routing problems. The first level requires a design of the routes for a vehicle fleet located at the depot to transport the customer demands to a subset of the satellites. The second level concerns the routing of a vehicle fleet located at the satellites to serve all customers from the satellites supplied from the depot. The objective is to minimize the sum of routing and handling costs. This paper describes a new mathematical formulation of the 2E-CVRP used to derive valid lower bounds and an exact method that decomposes the 2E-CVRP into a limited set of multidepot capacitated vehicle routing problems with side constraints. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1153|hwp:resource-id:opres;61/2/298
  Issue No: Vol. 61, No. 2 (2013)
An Exact Algorithm for the Capacitated Arc Routing Problem with Deadheading Demand
- Authors: Bartolini, E; Cordeau, J.-F, Laporte, G.
  Pages: 315 - 327
  Abstract: We study an extension of the capacitated arc routing problem (CARP) called the capacitated arc routing problem with deadheading demand (CARPDD). This problem extends the classical capacitated arc routing problem by introducing an additional capacity consumption incurred by a vehicle deadheading an edge. It can be used, e.g., to model time or distance constrained arc routing problems. We show that the strongest CARP lower bounds can be weak when directly applied to the CARPDD, and we introduce a new family of valid inequalities shown to significantly strengthen these bounds. We develop an exact algorithm for the CARPDD based on cut-and-column generation and branch and price, and we report extensive computational results on a large set of benchmark instances. The same exact algorithm is also tested on classical CARP benchmark sets and is shown to improve upon the best known exact algorithms for the CARP.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1154|hwp:resource-id:opres;61/2/315
  Issue No: Vol. 61, No. 2 (2013)
Staffing and Control of Instant Messaging Contact Centers
- Authors: Luo, J; Zhang, J.
  Pages: 328 - 343
  Abstract: In addition to traditional call centers, many companies have started building a new kind of customer contact center, in which agents communicate with customers via instant messaging (IM) over the Internet rather than phone calls. A distinctive feature of the service centers based on IM is that one agent can serve multiple customers in parallel. We choose to model such a center as a server pool consisting of many limited processor-sharing servers. We characterize the underlying stochastic processes by establishing a fluid approximation in the many-server heavy-traffic regime. The limiting behavior of the stochastic processes is shown to involve a stochastic averaging principle, and the fluid approximation provides insights into the optimal staffing and control for such service centers.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1151|hwp:resource-id:opres;61/2/328
  Issue No: Vol. 61, No. 2 (2013)
Flexible Server Allocation and Customer Routing Policies for Two Parallel Queues When Service Rates Are Not Additive
- Authors: Ahn, H.-S; Lewis, M. E.
  Pages: 344 - 358
  Abstract: We consider the question of how routing and allocation can be coordinated to meet the challenge of demand variability in a parallel queueing system serving two types of customers. A decision maker decides whether to keep customers at the station at which they arrived or to reroute them to the other station. At the same time, the decision maker has two servers and must decide where to allocate their effort. We analyze this joint decision-making scenario with both routing and station-dependent holding costs, but add an important twist. We allow the combined service rate (when the servers work at the same station) to be superadditive or subadditive. This captures positive or negative externalities that arise during collaboration. We seek an optimal control policy under the discounted or long-run average cost criteria. Our results show that in the superadditive case jobs should never be routed away from the lower-cost queue. When jobs are rerouted from the higher-cost queue to the low-cost queue the optimal control is monotone in the respective queue lengths. Moreover, we show that the optimal allocation is a nonidling priority rule based on the holding costs. In the subadditive case we find that the optimal policy need not exhibit such a simple structure. In fact, the optimal allocation need not prioritize one station (it may split the servers), and the optimal routing need not be monotone in the number of customers in each queue. We characterize the optimal policy for a few canonical cases and discuss why intuitive policies need not be optimal in the general case. An extensive numerical study examines the benefit of dynamically controlling both routing and resource allocation; we discuss when using one of the two levers—dynamic routing and dynamic allocation—is sufficient and when using both controls is warranted.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1157|hwp:resource-id:opres;61/2/344
  Issue No: Vol. 61, No. 2 (2013)
Utility Copula Functions Matching All Boundary Assessments
- Authors: Abbas; A. E.
  Pages: 359 - 371
  Abstract: The construction of a multiattribute utility function is an important step in decision analysis and can be a challenging task unless some decomposition of the utility function is performed. When every attribute is utility independent of its complement, the utility elicitation task is significantly simplified because the functional form of the utility function requires only one conditional utility function for each attribute, and some normalizing constants. When utility independence conditions do not hold, the conditional utility function of an attribute may vary across the domain of the complement attributes, and therefore a single conditional utility assessment for each attribute may not be sufficient to capture the decision maker's preferences. This paper proposes a method to construct utility functions that have the flexibility to match the variations in the conditional utility function, across the domain of the attributes, using univariate utility assessments at the boundary values. The approach incorporates the boundary assessments into a new function, which we call the double-sided utility copula. This formulation provides a wealth of new functional forms that the analyst may use to incorporate utility dependence in multiattribute decision problems. The utility copula function also allows for the flexibility to incorporate a wide range of trade-off assessments among the attributes, while keeping the utility assessments at the boundary values fixed. It is also useful in determining the order of approximation provided by using certain independence assumptions in a multiattribute decision problem when the attributes are utility dependent.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1152|hwp:resource-id:opres;61/2/359
  Issue No: Vol. 61, No. 2 (2013)
Expert Elicitation of Adversary Preferences Using Ordinal Judgments
- Authors: Wang, C; Bier, V. M.
  Pages: 372 - 385
  Abstract: We introduce a simple elicitation process where subject-matter experts provide only ordinal judgments of the attractiveness of potential targets, and the adversary utility of each target is assumed to involve multiple attributes. Probability distributions over the various attribute weights are then mathematically derived (using either probabilistic inversion or Bayesian density estimation). This elicitation process reduces the burden of time-consuming orientation and training in traditional methods of attribute weight elicitation, and explicitly captures the existing uncertainty and disagreement among experts, rather than attempts to achieve consensus by eliminating them. We identify the relationship between the two methods and conduct sensitivity analysis to elucidate how these methods handle expert consensus or disagreement. We also present a real-world application on elicitation of adversarial preferences over various attack scenarios to show the applicability of our proposed methods.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.2013.1159|hwp:resource-id:opres;61/2/372
  Issue No: Vol. 61, No. 2 (2013)
A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
- Authors: Mittal, S; Schulz, A. S.
  Pages: 386 - 397
  Abstract: In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal frontier of the functions that constitute the given objective. Using this idea, we give the first fully polynomial-time approximation schemes for the max-min resource allocation problem with a fixed number of agents, combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions, and assortment optimization problems with logit choice model.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1093|hwp:master-id:opres;opre.1120.1093
  Issue No: Vol. 61, No. 2 (2013)
Balance Optimization Subset Selection (BOSS): An Alternative Approach for Causal Inference with Observational Data
- Authors: Nikolaev, A. G; Jacobson, S. H, Cho, W. K. T, Sauppe, J. J, Sewell, E. C.
  Pages: 398 - 412
  Abstract: Scientists in all disciplines attempt to identify and document causal relationships. Those not fortunate enough to be able to design and implement randomized control trials must resort to observational studies. To make causal inferences outside the experimental realm, researchers attempt to control for bias sources by postprocessing observational data. Finding the subset of data most conducive to unbiased or least biased treatment effect estimation is a challenging, complex problem. However, the rise in computational power and algorithmic sophistication leads to an operations research solution that circumvents many of the challenges presented by methods employed over the past 30 years.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1118|hwp:master-id:opres;opre.1120.1118
  Issue No: Vol. 61, No. 2 (2013)
A Linear Programming Approach to Nonstationary Infinite-Horizon Markov Decision Processes
- Authors: Ghate, A; Smith, R. L.
  Pages: 413 - 425
  Abstract: Nonstationary infinite-horizon Markov decision processes (MDPs) generalize the most well-studied class of sequential decision models in operations research, namely, that of stationary MDPs, by relaxing the restrictive assumption that problem data do not change over time. Linear programming (LP) has been very successful in obtaining structural insights and devising solution methods for stationary MDPs. However, an LP approach for nonstationary MDPs is currently missing. This is because the LP formulation of a nonstationary infinite-horizon MDP includes countably infinite variables and constraints, and research on such infinite-dimensional LPs has traditionally faced several hurdles. For instance, duality results may not hold; an extreme point may not be a basic feasible solution; and in the context of a simplex algorithm, a pivot operation may require infinite data and computations, and a sequence of improving extreme points need not converge in value to optimal. In this paper, we tackle these challenges and establish (1) weak and strong duality, (2) complementary slackness, (3) a basic feasible solution characterization of extreme points, (4) a one-to-one correspondence between extreme points and deterministic Markovian policies, and (5) we devise a simplex algorithm for an infinite-dimensional LP formulation of nonstationary infinite-horizon MDPs. Pivots in this simplex algorithm use finite data, perform finite computations, and generate a sequence of improving extreme points that converges in value to optimal. Moreover, this sequence of extreme points gets arbitrarily close to the set of optimal extreme points. We also prove that decisions prescribed by these extreme points are eventually exactly optimal in all states of the nonstationary infinite-horizon MDP in early periods.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1121|hwp:master-id:opres;opre.1120.1121
  Issue No: Vol. 61, No. 2 (2013)
Weight Restrictions and Free Production in Data Envelopment Analysis
- Authors: Podinovski, V. V; Bouzdine-Chameeva, T.
  Pages: 426 - 437
  Abstract: It is known that the incorporation of weight restrictions in models of data envelopment analysis may result in their infeasibility. In our paper we investigate this effect in detail. We show that the infeasibility is only one of several possible outcomes that point to a particular problem with weight restrictions. For example, the use of weight restrictions may also lead to zero or negative efficiency scores of some units. Removing problematic units from the data set does not necessarily remove the underlying problem caused by the weight restrictions and only makes it undetected. We prove that all such problems arise when weight restrictions induce free or unlimited production of outputs in the underlying technology. This is unacceptable from the production theory point of view and indicates that the weight restrictions need reassessing. We develop analytical criteria and computational methods that allow us to identify the above problematic situations.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1122|hwp:master-id:opres;opre.1120.1122
  Issue No: Vol. 61, No. 2 (2013)
Probabilistic Set Covering with Correlations
- Authors: Ahmed, S; Papageorgiou, D. J.
  Pages: 438 - 452
  Abstract: We consider two variants of a probabilistic set covering (PSC) problem. The first variant assumes that there is uncertainty regarding whether a selected set can cover an item, and the objective is to determine a minimum-cost combination of sets so that each item is covered with a prespecified probability. The second variant seeks to maximize the minimum probability that a selected set can cover all items. To date, literature on this problem has focused on the special case in which uncertainties are independent. In this paper, we formulate deterministic mixed-integer programming models for distributionally robust PSC problems with correlated uncertainties. By exploiting the supermodularity of certain substructures and analyzing their polyhedral properties, we develop strong valid inequalities to strengthen the formulations. Computational results illustrate that our modeling approach can outperform formulations in which correlations are ignored and that our algorithms can significantly reduce overall computation time.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1135|hwp:resource-id:opres;61/2/438
  Issue No: Vol. 61, No. 2 (2013)
The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment
- Authors: Moreno-Centeno, E; Karp, R. M.
  Pages: 453 - 468
  Abstract: We develop a novel framework, the implicit hitting set approach, for solving a class of combinatorial optimization problems. The explicit hitting set problem is as follows: given a set U and a family S of subsets of U, find a minimum-cardinality set that intersects (hits) every set in S. In the implicit hitting set problem (IHSP), the family of subsets S is not explicitly listed (its size is, generally, exponential in terms of the size of U); instead, it is given via a polynomial-time oracle that verifies if a given set H is a hitting set or returns a set in S that is not hit by H. Many NP-hard problems can be straightforwardly formulated as implicit hitting set problems. We show that the implicit hitting set approach is valuable in developing exact and heuristic algorithms for solving this class of combinatorial optimization problems. Specifically, we provide a generic algorithmic strategy, which combines efficient heuristics and exact methods, to solve any IHSP. Given an instance of an IHSP, the proposed algorithmic strategy gives a sequence of feasible solutions and lower bounds on the optimal solution value and ultimately yields an optimal solution. We specialize this algorithmic strategy to solve the multigenome alignment problem and present computational results that illustrate the effectiveness of the implicit hitting set approach.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1139|hwp:resource-id:opres;61/2/453
  Issue No: Vol. 61, No. 2 (2013)
Basis Paths and a Polynomial Algorithm for the Multistage Production-Capacitated Lot-Sizing Problem
- Authors: Hwang, H.-C; Ahn, H.-S, Kaminsky, P.
  Pages: 469 - 482
  Abstract: We consider the multilevel lot-sizing problem with production capacities (MLSP-PC), in which production and transportation decisions are made for a serial supply chain with capacitated production and concave cost functions. Existing approaches to the multistage version of this problem are limited to nonspeculative cost functions—up to now, no algorithm for the multistage version of this model with general concave cost functions has been developed. In this paper, we develop the first polynomial algorithm for the MLSP-PC with general concave costs at all of the stages, and we introduce a novel approach to overcome the limitations of previous approaches. In contrast to traditional approaches to lot-sizing problems, in which the problem is decomposed by time periods and is analyzed unidirectionally in time, we solve the problem by introducing the concept of a basis path, which is characterized by time and stage. Our dynamic programming algorithm proceeds both forward and backward in time along this basis path, enabling us to solve the problem in polynomial time.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1141|hwp:resource-id:opres;61/2/469
  Issue No: Vol. 61, No. 2 (2013)
LP Bounds in an Interval-Graph Algorithm for Orthogonal-Packing Feasibility
- Authors: Belov, G; Rohling, H.
  Pages: 483 - 497
  Abstract: We consider the feasibility problem OPP (orthogonal packing problem) in higher-dimensional orthogonal packing: given a set of d-dimensional (d ≥ 2) rectangular items, decide whether all of them can be orthogonally packed in the given rectangular container without rotation. The one-dimensional (1D) "bar" LP relaxation of OPP reduces the latter to a 1D cutting-stock problem where the packing of each stock bar represents a possible 1D stitch through an OPP layout. The dual multipliers of the LP provide us with another kind of powerful bounding information (conservative scales). We investigate how the set of possible 1D packings can be tightened using the overlapping information of item projections on the axes, with the goal to tighten the relaxation. We integrate the bar relaxation into an interval-graph algorithm for OPP, which operates on such overlapping relations. Numerical results on 2D and 3D instances demonstrate the efficiency of tightening leading to a speedup and stabilization of the algorithm.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1150|hwp:resource-id:opres;61/2/483
  Issue No: Vol. 61, No. 2 (2013)
On a Level-Set Characterization of the Value Function of an Integer Program and Its Application to Stochastic Programming
- Authors: Trapp, A. C; Prokopyev, O. A, Schaefer, A. J.
  Pages: 498 - 511
  Abstract: We propose a level-set approach to characterize the value function of a pure linear integer program with inequality constraints. We study theoretical properties of our characterization and show how they can be exploited to optimize a class of stochastic integer programs through a value function reformulation. Specifically, we develop algorithmic approaches that solve two-stage multidimensional knapsack problems with random budgets, yielding encouraging computational results.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1156|hwp:master-id:opres;opre.1120.1156
  Issue No: Vol. 61, No. 2 (2013)
Enhancing Stochastic Kriging Metamodels with Gradient Estimators
- Authors: Chen, X; Ankenman, B. E, Nelson, B. L.
  Pages: 512 - 528
  Abstract: Stochastic kriging is a new metamodeling technique for effectively representing the mean response surface implied by a stochastic simulation; it takes into account both stochastic simulation noise and uncertainty about the underlying response surface of interest. We show theoretically, through some simplified models, that incorporating gradient estimators into stochastic kriging tends to significantly improve surface prediction. To address the issue of which type of gradient estimator to use, when there is a choice, we briefly review stochastic gradient estimation techniques; we then focus on the properties of infinitesimal perturbation analysis and likelihood ratio/score function gradient estimators and make recommendations. To conclude, we use simulation experiments with no simplifying assumptions to demonstrate that the use of stochastic kriging with gradient estimators provides more reliable prediction results than stochastic kriging alone.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.1120.1143|hwp:resource-id:opres;61/2/512
  Issue No: Vol. 61, No. 2 (2013)
Call for Papers--Special Issue of Operations Research: Information and Decisions in Social and Economic Networks: Deadline: July 1, 2013
- Authors: Anderson, E; Gamarnik, D, Kleywegt, A, Ozdaglar, A.
  Pages: 529 - 529
  Abstract: Networks have become increasingly pervasive in our lives: social networks not only have a defining impact on consumer choice but are also central in social and political decisions, ranging from political discourse in the blogosphere to the organization and coordination of protests in the Arab Spring. Economic and financial transactions also increasingly occur over large, complex, dynamically changing networks, not only contributing to the efficient allocation of resources, but also occasionally creating large, systemic, and poorly understood risks. Similarly, network effects are now seen as major elements in healthcare, smart power grids, urban transportation, and more. We invite high-quality submissions in social and economic networks, construed broadly to include any system in which human action and control play a major role. We welcome contributions based on rigorous mathematical models, as well as empirical and simulation studies, that contribute to the understanding of network formation, cascades, reliability, information and action propagation, decision making, inference, measurement, and efficient optimization algorithms over networks. We seek papers that apply tools from operations research, statistics, computer science, applied mathematics, and physics to offer novel insights, build new models, and possibly provide recommendations to policy makers. To submit your paper, go to the Operations Research ScholarOne Manuscripts site at http://mc.manuscriptcentral.com/opre and follow the instructions provided. July/August 2015: Expected issue publication date.
  PubDate: 2013-04-16T09:00:31-07:00
  DOI: 10.1287/opre.2013.1178|hwp:resource-id:opres;61/2/529
  Issue No: Vol. 61, No. 2 (2013)