Academic Commons Search Results
http://academiccommons.columbia.edu/catalog.rss?f%5Bdepartment_facet%5D%5B%5D=Operations+Research&q=&rows=500&sort=record_creation_date+desc
Academic Commons Search Resultsen-usOn the Kidney Exchange Problem and Online Minimum Energy Scheduling
http://academiccommons.columbia.edu/catalog/ac:175610
Herrera Humphries, Tuliahttp://dx.doi.org/10.7916/D8125QSXMon, 07 Jul 2014 11:36:10 +0000The allocation and management of scarce resources are of central importance in the design
of policies to improve social well-being. This dissertation consists of three essays; the first
two deals with the problem of allocating kidneys and the third one on power management
in computing devices.
Kidney exchange programs are an attractive alternative for patients who need a kidney
transplant and who have a willing, but medically incompatible, donor. A registry that keeps
track of such patient-donor pairs can nd matches through exchanges amongst such pairs.
This results in a quicker transplant for the patients involved, and equally importantly, keeps
such patients from the long wait list of patients without an intended donor. As of March
2014, there were at least 99,000 candidates waiting for a kidney transplant in the U.S.
However, in 2013 only 16,893 transplants were conducted. This imbalance between supply
and demand among other factors, has driven the development of multiple kidney exchange
programs in the U.S. and the subsequent development of matching mechanisms to run the
programs.
In the first essay we consider a matching problem arising in kidney exchanges between
hospitals. Focusing on the case of two hospitals, we construct a strategy-proof matching
mechanism that is guaranteed to return a matching that is at least 3/4 the size of a maximum cardinality
matching. It is known that no better performance is possible if one focuses on
mechanisms that return a maximal matching, and so our mechanism is best possible within
this natural class of mechanisms. For path-cycle graphs we construct a mechanism that
returns a matching that is at least 4/5 the size of max-cardinality matching. This mechanism
does not necessarily return a maximal matching. Finally, we construct a mechanism that is
universally truthful on path-cycle graphs and whose performance is within 2/3 of optimal.
Again, it is known that no better ratio is possible.
In most of the existing literature, mechanisms are typically evaluated by their overall
performance on a large exchange pool, based on which conclusions and recommendations
are drawn. In our second essay, we consider a dynamic framework to evaluate extensively
used kidney exchange mechanisms. We conduct a simulation-based study of a dynamically
evolving exchange pool during 9 years. Our results suggest that some of the features that
are critical in a mechanism in the static setting have only a minor impact in its longrun
performance when viewed in the dynamic setting. More importantly, features that
are generally underestimated in the static setting turn to be relevant when we look at
dynamically evolving exchange pool. For example, the pairs' arrival rates. In particular we
provide insights into the eect on the waiting times and the probability to receive an oer
of controllable features such as the frequency at which matching are run, the structures
through which pairs could be matched (cycles or chains) as well as inherent features such
as the pairs ABO-PRA characteristics, the availability of altruistic donors, and wether or
not compatible pairs join the exchange etc. We evaluate the odds to receive an oer and
the expected time to receive an oer for each ABO-PRA type of pairs in the model.
Power management in computing devices aims to minimize energy consumption to perform
tasks, meanwhile keeping acceptable performance levels. A widely used power management
strategy for devices, is to transit the devices and/or components to lower power
consumption states during inactivity periods. Transitions between power states consume
energy, thus, depending on such costs, it may be advantageous to stay in high power state
during some inactivity periods. In our third essay we consider the problem of minimizing
the total energy consumed by a 2-power state device, to process jobs that are sent over time
by a constrained adversary. Jobs can be preempted, but deadlines need to be met. In this
problem, an algorithm must decide when to schedule the jobs, as well as a sequence of power
states, and the discrete time thresholds at which these states will be reached. We provide
an online algorithm to minimize the energy consumption when the cost of a transition to
the low power state is small enough. In this case, the problem of minimizing the energy
consumption is equivalent to minimizing the total number of inactivity periods. We also
provide an algorithm to minimize the energy consumption when it may be advantageous
to stay in high power state during some inactivity periods. In both cases we provide upper
bounds on the competitive ratio of our algorithms, and lower bounds on the competitive
ratio of all online algorithms.Operations researchIndustrial Engineering and Operations Research, Operations ResearchDissertationsFrom Continuous to Discrete: Studies on Continuity Corrections and Monte Carlo Simulation with Applications to Barrier Options and American Options
http://academiccommons.columbia.edu/catalog/ac:171186
Cao, Menghuihttp://dx.doi.org/10.7916/D8PG1PS1Fri, 28 Feb 2014 15:26:30 +0000This dissertation 1) shows continuity corrections for first passage probabilities of Brownian bridge and barrier joint probabilities, which are applied to the pricing of two-dimensional barrier and partial barrier options, and 2) introduces new variance reduction techniques and computational improvements to Monte Carlo methods for pricing American options.
The joint distribution of Brownian motion and its first passage time has found applications in many areas, including sequential analysis, pricing of barrier options, and credit risk modeling. There are, however, no simple closed-form solutions for these joint probabilities in a discrete-time setting. Chapter 2 shows that, discrete two-dimensional barrier and partial barrier joint probabilities can be approximated by their continuous-time probabilities with remarkable accuracy after shifting the barrier away from the underlying by a factor. We achieve this through a uniform continuity correction theorem on the first passage probabilities for Brownian bridge, extending relevant results in Siegmund (1985a). The continuity corrections are applied to the pricing of two-dimensional barrier and partial barrier options, extending the results in Broadie, Glasserman & Kou (1997) on one-dimensional barrier options. One interesting aspect is that for type B partial barrier options, the barrier correction cannot be applied throughout one pricing formula, but only to some barrier values and leaving the other unchanged, the direction of correction may also vary within one formula.
In Chapter 3 we introduce new variance reduction techniques and computational improvements to Monte Carlo methods for pricing American-style options. For simulation algorithms that compute lower bounds of American option values, we apply martingale control variates and introduce the local policy enhancement, which adopts a local simulation to improve the exercise policy. For duality-based upper bound methods, specifically the primal-dual simulation algorithm (Andersen and Broadie 2004), we have developed two improvements. One is sub-optimality checking, which saves unnecessary computation when it is sub-optimal to exercise the option along the sample path; the second is boundary distance grouping, which reduces computational time by skipping computation on selected sample paths based on the distance to the exercise boundary. Numerical results are given for single asset Bermudan options, moving window Asian options and Bermudan max options. In some examples the computational time is reduced by a factor of several hundred, while the confidence interval of the true option value is considerably tighter than before the improvements.Operations research, FinanceOperations Research, Industrial Engineering and Operations ResearchDissertationsApproximate dynamic programming for large scale systems
http://academiccommons.columbia.edu/catalog/ac:169790
Desai, Vijay V.Fri, 28 Jun 2013 10:51:16 +0000Sequential decision making under uncertainty is at the heart of a wide variety of practical problems. These problems can be cast as dynamic programs and the optimal value function can be computed by solving Bellman's equation. However, this approach is limited in its applicability. As the number of state variables increases, the state space size grows exponentially, a phenomenon known as the curse of dimensionality, rendering the standard dynamic programming approach impractical. An effective way of addressing curse of dimensionality is through parameterized value function approximation. Such an approximation is determined by relatively small number of parameters and serves as an estimate of the optimal value function. But in order for this approach to be effective, we need Approximate Dynamic Programming (ADP) algorithms that can deliver `good' approximation to the optimal value function and such an approximation can then be used to derive policies for effective decision-making. From a practical standpoint, in order to assess the effectiveness of such an approximation, there is also a need for methods that give a sense for the suboptimality of a policy. This thesis is an attempt to address both these issues. First, we introduce a new ADP algorithm based on linear programming, to compute value function approximations. LP approaches to approximate DP have typically relied on a natural `projection' of a well studied linear program for exact dynamic programming. Such programs restrict attention to approximations that are lower bounds to the optimal cost-to-go function. Our program -- the `smoothed approximate linear program' -- is distinct from such approaches and relaxes the restriction to lower bounding approximations in an appropriate fashion while remaining computationally tractable. The resulting program enjoys strong approximation guarantees and is shown to perform well in numerical experiments with the game of Tetris and queueing network control problem. Next, we consider optimal stopping problems with applications to pricing of high-dimensional American options. We introduce the pathwise optimization (PO) method: a new convex optimization procedure to produce upper and lower bounds on the optimal value (the `price') of high-dimensional optimal stopping problems. The PO method builds on a dual characterization of optimal stopping problems as optimization problems over the space of martingales, which we dub the martingale duality approach. We demonstrate via numerical experiments that the PO method produces upper bounds and lower bounds (via suboptimal exercise policies) of a quality comparable with state-of-the-art approaches. Further, we develop an approximation theory relevant to martingale duality approaches in general and the PO method in particular. Finally, we consider a broad class of MDPs and introduce a new tractable method for computing bounds by consider information relaxation and introducing penalty. The method delivers tight bounds by identifying the best penalty function among a parameterized class of penalty functions. We implement our method on a high-dimensional financial application, namely, optimal execution and demonstrate the practical value of the method vis-a-vis competing methods available in the literature. In addition, we provide theory to show that bounds generated by our method are provably tighter than some of the other available approaches.Operations research, Mathematicsvvd2101Operations Research, BusinessDissertations