Stochastic Mixed-Integer Programming for Integrated Portfolio Planning in the LNG Supply Chain.

• Author: Werner, Adrian

1. INTRODUCTION

   Stochastic mixed-integer programming has been used to examine a number of issues in energy economics, including investment planning in the natural gas industry (Guldmann and Wang 1999, Zheng and Pardalos 2010). The majority of these applications take a cost-minimization approach. In this paper we take the perspective of firms that maximize expected profits. In doing so, we look at the whole value chain in a portfolio perspective. We consider contracting decisions, while allowing for arbitrage trades in the spot market, whereby physical shipments can be redirected to take advantage of geographical price differentials. We illustrate this using a price uncertainty example inspired by a real-life application. In fact, recent developments in the global natural gas markets have made our modeling innovations particularly important.

   The increasing importance of liquefied natural gas (LNG) is illustrated by rapid growth of the industry in recent years. In 2000, twelve LNG exporters traded 220 million [m.sup.3] to ten LNG importing countries (BP 2001). By 2010, this figure had more than doubled, with 18 LNG exporting countries trading 483 million [m.sup.3] to 23 LNG importers (BP 2011, GIIGNL 2010).

   The LNG supply chain typically includes production of natural gas, transportation to a liquefaction terminal, the liquefaction process and loading of vessels, shipping of the LNG to regasification terminals, and regasification to natural gas for distribution through the pipeline grid. Figure 1 in Section 3.2 provides an overview of the supply chain elements considered in our model, from liquefaction to transportation, and regasification to markets for natural gas. For a thorough description of this chain, we refer to Fodstad et al. (2010).

   Natural gas markets are dynamic and unpredictable both in the long and short term. The US Energy Information Administration (EIA) observed retrospectively, in yearly energy outlooks, that deviations between projections and market outcomes (both volumes and prices) were larger for natural gas than for all other fuels (EIA 2010). Despite significant uncertainty, lower operating and shipping costs and an increasing LNG market liquidity has induced a shift away from risk-reducing long-term contracts over the last decade. Due to a tenfold increase, spot and short-term trade accounted for 25% of total LNG trade in 2011 (GIIGNL 2011). Currently, an increasing share of short-term contracts and cargo re-routing is used to benefit from arbitrage opportunities in spot markets. These developments make it more difficult to devise profitable, yet flexible long-term strategies. It is, therefore, paramount to address uncertainty adequately when developing models to support investment and contract timing decisions.

   The main contribution of the LNGPlanner model is to provide a tool to perform integrated analysis of an industry actor's portfolio of both existing and potential investments along the LNG supply chain, which accommodates price uncertainty. It focuses on both physical and economic aspects, allowing for exploitation of flexibility in the supply chain to benefit from market opportunities while meeting operational criteria. The mathematical model forms a multistage stochastic mixed-integer linear programming (SMILP) problem, accommodating uncertainty through a scenario tree approach. The model has been developed for, and in close collaboration with, several partners from the LNG industry to provide decision support for some of their strategic decisions.

2. LITERATURE REVIEW

   There is an extensive base of literature on optimal (1) investment strategies; however, integrated approaches for the LNG business that take uncertainty into account are underrepresented. Investment models such as the one in Andre (2010) tend to focus on deterministic cost minimization rather than stochastic profit maximization. In a recent paper, MirHassani and Noori (2011) explicitly address the drawbacks of the use of scenario analysis assuming perfect foresight for a realistic problem. Birge and Loveaux (1997) showed that stochastic optimization approaches are needed to make optimal decisions and to represent the hedging behavior of investors facing uncertainty.

   Alternative means for evaluating investment opportunities are provided by real-options approaches. Murto and Keppo (2002), Klaassen et al. (2004), and Krey and Minullin (2005) emphasized game-theoretic aspects among the investors. Real option approaches for investment decisions in the oil and gas industry can be found in Smith and McCardle (1999), Bockman et al. (2008), Kaminski et al. (2008), Thompson et al. (2009), and Lai et al. (2011). Such approaches provide useful insight into the timing of investments. However, they have limitations with regard to capturing the interrelations of multiple investment opportunities within the same modeling framework.

   The stochastic dynamic programming (SDP) approaches for energy planning problems discussed in Botterud and Korpas (2007), Fleten (2000), and Andre (2010) potentially allow for the flexibility needed for optimal capacity and timing decisions that affect each other. However, due to the combinatorial characteristic of the problems, heuristics are needed to provide solutions within acceptable time limits. To circumvent these combinatorial challenges, Pereira and Pinto (1991), Granville et al. (2003), Bezerra et al. (2010), and Aouam and Yu (2008) developed the concept of stochastic dual dynamic programs (SDDP). Although some of these concepts and insights can be transferred to other fields, the applicability of the SDDP approach to the problem studied in this paper is limited. SDDP requires a discretization of the potential values for the decision variables while our approach includes continuous variables that may take a large range of values.

   Other approaches have also been used for solving energy planning problems. Egging (2010) developed a stochastic mixed complementarity problem addressing optimal capacity expansion by various actors in the global natural gas market. The approach does not allow for integer variables and does not scale well in terms of the number of scenarios that can be accommodated. In a more operational setting, Tomasgard et al. (2007) presented an integrated operational and financial approach to manage and optimize the various elements of the natural gas supply chain from production to sales, taking into account uncertainty in both demand and prices in a two-stage recourse approach. Zheng and Pardalos (2010) propose a SMILP problem for location of LNG terminals and expansion of pipelines. Their model is highly relevant albeit complementary to the work presented here, as they minimize expected costs while we maximize expected net present value. The authors include pipeline expansions and regasification terminals in their model, while our model includes regasification and liquefaction terminals, vessel investments and charter, contract decisions and spot markets, but not pipeline expansions.

   Important stepping-stones to the model presented here are papers by Nygreen et al. (1998), Fodstad et al. (2010), and Gronhaug et al. (2010). Nygreen et al. (1998) developed a model for optimally operating and expanding the pipeline network on the Norwegian continental shelf using a project-based approach for timing the start-up of production fields. The work of Fodstad et al. (2010) and Gronhaug et al. (2010) focused on tactical planning in the LNG business including routing of ships, typically within a yearly horizon, while LNGPlanner has a much longer planning horizon (typically 10-25 years).

   The remainder of this paper is organized as follows. The next section presents the model. Sections 4 and 5 discuss two test cases, illustrating selected model features. The first case elaborates on uncertainty, hedging, and spot trading, while the second one discusses the added value of the portfolio approach. Section 6 concludes and provides directions for future research. The appendix provides more detailed results for the test cases.

3. THE MODEL

   Our stochastic mixed-integer linear programming model covers the supply chain from liquefaction to shipping and regasification to natural gas markets. The objective of the model is to maximize the expected NPV of a company's portfolio of terminals, vessels, and contracts. This chapter gives a verbal description of the model. The corresponding mathematical formulation can be found in Werner et al. (2012).

   3.1 Strategic Decisions

   The main decisions are investments and disinvestments that design the supply chain. These constitute the integer and binary variables in the model. Investment opportunities are denoted as "projects" and cover liquefaction terminals, regasification terminals, vessels, and contracts. The timing of investments and disinvestments is chosen by the model, but is limited to a given time interval. The decisions typically make some capacity available in the time periods following the decision and generate a series of cash flows. In some situations, a project depends on other projects being started first. For instance, a terminal cannot be built unless the related feasibility study has been completed and the necessary permits are obtained. The model allows for mutually exclusive projects. For instance, it is not possible to choose two different sizes of terminals for a given location.

   Vessel projects represent investments in different vessel types with varying capacities and costs. Furthermore, the fleet can be supplemented by chartering vessels. Unused vessels can be chartered out or sold. In contrast to buying and selling vessels, prematurely ending a charter is not possible.

   The finite time horizon of a MILP model can often distort decisions close to the end of the horizon. For instance, it is unlikely for this model to invest in new assets in the last part of the time horizon because that would incur investment costs while the...