CHEMICAL ENGINEERING TRANSACTIONS VOL. 76, 2019 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Petar S. Varbanov, Timothy G. Walmsley, Jiří J. Klemeš, Panos Seferlis Copyright © 2019, AIDIC Servizi S.r.l. ISBN 978-88-95608-73-0; ISSN 2283-9216 A Multiobjective Mixed-Integer Bilevel Linear Programming Approach to Global Crude Oil Purchase and Sale with Noncooperative Stakeholders Jack Thomas Nicoletti, Fengqi You* Cornell University, Ithaca, New York, USA fengqi.you@cornell.edu The petrochemical industry is an integral component of the global today. The petrochemical supply chain itself is a worldwide undertaking, and the final products that are offered to consumers will often travel thousands of miles from oil well to gas station pump. In the crude oil supply chain, there are three main stages: crude oil extraction, oil separation and refinement, and final product delivery. Within this supply chain, various companies will compete and attempt to maximize their profits by exploiting the demands and needs of the other companies within the supply chain. Each company or player in the crude oil industry has its own objective, and it will compete against other companies trying to pursue their individual objectives. In this work, the crude oil supply chain from oil well to refinery is modelled as a mixed-integer bilevel linear program (MIBLP) which accounts for conflicting objectives and interactions between different stakeholders. The composition, pricing, transportation distances, and environmental impacts of the different oils are taken into consideration when constructing the model. The resulting model is then applied to a U.S.-based refinery that purchases oil from various countries surrounding the Persian Gulf. The case study produces a pareto-optimal curve that displays the trade-off between environmental impact and profit. One intermediate point on the curve is selected to show how a 4.4 % decrease in profit can lead to a 3.0 % decrease in total kg CO2-eq produced. 1. Introduction Fuel supply chain optimization has been a growing topic of research in recent years (Garcia and You, 2015). Various works aim to identify optimal decisions in scenarios where multiple stakeholders with competing objectives are present (Gao and You, 2017b). In existing works, bilevel programming (Colson et al., 2007) is the preferred and predominant method of modelling game-theoretic decisions in supply chains (Basar et al., 1995) and in process control (Chu et al., 2014). Bilevel programs are a mathematical formulation of Stackelberg game theory (Hanley and Folmer, 1998), which consists of a hierarchical game between a leader and one or more followers (Myerson, 2013). The leader in the Stackelberg game will make its decisions first, and after the leader has made its decision, the followers will make optimal recourse decisions (Matos and Hall, 2007). The Stackelberg game is asymmetric in the fact that the leader has full knowledge of the followers’ optimal recourse decision before the leader’s decision is made (Zhao et al. 2019). In bilevel optimization, the upper level problem corresponds to the leader’s problem, and the nested lower level program corresponds to the follower problem (Hennet and Arda, 2008). However, bilevel programming does not come without its own set of caveats. For example, in order to reformulate the bilevel program into a single level program that can be solved in one iteration by an off-the-shelf optimization tool, the lower level program must be a linear program that does not have any discrete variables (Yue et al., 2019). If the lower level program involves discrete variables, an iterative reformulation and decomposition algorithm that involves partial enumeration of discrete variables must be applied to the bilevel program (Yue et al., 2017). Therefore, the continuous and discrete variables must be carefully selected to ensure that the model avoids discrete decisions in the lower-level problem if possible. In this work, bilevel programming is applied to the crude oil supply chain to model decisions made by an oil refinery (the leader) and variety of global oil fields (the followers). In this model, the leader has the dual objective of maximizing the profit made from selling refined products and minimizing the environmental cost of the DOI: 10.3303/CET1976013 Paper Received: 26/03/2019; Revised: 11/08/2019; Accepted: 11/08/2019 Please cite this article as: Nicoletti J.T., You F., 2019, A Multiobjective Mixed-Integer Bilevel Linear Programming Approach to Global Crude Oil Purchase and Sale with Noncooperative Stakeholders, Chemical Engineering Transactions, 76, 73-78 DOI:10.3303/CET1976013 73 products that it creates. Meanwhile, the followers all share in the objective of maximizing individual profit. The conflicting objectives for the leader will lead to a set of pareto-optimal decisions that will display the trade-off between environmental costs and economic gains (Gao and You, 2017a). The followers are distinguished from each other by the type of oil that they are selling. Each oil has unique chemical composition, environmental impact, and energy density (Mittal et al. 2016), and these differences can be exploited by the leader to recognize which oil should be purchased. Finally, the resulting program involves both discrete and binary decisions, but the formulation is constructed so that only continuous variables appear in the lower-level problem. As a result, the Karush-Kuhn-Tucker (KKT) conditions can be applied to transform the MIBLP into a single-level MILP as shown in previous works (Gao and You 2018). The program is then applied to a case study for an American refinery using various crude oils being sold from the Persian Gulf region. The major contributions of this work can be summarized as follows: • A novel bilevel optimization framework for the operation of global crude oil networks with noncooperative stakeholders; • A specific case study on bilevel optimization of the global crude oil market based on the purchase and sale of various middle eastern crude oils; • Comparisons and analysis of the leader’s and followers’ decisions under varying degrees of environmental constraint. 2. Model formulation In this section, the full bilevel program, as well as the necessary steps to transform the MIBLP into a mixed- integer linear program (MILP), are presented. In the model, the leader must focus on maximizing the profit from selling end products as well as minimizing the environmental impact of creating the final products. The leader decides not only which crude oil suppliers to buy from, but also how much crude oil to buy from each of these suppliers. The followers will focus solely on maximizing the profit made from the sale of oil to the refinery. The prices of oil are made to be continuous in the model, whereas the oil quantities are discretized by the standard oil lot size, which equals 1,000 barrels of oil as the functional unit (Yue et al., 2013). Eq(1) is the leader’s economic objective of maximizing profit, and Eq(2) is the definition of cost that factors into the calculation of profit. The leader’s environmental objective of minimizing impact is shown in Eq(3). Eq(4) is a binary variable constraint to ensure that each oil can only be sold at one lot size, and Eq(5) and Eq(6) impose demand restrictions to ensure that the amounts of each product being created are sufficient to satisfy demand but not too much as to create an unnecessarily large surplus of a certain product. Eq(7) is a conversion constraint which relates the amount of each final product created to the crude oils that have been purchased. Data for the conversion of each oil to the final products based on the oil chemical composition can be found in online oil databases (Bergerson, 2017). A constraint on the % of the total oil produced at one oil well than can be consumed by the leader refinery is shown in Eq(8). The lower level problems are displayed in Eq(9). Within the equation block, the first line represents the objective of a producer to maximize profit. The second line represents the upper bound and ensures that the price charged for a specific oil relates to the amount of that oil sold. If no oil is sold, then the upper bound on the price of the oil will be equal to the minimum price, and if the maximum amount of oil is sold, the upper bound on the price will be equal to the maximum price. Any quantity of oil that is between zero and the maximum will have an upper bound on the price between the maximum and minimum price for the crude oil. Finally, the third line ensures that the oil cannot be sold for less than the lower bound. Eq(10) ensures non-negativity and defines the binary variables. ( )max i i i I sp P COST   − (1) ( ) ( ), ,j j k k k j k j j j j J k K k K j J COST C X a a X sc sdis pc pdis tc tdis      =   +   +  +     (2) ( ) ( ) , , min j k j k k K j J j k j k k K j J ghg a X lhv a X           (3) , 1 j k k K X j    (4) 74 _ i i P dem lb i  (5) _ i i P dem ub i  (6) ( ), , i i j k j k k K j J P cof a X i   =    (7) , k j k j k K a X pct bbld j      (8) ( ) ( ) , , : arg max 1 , k j k j k K k j k k K j j j j j j j j a X C a X C C cub cub clb j pct bbld C clb                  − −  −                (9) , , 0, {0,1} , , i j j k P C X i j k   (10) Where Cj refers to the cost of oil j and Xj,k is the binary variable decision to buy ak lots of oil j. sc, sdisj, pc, pdisj, tc, and tdisj are the shipping, piping, and trucking costs and distances, where the distances are indexed by j because each transportation distance will be oil-specific. ghgj denotes the kg of CO2-equivalent emissions created during the extraction, refining, and end use of crude oil j, which can be found using tools such as the Oil Production Greenhouse Gas Emissions Estimator (El-Houjeiri et al., 2013). lhvj is the lower heating value of oil j in megajoules per barrel. The parameter pct represents the percentage of the daily production of a certain crude oil that can be allocated to the leader refinery. Pi is the price of final product i, and cofi,j is a coefficient matrix that displays the amount of final product i that can be made from oil j based on the chemical composition of oil j. The upper bound and lower bound on the cost of oil are represented by cubj and clbj, and the maximum amount of oil j that can be sold in one day is bbldj. The resulting problem has both and environmental and economic objective. To solve this problem using modelling software, ε-constraint method is implemented on the environmental objective. The new constraint that will replace the environmental objective is as follows: ( ) ( ), ,j k j k j k j k k K j J k K j J lhv a X ghg a X            (11) By varying the parameter ε, varying degrees on environmental constraint can be imposed on the refinery, causing it to adhere to increasingly strict environmental standards. After this constraint is added, the model is fully linearized and can be solved as a single level MILP. 3. Case study The MILP developed in the previous section can be applied to oil refineries and crude oils around the world. In this study, the refinery is in Baton Rouge, Louisiana, which is home to some of the largest oil refineries in the world. The refinery is assumed to be a large-scale refinery, with a capacity of over 100,000 barrels processed per day. The oils considered in this case study come from counties that are surrounding or near to the Persian Gulf, including Saudi Arabia, Kuwait, Iran, Iraq, Russia, and the United Arab Emirates. All six of the countries considered in this study are top ten global yearly producers of crude oil (Kay, 2018). All optimization problems for the case study are modelled in GAMS 25.1.1 and solved with CPLEX 12.8.0.0. The % of daily crude oil production that the refinery can order from any site is set to a maximum of 20 %. The upper and lower bounds on crude oil price represent positive and negative 10 % deviations from a nominal price for each oil, which can be found online. Data for the greenhouse gas emission, lower heating value, and conversion coefficients of each of the crude oils used in the case study were found in online databases as well (Bergerson, 2017). The demands for gasoline, jet fuel, diesel, residual fuel oil, and liquefied petroleum gas (LPG) are set so that the total is approximately 100,000 barrels/d. Prices per barrel of distillate product are 75 calculated using the most recent data for U.S. petroleum product prices found on the U.S. Energy Information Administration website. The pareto curve shown in Figure 1 displays the trade-off between profit maximization and environmental cost minimization that occurs as the ε value in Eq(26) is incremented to become increasingly restrictive. At point C on the graph, the maximum profit for the problem is realized. At this point, there is no environmental restriction imposed, and Eq(26) does not hold at equality. For the other ten points on the graph, however, an environmental restriction is imposed to a varying degree. At point A on the graph, the environmental constraint is as restrictive as possible, and the profit is at a minimum on the graph. From point A to point C, the profit decreases by nearly 14.6 %. Point B on the graph represents a reasonable trade-off between the environmental and economic objectives. For a 4.4 % decrease in profit, the kilograms of CO2 per megajoule of energy decrease by 3.0 %. The price of going from point C to point B in the case study is approximately 3.5 ¢/kg CO2; that is, if the refiner was charged 3.5 ¢/kg CO2, then operating at point B and point C would yield the same profit, with point B being an environmentally cleaner operating point. Figure 1: Pareto Curve displaying the trade-off between profit maximization and environmental impact minimization. The crude oil distribution is shown in the pie charts associated with specific points on the diagram. The distribution of the oils purchased at different points is displayed on the pareto curve. Figure 1 displays three pie charts that correlate to amounts of each oil that are purchased at points A, B, and C. Based on the information in the chart, the presence of a strict environmental constraint causes almost all the oil that is bought to be Saudi Arabian, as shown in chart A. As the environmental constraint relaxes, however, a diverse grouping of the crude oils is purchased, and the amount of Saudi Arabian oil that is purchased greatly decreases. At point C, all oils are used, and no one crude oil is the outright majority. This can be attributed to the fact that the Saudi Arabian oil that is used is a lighter oil with a lower heating value. As a result, the Saudi Arabian oil is relatively environmentally friendly, but it does not contain as much energy per barrel as some of the other, heavier oils in the study. Therefore, in the absence of an environmental constraint, the Saudi Arabian oil is selected to a lesser extent because the other oils in the study can produce the same final products for a smaller overall cost. While the pareto curve displays the trade-off that occurs in the upper level problem, there are also decisions being made by the followers in the lower level problems. As the upper level refiner starts to demand cleaner oils, the demand, and subsequent price, of the less environmentally friendly oils will decrease, and the opposite happens for the clean oils. This can be seen in Figure 2, which displays the prices of Iranian oil and Saudi Arabian oil. The Saudi Arabian oil is more environmentally friendly, so as environmental restrictions increase, it is demanded more and the price increases. The Iranian oil behaves in the opposite way, and as the environmental restrictions increase, the demand for the Iranian oil decreases. The price of the Saudi Arabian oil is shown on the left axis, and the price of the Iranian oil is displayed on the right axis. The green dotted arrows show which line refers to the two crude oils in the study. Finally, a complete breakdown of the crude oil is provided in the form of a Sankey diagram in Figure 3. For the Sankey diagram, the trade-off point B is chosen. In this scenario, all six oils in the case study are utilized to 76 make the assortment of final products. One addition to the chart on the oil supply side is the “additives” stream. The conversion of each barrel of oil to final products is not a one-to-one conversion, and the overall mass coming out of the refinery will often be slightly greater than or less than the amount of oil that is delivered depending on how the oil is processed. Hydrocracking, for example, involves hydrogenating oil distillates with high carbon-to- hydrogen ratios to make higher quantities of lighter products. Therefore, a stream is added to account for the various processes that contribute to the overall mass changing. Figure 2: Price changes in Iranian and Saudi Arabian crude oil with respect to the environmental restrictions. Figure 3: Sankey chart displaying the conversion of various crudes into final products. The number associated with each stream represents the number of barrels of the specified crude oil or product. 4. Conclusions In this work, a bilevel program is developed to analyse the single-leader-multiple-follower structure of the multi- stakeholder crude oil supply chain. In the model, the crude oil refiner acts as the leader and decides how much oil to purchase to maximize its profit while at the same time minimizing the environmental impact of its operations and of the products it sells. The followers in the problem are crude oil producers. The crude oil producer aims to maximize the profit of their operation by selling their oil for the highest possible price. Using the resulting 77 bilevel programming model with a single leader and two objectives in the upper level, a case study was completed to showcase the trade-off between environmental and economic objectives. This case study also shows how the price of each oil varies based on the refiner’s demand for the crude oil. Finally, the breakdown of crude oils purchased by the refiner at different points on the pareto curve show that cleaner crude oils dominate when the refiner optimizes for the environmental objective and that a variety of oils are purchased when the refiner optimizes for profit. References Basar T., Olsder G. J., Clsder G.,1995, Dynamic noncooperative game theory, Vol. 23, SIAM, New York, the U.S. Bergerson, J., PRELIM: The Petroleum Refinery Life Cycle Inventory Model | LCAOST | University of Calgary, accessed March 20, 2019. Chu Y., You F., 2014, Integrated scheduling and dynamic optimization by Stackelberg game: Bi-level model formulation and efficient solution algorithm. Industrial & Engineering Chemistry Research, 53, 5564-5581. Colson B., Marcotte P., Savard G., 2007, An Overview of Bilevel Optimization, Annals of Operations Research, 153, 235–256. El-Houjeiri H., Brandt A., Duffy J., 2013, Open-Source LCA Tool for Estimating Greenhouse Gas Emissions from Crude Oil Production Using Field Characteristics. Environmental Science & Technology, 47, 5998– 6006. Hanley N., Folmer H., 1998, Game theory and the environment, Edward Elgar Publishing, Cheltenham, UK. Garcia D. J., You, F., 2015, Supply chain design and optimization: Challenges and opportunities. Computers & Chemical Engineering, 81, 153-170. Gao, J., You, F., 2017a, Game theory approach to optimal design of shale gas supply chains with consideration of economics and life cycle greenhouse gas emissions. AIChE Journal, 63, 2671-2693. Gao J., You F., 2017b, Economic and Environmental Life Cycle Optimization of Noncooperative Supply Chains and Product Systems: Modeling Framework, Mixed-Integer Bilevel Fractional Programming Algorithm, and Shale Gas Application, ASC Sustainable Chemistry & Engineering, 5, 3362-3381. Gao J., You F., 2019, A Stochastic Game Theoretic Framework for Decentralized Optimization of Multi- Stakeholder Supply Chains under Uncertainty, Computers and Chemical Engineering, 122, 31-46. Hennet J. C., Arda Y., 2008, Supply chain coordination: A game-theory approach. Engineering Applications of Artificial Intelligence, 21(3), 399-405. Kay, A., Top 10 Oil-Producing Countries, accessed March 21, 2019. Matos S., Hall J., 2007, Integrating sustainable development in the supply chain: The case of life cycle assessment in oil and gas and agricultural biotechnology. Journal of Operations Management, 25, 1083- 1102. Myerson R. B., 2013, Game theory, Harvard University Press, Boston, USA. Mittal S., Garg M., Sande P., 2016. Characterization And Comparison Of Shale Oil And Crude Oil, 6th World Petro Coal Conference. Yue, D., Gao, J., Zeng, B., You, F., 2019, A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs. Journal of Global Optimization, 73, 27-57. Yue D., Kim M. A., You F., 2013, Design of sustainable product systems and supply chains with life cycle optimization based on functional unit: general modeling framework, mixed-integer nonlinear programming algorithms and case study on hydrocarbon biofuels. ACS Sustainable Chemistry & Engineering, 1, 1003- 1014. Yue D., You, F., 2014, Game-theoretic modeling and optimization of multi-echelon supply chain design and operation under Stackelberg game and market equilibrium. Computers & Chemical Engineering, 71, 347- 361. Yue D., You F., 2017, Stackelberg-Game-Based Modeling and Optimization for Supply Chain Design and Operations: A Mixed Integer Bilevel Programming Framework, Computers and Chemical Engineering, 102, 81–95. Zhao N., You F., 2019, Dairy Waste-to-Energy Incentive Design using Stackelberg-Game-Based Modeling and Optimization. Applied Energy, 254, 113701. 78