Decision, Operations & Information Technologies
Permanent URI for this communityhttp://hdl.handle.net/1903/2230
Prior to January 4, 2009, this unit was named Decision & Information Technologies.
Browse
20 results
Search Results
Item Models for Budget Constrained Auctions: An Application to Sponsored Search & Other Auctions(2010) Pani, Abhishek; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The last decade has seen the emergence of auction mechanisms for pricing and allocating goods on the Internet. A successful application area for auctions has been sponsored search. Search firms like Google, Bing and Yahoo have shown stellar revenue growths due to their ability to run large number of auctions in a computationally efficient manner. The online advertisement market in the U.S. is estimated to be around $41 billion in 2010 and expected to grow to $50 billion by 2011 (http://www.marketingcharts.com/interactive/us-online-advertising-market-to-reach-50b-in-2011-3128/). The paid search component is estimated to account for nearly 50% of online advertising spend. This dissertation considers two problems in the sponsored search auction domain. In sponsored search, the search operator solves a multi-unit allocation and pricing problem with the specified bidder values and budgets. The advertisers, on the other hand, regularly solve a bid determination problem for the different keywords, given their budget and other business constraints. We develop a model for the auctioneer that allows the bidders to place differing bids for different advertisement slots for any keyword combination. Despite the increased complexity, our model is solved in polynomial time. Next, we develop a column-generation procedure for large advertisers to bid optimally in the sponsored search auctions. Our focus is on solving large-scale versions of the problem. Multi-unit auctions have also found a number of applications in other areas that include supply chain coordination, wireless spectrum allocation and transportation. Current research in the multi-unit auction domain ignores the budget constraint faced by participants. We address the computational issues faced by the auctioneer when dealing with budget constraints in a multi-unit auction. We propose an optimization model and solution approach to ensure that the allocation and prices are in the core. We develop an algorithm to determine an allocation and Walrasian equilibrium prices (when they exist) under additive bidder valuations where the auctioneer's goal is social welfare maximization and extend the approach to address general package auctions. We, also, demonstrate the applicability of the Benders decomposition technique to model and solve the revenue maximization problem from an auctioneer's standpoint.Item Heuristics for Solving Three Routing Problems: Close-Enough Traveling Salesman Problem, Close-Enough Vehicle Routing Problem, Sequence-Dependent Team Orienteering Problem(2009) Mennell, William Kenneth; Golden, Bruce L.; Wasil, Edward A.; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we examine three important routing problems. In the second chapter we investigate the Close-Enough Traveling Salesman Problem (CETSP) in which a salesman must get within a specified radius of each node to visit it. The third chapter studies the multi-vehicle extension of the CETSP, the Close-Enough Vehicle Routing Problem (CEVRP). In the fourth chapter, we develop a post-processor to improve the accuracy of our heuristics for solving the CETSP and CEVRP. In the fifth chapter, we solve the Sequence-Dependent Team Orienteering Problem (SDTOP) in which the profit received for each node visited is dependent on the sequence in which all the nodes are visited. We summarize the dissertation in the final chapter. The CETSP, CEVRP, and SDTOP have application in aerial reconnaissance route planning. We formulate each problem as a mathematical program and apply heuristic and combinatorial optimization techniques to solve them. We present the results of extensive computational experiments that show that our methods produce high-quality solutions quickly.Item ROBUST REVENUE MANAGEMENT WITH LIMITED INFORMATION : THEORY AND EXPERIMENTS(2009) Lan, Yingjie; Ball, Michael O; Karaesmen, Itir A; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Revenue management (RM) problems with full probabilistic information are well studied. However, as RM practice spreads to new businesses and industries, there are more and more applications where no or only limited information is available. In that respect, it is highly desirable to develop models and methods that rely on less information, and make fewer assumptions about the underlying uncertainty. On the other hand, a decision maker may not only lack data and accurate forecasting in a new application, but he may have objectives (e.g. guarantees on worst-case profits) other than maximizing the average performance of a system. This dissertation focuses on the multi-fare single resource (leg) RM problem with limited information. We only use lower and upper bounds (i.e. a parameter range), instead of any particular probability distribution or random process to characterize an uncertain parameter. We build models that guarantee a certain performance level under all possible realizations within the given bounds. Our methods are based on the regret criterion, where a decision maker compares his performance to a perfect hindsight (offline) performance. We use competitive analysis of online algorithms to derive optimal static booking control policies that either (i) maximize the competitive ratio (equivalent to minimizing the maximum regret) or (ii) minimize the maximum absolute regret. Under either criterion, we obtain closed-form solutions and investigate the properties of optimal policies. We first investigate the basic multi-fare model for booking control, assuming advance reservations are not cancelled and do not become no-shows. The uncertainty in this problem is in the demand for each fare class. We use information on lower and upper bounds of demand for each fare class. We determine optimal static booking policies whose booking limits remain constant throughout the whole booking horizon. We also show how dynamic policies, by adjusting the booking limits at any time based on the bookings already on hand, can be obtained. Then, we integrate overbooking decisions to the basic model. We consider two different models for overbooking. The first one uses limited information on no-shows; again the information being the lower and upper bound on the no-show rate. This is appropriate for situations where there is not enough historical data, e.g. in a new business. The second model differs from the first by assuming the no-show process can be fully characterized with a probabilistic model. If a decision-maker has uncensored historical data, which is often the case in reality, he/she can accurately estimate the probability distribution of no-shows. The overbooking and booking control decisions are made simultaneously in both extended models. We derive static overbooking and booking limits policies in either case. Extensive computational experiments show that the proposed methods that use limited information are very effective and provide consistent and robust results. We also show that the policies produced by our models can be used in combination with traditional ones to enhance the system performance.Item Industrial Flexibility in Theory and Practice(2009) Reindorp, Matthew; Fu, Michael; Goyal, Manu; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)At the heart of any decision problem is some degree of "flexibility" in how to act. Most often, we aim to extract greatest possible value from this inherent flexibility. The three essays compiled here are aligned with this same general aim, but we have an important secondary concern: to highlight the value of flexibility itself in the various situations we study. In the first essay, we consider the timing of an action: when to replace obsolete subsystems within an extensive, complex infrastructure. Such replacement action, known as capital renewal, must balance uncertainty about future profitability against uncertainty about future renewal costs. Treating renewal investments as real options, we derive the unique, closed-form optimal solution to the infinite horizon version of this problem and determine the total present value of an institution's capital renewal options. We investigate the sensitivity of the solution to variations in key problem parameters. The second essay addresses the promising of lead times in a make-to-order environment, complicated by the need to serve multiple customer classes with differing priority levels. We tackle this problem with a "model free" approach: after preparing a discrete-event simulation of a make-to-order production system, we determine a policy for lead time promising through application of a reinforcement learning algorithm. The third essay presents an empirical analysis of new product launches in the automotive industry, showing that manufacturing flexibility is one key indicator of superior productivity during launch. We explore the financial dimensions of the apparent productivity differences and show that the use of flexible manufacturing increases an automobile plant's likelihood of being chosen to host a new product launch.Item Simulating and Optimizing: Military Manpower Modeling and Mountain Range Options(2009) Hall, Andrew Oscar; Fu, Michael C; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation we employ two different optimization methodologies, dynamic programming and linear programming, and stochastic simulation. The first two essays are drawn from military manpower modeling and the last is an application in finance. First, we investigate two different models to explore the military manpower system. The first model describes the optimal retirement behavior for an Army officer from any point in their career. We address the optimal retirement policies for Army officers, incorporating the current retirement system, pay tables, and Army promotion opportunities. We find that the optimal policy for taste-neutral Lieutenant Colonels is to retire at 20 years. We demonstrate the value and importance of promotion signals regarding the promotion distribution to Colonel. Signaling an increased promotion opportunity from 50% to 75% for the most competitive officers switches their optimal policy at twenty years to continuing to serve and competing for promotion to Colonel. The second essay explores the attainability and sustainability of Army force profiles. We propose a new network structure that incorporates both rank and years in grade to combine cohort, rank, and specialty modeling without falling into the common pitfalls of small cell size and uncontrollable end effects. This is the first implementation of specialty modeling in a manpower model for U.S. Army officers. Previous specialty models of the U.S. Army manpower system have isolated accession planning for Second Lieutenants and the Career Field Designation process for Majors, but this is the first integration of rank and specialty modeling over the entire officer's career and development of an optimal force profile. The last application is drawn from financial engineering and explores several exotic derivatives that are collectively known Mountain Range options, employing Monte Carlo simulation to price these options and developing gradient estimates to study the sensitivities to underlying parameters, known as "the Greeks". We find that IPA and LR/SF methods are efficient methods of gradient estimation for Mountain Range products at a considerably reduced computation cost compared with the commonly used finite difference methods.Item ANALYSIS OF DISTRIBUTION-FREE METHODS FOR REVENUE MANAGEMENT(2008-10-14) Gao, Huina; Ball, Michael; Karaesmen, Itir; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Revenue management (RM) is one area of research and practice that has gained significant attention in the past decade. The practice originated in the airline industry, where the idea was to maximize revenues obtained from a fixed amount of resources through differentiation/segmentation and strategic use of pricing and capacity. While many of the research models take into account uncertainty, the uncertainty is modeled using random variables and known probability distributions, which is often difficult to estimate and prone to error for a variety of reasons. For instance, demand patterns can fluctuate substantially from the past,and characterizing demand from censored data is challenging. This dissertation focuses on the multifare single resource (leg) problem in RM.We consider the "limited information" case where the demand information available consists of lower and upper bounds rather than a characterization of a particular probability distribution or stochastic process. We first investigate the value of the amount and type of information used in solving the single-leg RM problem. This is done via extensive computational experiments. Our results indicate that new robust methods using limited information perform comparably to other well-known procedures. These robust policies are very effective and provide consistent results, even though they use no probabilistic information. Further, robust policies are less prone to errors in modeling demand. Results of our preliminary computations justify the use of robust methods in the multi-fare single-leg problem. We next apply this distribution-free approach to a setting where progression of demand is available through time-dependent bounds. We do not make any further assumptions about the demand or the arrival process beyond these bounds and also do not impose a risk neutrality assumption. Our analytical approach relies on competitive analysis of online algorithms, which guarantee a certain performance level under all possible realizations within the given lower and upper bounds. We extend the robust model from a problem using static information into a dynamic setting, in which time-dependent information is utilized effectively. We develop heuristic solution procedures for the dynamic problem. Extensive computational experiments show that the proposed heuristics are very effective and provide gains over static ones. The models and computations described above assume a single airline, disregarding competition. As an extension of robust decision-making, in the third part of this dissertation, we analyze a model with two airlines and two fare classes where the airlines engage in competition. The model does not use any probabilistic information and only the range of demand in each fare-class is known. We develop a game-theoretic model and use competitive analysis of online algorithms to study the model properties. We derive the booking control policies for both centralized and decentralized models and provide additional numerical results.Item Empirical Analyses on Federal Thrift Savings Plan Portfolio Optimization(2007-11-27) Nestler, Scott T; Fu, Michael C; Madan, Dilip B; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)There is ample historical data to suggest that log returns of stocks and indices are not independent and identically distributed Normally, as is commonly assumed. Instead, the returns of financial assets are skewed and have higher kurtosis. To account for skewness and excess kurtosis, it is necessary to have a distribution that is more flexible than the Gaussian distribution and uses additional information that may be present in higher moments. The federal government's Thrift Savings Plan (TSP) is the largest defined contribution retirement savings and investment plan, with nearly 3.6 million participants and over $173 billion in assets. The TSP offers five assets (government bond fund, fixed income fund, large-cap stock fund, small-cap stock fund, and international stock fund) to U.S. government civilian employees and uniformed service members. The limited choice of investments, in comparison to most 401(k) plans, may be disappointing from a participant's perspective; however, it provides an attractive framework for empirical study. In this study, we investigate how the optimal choice of TSP assets changes when traditional portfolio optimization methods are replaced with newer techniques. Specifically, the following research questions are posed and answered: (1) Does use of a non-Gaussian factor model for returns, generated with independent components analysis (ICA) and following the Variance Gamma (VG) process, provide any advantage in constructing optimal TSP portfolios? (2) Can excess TSP portfolio returns be generated through rebalancing to an optimal mix? If so, what frequency of rebalancing provides benefits that offset increased computationalal and administrative burden? (3) How does the use of coherent risk and portfolio performance measures, in place of variance as the traditional the measure for risk and Sharpe Ratio as the usual portfolio performance measure affect TSP portfolio selection? We show through simulation that some of the newer schemes should produce excess returns over conventional (mean-variance optimization with Normally-distributed returns) portfolio choice models. The use of some or all of these methods could benefit the nearly 4 million TSP participants in achieving their retirement savings and investment objectives. Furthermore, we propose two new portfolio performance measures based on recent developments in coherent measures of risk.Item A Study of Four Network Problems in Transportation, Telecommunications, and Supply Chain Management(2007-08-01) Chen, Si; Golden, Bruce; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The increasing material costs and the rapid advances in computing technology have both motivated and promoted the study of network problems that arise in several different application domains. This dissertation consists of four chapters on network applications in transportation, telecommunications, and supply chain management. The core of our research is to apply heuristic search procedures and combinatorial optimization techniques to various practical problems. In the second chapter we investigate the split delivery vehicle routing problem (SDVRP), where a customer's demand can be split among several vehicles. The third chapter deals with the regenerator location problem (RLP) that arises in optical networks. The fourth chapter solves the parametric uncapacitated network design problems on series-parallel graphs, which have potential application in supply chain management. In the fifth chapter we study the arc routing problem that arises in the small package delivery industry. The last chapter summarizes the dissertation. The results in this dissertation indicate that the methodologies developed to solve the network problems in the four different applications are quite efficient. Consequently, when applied in practice, they have the potential to significantly improve the operational efficiency of organizations in the relevant application domains.Item Three Essays on Stochastic Optimization Applied in Financial Engineering and Inventory Management(2007-04-19) Zhang, Huiju; Fu, Michael C; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Stochastic optimization methods are now being widely used in a multitude of applications. This dissertation includes three essays on applying stochastic optimization methods to solve problems in inventory management and financial engineering. Essay one addresses the problem of simultaneous price determination and inventory management. Demand depends explicitly on the product price p, and the inventory control system operates under a periodic review (s, S) ordering policy. To minimize the long-run average loss, we derive sample path derivatives that can be used in a gradient-based algorithm for determining the optimal values of the three parameters (s, S, p) in a simulation-based optimization procedure. Numerical results for several optimization examples via different stochastic algorithms are presented, and consistency proofs for the estimators are provided. Essay two considers the application of stochastic optimization methods to American-style option pricing. We apply a randomized optimization algorithm called Model Reference Adaptive Search (MRAS) to pricing American-style options through parameterizing the early exercise boundary. Numerical results are provided for pricing American-style call and put options written on underlying assets following geometric Brownian motion and Merton jump-diffusion processes. We also price American-style Asian options written on underlying assets following geometric Brownian motion. The results from the MRAS algorithm are compared with the cross-entropy (CE) method, and MRAS is found to be an efficient method. Essay three addresses the problem of finding the optimal importance sampling measure when simulating portfolios of credit risky assets. We apply a gradient-based stochastic approximation method to find the parameters in the minimum variance problem when importance sampling is used. The gradient estimator is obtained under the original measure. We also employ the CE method to solve the same variance minimization problem. Numerical results illustrating the variance reduction are presented for the estimation of the portfolios' expected loss, unexpected loss and quantiles.Item Weight Annealing Heuristics for Solving Bin Packing and other Combinatorial Optimization Problems: Concepts, Algorithms and Computational Results(2006-10-23) Loh, Kok-Hua; Golden, Bruce L.; Decision and Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The application of weight annealing to combinatorial optimization problems is relatively new, compared to applications of well-known optimization techniques such as simulated annealing and tabu search. The weight annealing approach seeks to expand a neighborhood search by creating distortions in different parts of the search space. Distortion is controlled through weight assignment based on insights gained from one iteration of the search procedure to the next with a view towards focusing computational efforts on the poorly solved regions of the search space. The search for the global optimum should be accelerated and the solution quality should be improved with weight annealing. In this dissertation, we present key ideas behind weight annealing and develop algorithms that solve combinatorial optimization problems. Our weight annealing-based heuristics solve the one-dimensional bin packing problem and the two-dimensional bin packing problem with and without guillotine cutting and item orientation constraints. We also solve the maximum cardinality bin packing problem and the multidimensional multiple knapsack problem with our heuristics.