on paper title to view abstract)
- Comparison of
least squares Monte Carlo methods with applications to energy
real options (with F. Margot and N. Secomandi). European Journal of
Operational Research, 256, 2017. [pdf]
Least squares Monte Carlo (LSM) is a state-of-the-art approximate dynamic programming approach used in financial engineering and real options to value and manage options with early or multiple exercise opportunities. It is also applicable to capacity investment and inventory/production management problems with demand/supply forecast updates arising in operations and hydropower-reservoir management. LSM has two variants, referred to as regress-now/later (LSMN/L), which compute continuation/value function approximations (C/VFAs). We provide novel numerical evidence for the relative performance of these methods applied to energy swing and storage options, two typical real options, using a common price evolution model. LSMN/L estimate C/VFAs that yield equally accurate (near optimal) and precise lower and dual (upper) bounds on the value of these real options. Estimating the LSMN/L C/VFAs and their associated lower bounds takes similar computational effort. In contrast, the estimation of a dual bound using the LSML VFA instead of the LSMN CFA takes seconds rather than minutes or hours. This finding suggests the use of LSML in lieu of LSMN when estimating dual bounds on the value of early or multiple exercise options, as well as of related capacity investment and inventory/production policies.
of approximate linear programs for the real option management
of commodity storage (with F. Margot and N. Secomandi).
Management Science, 61(12), 2015.
The real option management of commodity conversion
assets gives rise to intractable Markov decision processes
(MDPs), in part due to the use of high dimensional models of
commodity forward curve evolution, as commonly done in
practice. Focusing on commodity storage, we identify a
deficiency of approximate linear programming, which we address
by developing a novel approach to derive relaxations of
approximate linear programs (ALPs). We apply our approach to
obtain a class of tractable ALP relaxations, also subsuming an
existing method. We provide theoretical support for the use of
these ALP relaxations rather than their corresponding ALPs.
Applied to existing natural gas storage instances, our ALP
relaxations significantly outperform their corresponding ALPs.
Our best ALP relaxation is both near optimal and competitive
with, albeit slower than, state-of-the-art methods for
computing heuristic policies and lower bounds on the value of
commodity storage, but is more directly applicable for dual
upper bound estimation than these methods. Our approach is
potentially relevant for the approximate solution of MDPs that
arise in the real option management of other commodity
conversion assets, as well as the valuation of real and
financial options that depend on forward curve dynamics.
- Real option
management of hydrocarbon cracking operations (with N.
Secomandi, G. Sowers, and J. Wassick). Forthcoming in Real
Options in Energy and Commodity Markets (Now Publishing).
Commodity conversion assets play important economic
roles. It is well known that the market value of these assets
can be maximized by managing them as real options on the
prices of their inputs and/or outputs. In particular, when
futures on these inputs and outputs are traded, managing such
real options, that is, valuing, hedging, and exercising them,
is analogous to managing options on such futures, using risk
neutral valuation and delta hedging methods. This statement
holds because dynamically trading portfolios of these futures
and a risk less bond can replicate the cash flows of these
assets. This basic principle is not always appreciated by
managers of commodity conversion assets. Moreover, determining
the optimal operational cash flows of such an asset requires
optimizing the asset operating policy. This issue complicates
the real option management of commodity conversion assets.
This chapter illustrates the application of this approach to
manage a hydrocarbon cracker, a specific commodity conversion
asset, using linear programming and Monte Carlo simulation.
The discussion is based on a simplified representation of the
operations of this asset. However, the material presented here
has potential applicability to the real option management of
more realistic models of hydrocarbon cracking assets, as well
as other energy and commodity conversion assets.
- Less-Than-Truckload carrier collaboration problem: modeling framework and solution approach (with J. H. Bookbinder). Journal of Heuristics, 19(6),
Less-Than-Truckload (LTL) carriers generally serve
geographical regions that are more localized than the
inter-city line-hauls served by truckload carriers. That
localization can lead to urban freight transportation routes
that overlap. If trucks are traveling with less than full
loads, there typically exist opportunities for carriers to
collaborate over such routes. We introduce a two stage
framework for LTL carrier collaboration. Our first stage
involves collaboration between multiple carriers at the
entrance to the city and can be formulated as a vehicle
routing problem with time windows (VRPTW). We employ guided
local search for solving this VRPTW. The second stage involves
collaboration between carriers at transshipment facilities
while executing their routes identified in phase one. For
solving the second stage problem, we develop novel local
search heuristics, one of which leverages integer programming
to efficiently explore the union of neighborhoods defined by
new problem-specific move operators. Our computational results
indicate that integrating integer programming with local
search results in at least an order of magnitude speed up in
the second stage problem. We also perform sensitivity analysis
to assess the benefits from collaboration. Our results
indicate that distance savings of 7–15 % can be achieved
by collaborating at the entrance to the city. Carriers
involved in intra-city collaboration can further save
3–15 % in total distance traveled, and also reduce their
overall route times.
- Revisiting approximate linear programming using a saddle point based reformulation and root finding solution approach
(with Q. Lin and N. Soheili). [pdf]
Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) for high dimensional Markov decision processes (MDPs) arising in business applications. VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost, which can be used to assess the suboptimality of heuristic policies. However, solving ALPs near optimally remains challenging, for instance, in applications where the MDP includes cost functions or transition dynamics that are nonlinear or when rich basis functions are required to obtain a good VFA. We address this tension between ALP theory and solvability by (i) proposing a saddle point based reformulation of an ALP that endogenizes a state-action density function as a dual decision variable to avoid non-convexities, and (ii) developing a solution approach, ALP-Secant, that combines root finding and saddle point methods to solve this reformulation. We establish that ALP-Secant returns a near optimal ALP solution and a lower bound on the optimal policy cost with high probability in a finite number of iterations. We numerically compare ALP-Secant with the commonly used constraint sampling approach to solve ALP and a look-ahead heuristic on inventory control and energy storage applications, where using row generation is not a viable option. We find that ALP-Secant is more effective than constraint sampling for solving ALPs and delivers high quality policies and lower bounds, with its policies outperforming those from the other two heuristics. Our ALP reformulation and solution approach broaden the applicability of approximate linear programming.
- Merchant energy trading in a network
(with N. Secomandi). [pdf]
We formulate the merchant trading of energy in a network of storage and transport assets as a Markov decision process with uncertain energy prices, generalizing known models. Because of the intractability of our model, we develop heuristics and both lower and dual (upper) bounds on the optimal policy value estimated within Monte Carlo simulation. We achieve tractability using linear optimization, extending near optimal approximate dynamic programming techniques for the case of a single storage asset, versions of two of which are commercially available. We propose (i) a generalization of a deterministic reoptimization heuristic, (ii) an iterative version of the least squares Monte Carlo approach, and (iii) a perfect information dual bound. We apply our methods to a set of realistic natural gas instances. The combination of our reoptimization heuristic and dual bound emerges as a practical approach to nearly optimally solve our model. Our iterative least squares Monte Carlo heuristic is also close to optimal. Compared to our other heuristic, it exhibits slightly larger optimality gaps and requires some tuning, but is faster to execute in some cases. Our methods could enhance single energy storage asset software and have potential relevance beyond our specific application.
- Relationship between least squares Monte Carlo and approximate linear programming
(with N. Secomandi). [pdf]
Least squares Monte Carlo (LSM) is commonly used to manage and value intractable early and multiple exercise financial and real options. Recent research in this area has started applying approximate linear programming (ALP) and its relaxations, which aim at addressing a possible ALP drawback. We show that LSM is itself an ALP relaxation that potentially corrects this ALP shortcoming. Our analysis consolidates two separate streams of research and suggests using LSM rather than ALP for the considered class of problems.
- Dynamic pricing
for hotel rooms when customers request multiple-day stays
(with Y. F. Lim and Q. Ding). [pdf]
Some prominent hotel chains quote a booking price of a particular type of rooms on each day and dynamically update these prices over time. We present a novel Markov decision process formulation that determines the optimal booking price for a single type of rooms under this strategy, while considering the availability of rooms throughout the multiple-day stays requested by customers. We unveil the importance of modeling multiple-day stays by comparing the optimal policy with a single-day decomposition approach (SDD). Our analysis of the optimal policy around peak-demand events (such as public holidays or conferences) suggests that hotels should substantially raise the booking prices for some high-demand days, and simultaneously, significantly lower the booking prices for the low-demand days that are immediately adjacent to these high-demand days. This finding may potentially simplify the implementation of pricing policies. Since computing an optimal policy is intractable, we develop heuristics based on a fluid approximation and approximate linear programming (ALP). We numerically benchmark them against an SDD and an adaptation of a fixed-price heuristic. The ALP-based heuristic (i) outperforms the other methods; (ii) generates up to 7% and 6% more revenue than the SDD and fixed-price heuristic respectively; and (iii) incurs a revenue loss of only less than 1% when using our pricing structure around peak-demand events, which supports the use of this simple pricing profile. Our findings are potentially relevant beyond the hotel domain for applications involving the dynamic pricing of capacitated resources used by multiple products.
- Partial hyperplane activation for generalized intersection cuts
(with A. Kazachkov, E. Balas, and F. Margot). [pdf]
The generalized intersection cut (GIC) paradigm is a recent framework for generating cutting planes in mixed integer programming with attractive theoretical properties. We investigate this computationally unexplored paradigm and observe that a key hyperplane activation procedure embedded in it is not computationally viable. To overcome this issue, we develop a novel replacement to this procedure called partial hyperplane activation (PHA), introduce a variant of PHA based on a notion of hyperplane tilting, and prove the validity of both algorithms. We propose several implementation strategies and parameter choices for our PHA algorithms and provide supporting theoretical results. We computationally evaluate these ideas in the COIN-OR framework on MIPLIB instances. Our findings shed light on the the strengths of the PHA approach as well as identify properties related to strong cuts that can be targeted in the future.
- A three-echelon integrated production-distribution
system (with J. H. Bookbinder). International Conference on
Decision Sciences and Technology for Globalization, Decision
Sciences Institute, Ghaziabad, India. 2008.
- Enhancing transportation efficiencies through carrier
collaboration (with J. H. Bookbinder). BPC World Conference ,
Mumbai, India. 2007.
- Non-destructive evaluation by low pulsing acoustic tap
technique: Spectral relationships (with T.S. Niranjan and
A.V.Varun). Flight 2006, National Aerospace Symposium, Chennai,