A market regulation bilevel problem: a case study of the Mexican petrochemical industry

A market regulation bilevel problem: a case study of the Mexican petrochemical industry H´ector Maravilloa, Jos´e-Fernando Camacho-Vallejoa,∗, Justo Puertob, Martine Labb´ec aFacultad de Ciencias F´ısico-Matem´aticas, Universidad Aut´onoma de Nuevo Le´on, Monterrey, Mexico bDepartment of Statistics and Operational Research &Instituto de Matem´aticas Universidad de Sevilla, Universidad de Sevilla, Seville, Spain cD´epartament d’Informatique, Universit´e Libre de Bruxelles, Brussels, Belgium and INRIA, Lille, France Abstract In this paper, a bilevel programming model is proposed to study a problem of market regulation through government intervention. One of the main characteristics of the problem herein analyzed is that the government monopolizes the raw material in one industry, and competes in another industry with private firms for the production of commodities. Under this scheme, the government controls a state-owned firm to balance the market; that is, to minimize the difference between the produced and demanded commodities. On the other hand, a regulatory organism that coordinates private firms aims to maximize the total profit by deciding the amount of raw material bought from the state-owned firm. Two equivalent single-level reformulations are proposed to solve the problem. The first reformulation is based on the strong duality condition of the lower level and results in a continuous nonlinear model. The second reformulation resorts to the complementarity slackness optimality constraints yielding a mixed-integer linear model. Additionally, three heuristic algorithms are designed to obtain good-quality solutions with low computational effort. In this problem, the feasible region of the dual problem associated to the follower is independent from the leader’s decision. Therefore, the proposed heuristics exploit this particular characteristic of the bilevel model. Moreover, the third heuristic hybridizes the other two algorithms to enhance its performance. Extensive computational experimentation is carried out to measure the efficiency of the proposed solution methodologies. A case study based on the Mexican petrochemical industry is presented. Additional instances generated from the case study are considered to validate the robustness of the proposed heuristic algorithms. Numerical results indicate that the hybrid algorithm outperforms the other two heuristics. However, all of them demonstrate to be good alternatives for solving the problem. Additionally, optimal solutions of all the instances are obtained by using good quality solutions (given by the hybrid algorithm) as initial solutions when solving the second reformulation via a general purpose solver. Keywords: Market regulation, Bilevel programming, Petrochemical industry Preprint submitted to Elsevier November 13, 2018 1. Introduction1 Market regulation through government intervention has appeared in different ways, such2 as, fiscal policies (taxes and subsidies), anti-monopoly legislation, price control, quantity3 control, and nationalization of firms [1]. Two of the main motivations for regulating the4 economy is to seek social equity and to handle market failures [2]. A specific manner of5 government intervention is through the participation of state-owned firms, which are under6 the government control and compete with the private firms. The goal to regulate the market7 by participation has been very noticeable in developing countries, mainly in raw materials8 industries [3]. For instance, a list of countries in which market regulation by participation9 exists in oil industry is presented in [4], [5], [6]. At this point we would like to emphasize10 that this situation occurred in Mexico in the petrochemical industry from 1958 until 2014.11 12 The first paper that considers the idea of regulate the market by including a state-owned13 firm is [7]. In that paper, a short-term analysis that concerns with the entrance of a state-14 owned firm into a three-firms oligopoly market is done. They conclude that the existence of15 a state-owned firm may improve the performance of the market, which it is also shown in [8]16 in the aerospace market. Following up with the existence of state-owned firms, [9] considers17 a situation in which the difference between the production and the production level is made18 up by the government. The novelty in that paper is to realize that state-owned firm acts19 as the dominant decision-maker, that is, it has complete information of the market and20 announces its decision. Hence, each private firm reacts to this decision by establishing its21 output level so that its marginal cost equals the price. Furthermore, [10] explicitly considers22 the state-owned firm as a leader in a Stackelberg game. Later, in [11], a mixed oligopoly23 model that helps to compare the differences among the nationalization of a state-owned firm24 and the entrance of a new state-owned firm is studied. This last paper also analyzes the cost25 effectiveness of the state-owned firms in the long-term and moreover, the authors consider26 for the first time a budgetary constraint associated with the state-owned firm to guarantee27 a minimum profit.28 29 Literature reviews regarding mixed oligopolies can be found in [12] and [13]. In those30 reviews the common characteristics of these models are identified. Particularly, the context31 of the problem, the cases when the government provides complete information, the goal of32 the state-owned firm, the technology assumptions, the costs structure, and the hierarchy33 among the firms (in case of Stackelberg games). Another literature review that deals with34 some foundations for a theory of mixed oligopoly markets is presented in [14]. It is important35 to remark that all the above mentioned papers coincide in that there is a lack of an unified36 and accepted general mixed oligopolies modeling framework because each model pursues its37 own characteristics and set different basic hypothesis. At this point, it is also important to38 ∗I am corresponding author Email addresses: [email protected] (H´ector Maravillo), [email protected] (Jos´e-Fernando Camacho-Vallejo ), [email protected] (Justo Puerto), [email protected] (Martine Labb´e) 2 emphasize that, to the best of our knowledge and after an intensive literature review, the39 intervention of the government via state-owned firms to regulate an industry conformed by40 two interrelated markets has not been studied before. However, these characteristics appear41 in real situations, as it will be described in the case study herein considered.42 43 The problem studied in this paper is inspired by a situation where a state-owned firm44 controls the monopoly of a market but this is interrelated with a second market in which45 state-owned and private firms compete. The problem considers two interdependent indus-46 tries, in which the first one produces the necessary supplies for the second one. The gov-47 ernment has the monopoly of the first industry, while in the second industry a state-owned48 firm competes with remaining private firms in the production of commodities. Private firms49 aim to maximize their profit. Government aims as a general social welfare to balance the50 market. The latter is achieved by minimizing the difference between the supply and demand51 of the final commodities.52 53 Given the privileged position that the government occupies in this market as the leader54 decision-maker, the government decides the amount of commodities that will be produced at55 the state-owned firms and the amount of supplies that will be offered to the private firms. By56 doing this, the government will regulate indirectly the production. One can easily appreciate57 a hierarchical relationship between both economic agents, in which the government makes a58 decision and the private firms reacts to it affecting the balance in the market. Furthermore,59 technical and technological issues in the raw material market limit the production, for ex-60 ample, the scarcity of natural resources and the existing production capacity of the firms.61 The hierarchy and inter-relationship among the actors of this situation allow to formulate a62 bilevel programming model, in which the government will act as the leader and the private63 firms as the follower. Other bilevel models in which the government intervenes to regulate64 social aspects are [15] and [16]. In the former, the government employs an intervention pol-65 icy based on subsidies in the automotive market, while in the latter, the government apply66 taxes via an agro-environmental policy imposed to the agriculturists. Additionally, the gen-67 eral model proposed by us perfectly fits to the petrochemical industry in several developing68 countries in the last decades and it was the case of Mexico for almost 56 years, where it was69 apparently run without a theoretically recognizable model.70 71 The main contributions of this paper can be listed as follows: a novel mathematical72 bilevel programming model to study a mixed-oligopoly market, three heuristic algorithms73 based on an iterative exploration of vertices in the inducible region of the bilevel problem, an74 extensive computational study analyzing the performance of our exact reformulations and75 the proposed heuristic algorithms, and a case-study based on the Mexican petrochemical76 industry.77 78 The remainder of the paper is organized as follows. Section 2 defines the mathematical79 programming bilevel model and sets the notation. Two reformulations of the bilevel model80 that reduce it to a single-level one are presented in section 3. The first one is a continuous81 3 non-linear problem, and the second one reduces to a mixed integer linear program. In82 both cases, the resulting programs are hard to solve for medium to large sizes. Then,83 section 4 describes three proposed heuristic algorithms to provide good quality solutions84 for the bilevel model. Section 5 reports the numerical results according to the case study85 under consideration, and compares the results obtained through the reformulations and86 the algorithms. Also, the results obtained from additional experimentation with random87 instances are summarized. Conclusions and recommendations for future research are given88 in section 6.89 2. A market regulation bilevel problem90 2.1. Problem’s description91 The problem herein studied considers an industry conformed by two economic markets,92 one of them associated to raw material and the other one of the final commodities. The93 supplies (raw material) of the second economic market are produced in the first one. In94 this industry, there is a state-owned firm vertically integrated, that is, that produces in95 both economic markets. The state-owned firm monopolizes the production of the supplies96 in the first economic market, but in the other one, this firm competes against the private97 firms. All the firms have a maximum production capacity and the state-owned firm requires98 to obtain a minimum profit (there is a lower bound over its net profit). The objective of99 this latter firm is to balance the market by its intervention. To achieve this goal, it mini-100 mizes the lack and surplus of the offered commodities with respect to the demand. Hence,101 this firm determines its production of commodities and the amount of supplies to be offered102 to the private firms. On the other hand, private firms’ goal will be to maximize their benefit.103 104 The decisions taken by the state-owned firm limit the admissible production by the pri-105 vate firms, and the decisions of the private firms affect the achievement of the government.106 As it is mentioned before, the government has the monopoly of the supplies production, and107 it is assumed that there exists a centralized organism that regulates the supplies demand.108 This organism determines the amount of supplies to each private firm, which is common109 in economic markets with government intervention. A typical example occurs when the110 government creates organisms to regulate the competition among firms and establishes par-111 ticular contracts with each private firm fixing the supplies to be sold to each one. Another112 case is when the private firms get together and create a centralized mechanism to which113 the responsibility of distributing supplies among them is delegated. In the latter case, that114 mechanism seeks for a global welfare of the market; this is the case of common lands coop-115 erative organization in agriculture. Under this scheme, the government will be the leader116 and the centralized mechanism the follower.117 2.2. Mathematical formulation118 In this section, the mathematical formulation of the problem described in the previous119 section is formally introduced. Let Ibe the set of commodities and let Jbe the set of120 private firms. Each commodity i∈Iis sold at a price pi, and it has a demand diin the121 4 market. To produce a commodity i∈I, it costs cG ito the state-owned firm and cE ij to a122 private firm j∈J. The government fixes a minimum profit tto be obtained by the state-123 owned firm. The amount of primary resources that a private firm j∈Jneeds to produce124 a unit of commodity i∈Iis denoted by bij and the amount of supply required to produce125 a unit of commodity i∈Iis denoted by aij . Both types of firms have a limited production126 capacity. The state-owned firm has a maximum production capacity qB ito obtain supplies127 of the commodity i∈Iand a maximum amount qA ito produce for each commodity i∈I.128 Also, each private firm j∈Jhas a maximum production capacity mj.129 130 In order to present our mathematical programming formulation, we will use the following131 decision variables. The leader’s decision variables are:132 xi, which denotes the production of the state-owned firm for each commodity i∈I.133 zi, which denotes the supply offered by the government to the private firms to produce a134 commodity in ∈I.135 136 The follower’s decision variables are:137 yij, which denotes the amount produced by private firm j∈Jof a commodity i∈I.138 139 In our model, non-negative auxiliary variables are introduced to express the leader’s ob-140 jective function. Let ribe the shortage of commodity i∈Iand let sibe the corresponding141 surplus.142 143 With the above elements, the proposed bilevel programming formulation to model the144 regulation of the economic market described above results as follows:145 min x,z,r,s,y X i∈I (ri+si) (1) s.t.Pj∈Jyij +xi di +ri−si= 1 ∀i∈I(2) X i∈I (pi−cG i)xi≥t(3) 0≤xi≤qA i∀i∈I(4) 0≤zi≤qB i∀i∈I(5) ri≥0∀ ∈ Ii (6) si≥0∀i∈I(7) y∈argmax X j∈JX i∈I (pi−cE ij)¯yij (8) s.t. X j∈J aij ¯yij ≤zi∀i∈I(9) X i∈I bij ¯yij ≤mj∀j∈J(10) 5 ¯yij ≥0∀i∈I, ∀j∈J(11) The leader’s problem is defined by (1)-(8), in which (1) represents the leader’s objective146 function that aims to minimize the inefficiency of the market, namely the overall shortage147 and surplus production with respect to the total demand. Constraint (2) seeks to balance the148 demand of each commodity with the corresponding production of the state-owned and pri-149 vate firms. In (3), it is ensured that the state-owned firm obtains a minimum required profit150 from its commodities production. Constraints (4) and (5) establish the production capacity151 associated with the commodities and offered supplies, respectively. The non-negativity of152 the auxiliary variables is expressed in (6) and (7). Constraint (8) plays a key role in this153 model, due to the fact that it requires that the value of the follower’s variables is given by the154 optimal solution of another mathematical programming problem. The follower’s problem155 is defined by equations (8)-(11), which aims to maximize the total profit of all the private156 firms. The production of the private firms is limited by the amount of supplies provided by157 the government, this is enforced by (9). Constraint (10) imposes that each private firm’s158 production cannot exceed its maximum capacity. Finally, (11) expresses the non-negativity159 of the follower’s variables.160 161 In order to have a well-defined formulation for the proposed bilevel model, it is neces-162 sary to make an assumption regarding multiple optimal solutions that may appear in the163 follower’s problem. We assume the optimistic approach defined in [17]. In other words,164 among all the optimal follower’s solutions, the one that minimizes the leader’s objective165 function is selected. The optimistic approach is suitable for the situation under study since166 it may express the existence of a certain cooperation degree among the government and the167 mechanism (committee) that represents the private firms.168 3. Exact solution methodologies169 A common methodology that applies, at times, to solve a bilevel programming model is170 to transform it to a single-level reformulation. In order to achieve this goal, the character-171 istics of the follower’s problem have to be exploited. Once a leader’s solution is established,172 the leader’s variables are fixed in the follower’s problem. Particularly, zis going to be con-173 sidered as a parameter in the problem defined by (8)-(11). Therefore, the follower’s problem174 results in a linear programming problem that has a corresponding dual, in which αand β175 correspond to the associated dual variables. The dual problem associated with the follower’s176 problem is as follows:177 178 min α,β X i∈I αizi+X j∈J βjmj(12) s.t. aijαi+bijβj≥(pi−cE ij)∀i, ∀j(13) αi≥0∀i(14) βj≥0∀j(15) 6 For both, the primal and dual of the follower’s problem, the space of feasible solutions179 is bounded. Hence, the fundamental duality theorem states that both problems have op-180 timal solutions and their objective function values are equal [18]. Hence, two single-level181 reformulations that are equal to the bilevel model are presented in this section. The first182 reformulation ensures that the optimal solution of the reformulated model are in the in-183 ducible region of the bilevel problem by using a corollary of the strong duality theorem.184 The second reformulation substitutes a non-linear constraint of the first reformulation via185 the complementarity slackness constraint. The first reformulation results in a continuous186 non-linear model and the second one is a mixed-integer linear model.187 3.1. Non-linear reformulation based on the strong duality condition188 The first reformulation consists in adding the constraints associated with the dual of the follower’s problem, that is, (12-15), and to use the necessary and sufficient optimality conditions to ensure that the follower’s decision belongs to the set of rational reactions. Therefore, a constraint that equals the follower’s primal and dual objective functions is added. For a predefined leader’s fixed value of zthe resulting constraint is as follows: X j∈JX i∈I (pi−cE ij)yij =X i∈I αizi+X j∈J βjmj(16) The first proposed reformulation consists in the following non-linear single-level problem: min x,z,r,s,y,α,β X i∈I (ri+si) (Ref.1) s.t. Pj∈Jyij +xi di +ri−si= 1 ∀i∈I(17) X i∈I (pi−cG i)xi≥t(18) 0≤xi≤qA i∀i∈I(19) 0≤zi≤qB i∀i∈I(20) ri≥0∀i∈I(21) si≥0∀i∈I(22) X j∈J aijyij ≤zi∀i∈I(23) X i∈I bijyij ≤mj∀j∈J(24) yij ≥0∀i∈I, j ∈J(25) aijαi+bijβj≥(pi−cE ij)∀i∈I, j ∈J(26) αi≥0∀i∈I(27) βj≥0∀j∈J(28) 7 X j∈JX i∈I (pi−cE ij)yij =X i∈I αizi+X j∈J βjmj(29) Note that the linearity of the model is lost in (29). Further, it can be represented in the189 following manner since weak duality implies that the other inequality is always satisfied.190 −X j∈JX i∈I (pi−cE ij)yij +X i∈I αizi+X j∈J βjmj≤0 (30) 3.2. Mixed-integer linear reformulation based on complementarity slackness191 The second reformulation is based on the complementarity slackness constraints that192 ensures the optimality of the follower’s problem. A single-level reformulation is recovered193 by introducing the following constraints:194 αi zi−X j∈J aijyij!= 0 ∀i∈I(31) βj mj−X i∈I bijyij!= 0 ∀j∈J(32) yij aijαi+bijβj−(pi−cE ij)= 0 ∀i∈I, j ∈J(33) Constraints (31), (32), and (33) are non-linear, nevertheless they can be linearized in a195 straightforward manner by introducing positive big-Mconstants M1 i,M2 i, and M3 ifor all196 i∈I. Also, binary variables γi,δj, and ij for all i∈I,j∈Jare included. Constraints197 (31)-(33) are replaced by the following constraints:198 αi≤M1 iγi∀i∈I(34) zi−X j∈J aijyij ≤M1 i(1 −γi)∀i∈I(35) βj≤M2 iδj∀i∈I, j ∈J(36) mj−X i∈I bijyij ≤M2 i(1 −δj)∀i∈I, j ∈J(37) yij ≤M3 iij ∀i∈I, ∀j∈J(38) aijαi+bijβj−(pi−cE ij)≤M3 i(1 −ij)∀i∈I, j ∈J(39) Therefore, this reformulation results in the following single-level linear mixed-integer programming model. min x,z,r,s,y,α,β,γ,δ, X i∈I (ri+si) (Ref.2) s.t. Pj∈Jyij +xi di +ri−si= 1 ∀i∈I(40) 8 X i∈I (pi−cG i)xi≥t(41) 0≤xi≤qA i∀i∈I(42) 0≤zi≤qB i∀i∈I(43) ri≥0∀i∈I(44) si≥0∀i∈I(45) X j∈J aijyij ≤zi∀i∈I(46) X i∈I bijyij ≤mj∀j∈J(47) yij ≥0∀i, j ∈J(48) aijαi+bijβj≥(pi−cE ij)∀i∈I, j ∈J(49) αi≥0∀i∈I(50) βj≥0∀j∈J(51) αi≤M1 iγi∀i∈I(52) zi−X j∈J aijyij ≤M2 i(1 −γi)∀i∈I(53) βj≤M1 jδj∀j∈J(54) mj−X i∈I bijyij ≤M2 j(1 −δj)∀j∈J(55) yij ≤M1 ijij ∀i∈I, j ∈J(56) aijαi+bijβj−(pi−cE ij)≤M2 ij(1 −ij)∀i∈I, j ∈J(57) γi, δj, ij ∈ {0,1} ∀i∈I, j ∈J(58) 3.3. Adjusting the value of the big M’s199 In the problem under study, parameters aand bare always positives, which means that if200 more commodity production exists, more supplies are required and more production capacity201 is used in the private firms. Moreover, if term pi−cE ij is negative, private firms are having202 losses, which would lead to their exit from the economic market.203 Definition. Define the upper bound UB(·)∈Rof a vector as a real number that is is204 greater than or equal to all of the components of that vector.205 To adjust the value of M1 ifor all i∈I, first we seek for an upper bound for αi, such that206 αbelongs to an optimal solution of the follower’s dual problem. The worst scenario occurs207 when βj= 0 ∀j∈J, then αi≥pi−cE ij aij for all i∈I, ∀j∈Jmust hold due to (49). Since (12)208 aims to minimize, the optimal solution occurs at equality. To obtain the upper bound for209 M2 ifor all i∈I, constraint (53) is considered. Hence, it is possible to state the following210 proposition.211 9 the performance of the proposed heuristic algorithms, a set of 360 instances was used. The321 first subset of 180 instances corresponds to a case based on a real situation occurred in the322 Mexican petrochemical industry between 1958-2014. The second subset of 180 instances was323 randomly generated to test the efficiency of our algorithms in more general data sets.324 325 All the computational experiments were conducted in a personal computer Dell Inspiron326 5558, with the following characteristics: a processor Intel(R) Core i3 with 2.10 GHz, 6.00327 GB of RAM under Windows 10 operative system. The mixed-integer linear reformulation328 based on the complementarity slackness condition (hereafter Ref.2), and the three proposed329 heuristic algorithms were implemented in C++ using Microsoft Visual Studio 2017. The330 optimizer used was CPLEX 12.7.1. On the other hand, the non-linear reformulation based331 on the strong duality condition (hereafter Ref.1) was implemented in AMPL using Baron332 18.5.8 as optimizer.333 5.1. Case study334 In Mexico, the government intervention in the petrochemical industry existed by many335 decades. The main characteristic was that the government monopolized the extraction of336 the main raw material for this industry, namely petroleum and some other derivatives called337 basic petrochemicals. Another characteristic of this situation was that state-owned firms338 competed against private firms in the market of final commodities (secondary petrochemi-339 cals).340 341 The institutional framework defined by law the petrochemical industry as the one that342 performs chemical or physical processes to product compounds from petroleum natural hy-343 drocarbons or from the products derived from refinement operations. Some of these products344 may serve as raw materials to the industry, and they were classified as part of the basic petro-345 chemicals. The remaining products were included into the secondary petrochemical category346 [19].347 348 Specifically, in a law from 1958 [20], it was established that only the government was349 allowed to exploit the hydrocarbons related with the oil industry, which was concerned with350 the production, warehousing, distribution, and sales of the petroleum derivatives that can351 be considered as raw materials (basic petrochemicals) for the industry. However, for the352 production of secondary petrochemicals products, state-owned and private firms were al-353 lowed to be involved in. Therefore, Petr´oleos Mexicanos (PEMEX) and its subsidiaries was354 in charge of this industry [21], and from 1992, also their descentralized departments [22].355 The classification of basic and secondary petrochemical products varies by law from year to356 year [23], [21], [19], [24], [25], [26], [27].357 358 To delimit the scope and size of our case study instances based on the above situation,359 we consider the number of economic units involved in the manufacturing of organic chemical360 basic products registered by the National Institute of Statistics and Geography in Mexico361 (INEGI by its acronym in Spanish) during the economical census conducted in 1999, 2004,362 16 2009, and 2014. The biggest number of these units was registered in 2004, which was363 159. This value is used as an upper bound of the private firms dedicated to secondary364 petrochemical industry. For delimiting the amount of commodities considered, we consider365 the number of commodities classified as basic and secondary petrochemical by the Mexican366 legislation in different years. This information is summarized in table 1.367 Table 1: Classification of petrochemical commodities Year of the classification Basic petrochemicals Secondary petrochemicals 1960 16 - 1986 34 26 1989 8 13 1992 20 35 Obtained by using data from [21], [24], [25], [26] To complete the instances, we extracted data from the statistical report of the energy368 sector used by the Mexican Secretary of Energy. The data of 47 petrochemical commodi-369 ties from 1980 to 2002 were obtained. The information consists of the demand, prices, and370 productive capacity. For each commodity i, the demand diwas generated from a uniform371 distribution with the following parameters: the average of the demands in that period of372 time minus the standard deviation, and the average of the demands in that period of time373 plus the standard deviation. The price piand the government production capacity qA iwere374 randomly generated between 1 and the maximum price or the maximum capacity for each375 commodity i, respectively.376 377 The government costs cG iwere obtained as the product of the price of each commodity378 itimes a random number between 0.22 and 0.60. The latter range was defined based on379 the ratio between the production costs and the PEMEX (the Mexican state-owned firm)380 total income registered from the years 1988-2000, 2011-2013, and 2015-2016. The minimum381 profit that the state-owned firm must achieved was computed as the 30% of the total benefit382 that the government may obtain if all the petrochemicals market demand was satisfied by383 PEMEX.384 385 The state-owned firm has a production capacity qB iregarding raw materials i, which386 was computed as the product of the maximum production coefficient of the private firms387 and the maximum capacity of the state-owned firm for producing commodities. Under this388 assumption, the private firm with best technology could match the production capacity of389 the state-owned firm for an specific commodity.390 391 Production costs cE ij of private firm jare defined as the product of random coefficients392 in [0.784,0.884] multiplied times the price of each commodity i. That range corresponds to393 17 the minimum and maximum average values of the ration between the production costs and394 the income per year of five real private firms. These private firms operate in the Mexican395 petrochemical sector: Alpek, Kuo (UEN synthetic rubber), Kuo (UEN polystyrene), Mexi-396 chem, and Pochteca group.397 398 The production technical coefficients aij are randomly generated between [0.085,2.111],399 which correspond to the range determined by the average plus/minus one standard deviation400 of all the petrochemical substances considered in the report presented by CEPAL [?]. The401 production levels bij are generated from the interval [1,95]. The lower bound is natural since402 these coefficients must be strictly positives, while the upper bound is equal to the estimated403 average of the production levels for each substance considered in the petrochemical facilities404 of PEMEX.405 406 Finally, the production capacity mjof the private firms were randomly generated be-407 tween 4,665 and 20,825, which came from the average of the production capacity of five408 petrochemical complex of PEMEX.409 410 Based on the above factors and ranges, we generated 30 instances for each one of the411 following sizes:412 • |I|= 10, |J|= 10413 • |I|= 25, |J|= 25414 • |I|= 25, |J|= 75415 • |I|= 50, |J|= 100416 • |I|= 75, |J|= 125417 • |I|= 150, |J|= 200418 As it is mentioned above, the instances generated to analyze the case study were taken419 as a basis for constructing another set of synthetic instances to test the performance of our420 algorithms on a different data set. This new set of instances has the same sizes but were421 randomly generated using arbitrary ranges for each parameter. Furthermore, the generation422 scheme guarantees feasibility of the problem, that is, ensure that the state-owned firm has423 capacity to produce all the demand.424 5.2. Numerical results425 Our computational experiment consists on solving both subsets of instances described426 above, that is, the case-study and the synthetic instances. All of them were solved by the427 two reformulations presented in section 3 and by the three heuristic algorithms proposed428 in section 4. The leader’s objective function value and the required time were registered.429 Among the two exact methods, only Ref.2 was able to optimally solve all the tested instances.430 18 Hence, these values were used to compute the optimality gap obtained by the heuristic al-431 gorithms. A maximum CPU time of 1000 seconds was set to the solver for solving Ref.1,432 while Ref.2 and the heuristic algorithms we did not fix a time limit since in all cases the433 required time was rather small.434 435 We observe from our results, that Ref.1 was not able to solve all the instances within the436 time limit. We also observe that the case-study instances are harder to be solved than the437 synthetic ones. For example, for the larger instance sizes (150×200), Ref.1 did not even find438 feasible solutions for the problem. This may be due to the fact that synthetic instances were439 well-balanced so that, in most cases, shortages and surplus are both zero. Summarizing, the440 number of instances solved to optimality by each reformulation is shown in table 2.441 Table 2: Number of instances solved to optimality Instances Size Ref.1 Ref.2 Case-study 10 ×10 15 30 25 ×25 0 30 25 ×75 0 30 50 ×100 0 30 75 ×125 0 30 150 ×200 0 30 Synthetic 10 ×10 30 30 25 ×25 29 30 25 ×50 30 30 50 ×100 29 30 75 ×125 28 30 150 ×200 13 30 The following tables 3 and 4 report all the results of our experiment. The results are or-442 ganized in five column blocks corresponding to the five solution methods that are compared.443 In each block, we include two columns with the objective function values (F) and the CPU444 time (t). In these tables, averages of the registered values for each size of the case-study and445 synthetic instances are shown. It is worth mentioning that when Ref.1 was not able to solve446 the instance, that instance was omitted for the computation of the corresponding average447 value.448 19 Table 3: Summarized results obtained from the case-study instances Size Ref.1 Ref.2 EPIA FGPA HYBA ¯ F¯ t (s) ¯ F¯ t (s) ¯ F¯ t (s) ¯ F¯ t (s) ¯ F¯ t (s) 10 ×10 0.561 255.56 0.506 0.18 0.774 0.23 0.825 0.16 0.524 0.41 25 ×25 14.225 500.26 1.000 1.86 1.570 0.30 1.171 0.35 1.020 0.71 25 ×75 12.435 500.46 0.527 4.36 1.025 0.48 0.565 0.39 0.552 1.02 50 ×100 211.696 558.80 1.051 53.15 2.041 2.39 1.132 1.14 1.091 5.18 75 ×125 431.138 501.24 1.546 268.89 2.339 8.89 1.811 3.68 1.621 20.69 150 ×200 - - 3.279 2754.68 4.129 61.82 5.037 12.06 3.443 112.25 Table 4: Summarized results obtained from the synthetic instances Size Ref.1 Ref.2 EPIA FGPA HYBA ¯ F¯ t (s) ¯ F¯ t (s) ¯ F¯ t (s) ¯ F¯ t (s) ¯ F¯ t (s) 10 ×10 0 0.26 0 0.14 0.007 0.08 0.006 0.10 0 0.09 25 ×25 0.012 29.01 0 1.43 0 0.11 0.021 0.14 0 0.11 25 ×75 0 10.94 0 3.65 0 0.17 0.019 0.20 0 0.17 50 ×100 0.057 73.60 0 35.52 0 0.29 0.170 0.31 0 0.28 75 ×125 0 118.76 0 90.48 0 0.60 0.086 0.76 0 0.57 150 ×200 1.657 414.55 0 193.48 0 1.78 0.443 1.74 0 1.57 We observe from tables 3 and 4 that Ref.1 (recall that Ref.1 is a continuous non-linear449 global optimization problem, while Ref.2 is a MILP) gets values, on average, closed to those450 obtained by Ref.2 for the synthetic instances. However, for the case-study instances the451 situation is different and the average solution values and times move away from the optimal452 averages as the size of the instance increases. Note that for most of the synthetic instances,453 the optimal value is zero, i.e., the supply is perfectly balanced with the demand. Hence,454 neither shortages nor surplus exist due to the generation mechanism of these instances.455 456 Regarding the heuristic algorithms, it can been observed from table 4 that EPIA and457 HYBA report values, on average very close, to the optimal ones for all the sizes of the458 synthetic instances. However, for the case-study instances, HYBA reports the best results459 among all the three heuristic algorithms (see table 3). Moreover, the performance of EPIA460 and FGPA significantly depends on the size of the instance. In terms of the average re-461 quired time, FGPA requires less time for the case-study instances. This finding may be462 derived from the fact that the algorithm explores points not necessarily in the inducible463 region, which may help to approach the optimal solution in a faster manner. On the con-464 trary, HYBA is the algorithm that requires the more time, but this may be obvious since it465 performs all the steps of EPIA and at each iteration it may solve upon four extra mathemat-466 ical programs. Nevertheless, the registered times are acceptable for a problem of this nature.467 468 20 To compare the efficiency and the quality of the solutions obtained by the heuristic algorithms, the optimality gap is computed using the values obtained by Ref.2. Given that there are many optimal values equal to zero, the optimality gap (GAP) measures the relative deviation from the optimal value, and it is computed by the following formula: GAP =  (Optimal value) −(Obtained value) (Obtained value)  ×100% (105) Also, an analogous formula is used to compute the relative savings in time (%t). That is,469 the reduction in computational time when solving the problem using the heuristics rather470 than Ref.2. A negative value indicates that the heuristic consumes more time than the exact471 reformulation. The formula used is presented next:472 473 %t = (Required time by Ref.2) −(Required time by a heuristic) (Required time by a heuristic) ×100% (106) The GAP and %taverage values obtained for both type of instances are shown in tables474 5 and 6, respectively.475 Table 5: Evaluating the effectiveness of the heuristic algorithms in the case-study instances Size EPIA FGPA HYBA GAP %tGAP %tGAP %t 10 ×10 42.27% 12% 29.60% 15% 7.68% -48% 25 ×25 40.15% 746% 11.70% 534% 1.67% 190% 25 ×75 53.78% 1156% 19.67% 1101% 7.04% 445% 50 ×100 54.29% 3418% 10.72% 5418% 6.02% 1176% 75 ×125 33.20% 5269% 12.26% 10696% 5.64% 1499% 150 ×200 19.29% 9210% 17.20% 30206% 4.92% 3324% Table 6: Evaluating the effectiveness of the heuristic algorithms in the synthetic instances Size EPIA FGPA HYBA GAP %tGAP %tGAP %t 10 ×10 6.67% 79% 10.00% 42% 0% 69% 25 ×25 0% 1332% 46.67% 1038% 0% 1283% 25 ×75 0% 2189% 50.00% 1895% 0% 2192% 50 ×100 0% 13714% 90.00% 12176% 0% 14466% 75 ×125 0% 16773% 90.00% 14272% 0% 18485% 150 ×200 0% 11561% 100.00% 11377% 0% 12781% 21 HYBA is the algorithm that shows the best quality in the feasible solutions obtained.476 For the case study instances, the average optimality gap was lower than 8% for all the sizes477 (see table 5); while for the synthetic instances, the average optimality gap was zero (see ta-478 ble 6). FGPA presents a very good average gap in comparison with EPIA in the case-study479 instances, but this behavior is opposite in the synthetic instances. Concerning the savings480 in the required time, the three heuristic algorithms showed significant savings, which is im-481 proved as the size of the instance increases. FGPA is the one that evidence more savings for482 the case-study instances. It is convenient to mention that for the synthetic instances of size483 10 ×10, HYBA showed a negative saving, this implies that Ref.2 was faster to solve these484 instances. But, this is expected since HYBA solves at least one linear model and one MILP485 model, and Ref.2 only solves one MILP model. In spite of that, the advantage of HYBA486 over the reformulation is evident for medium and large-size instances.487 488 To support the latter findings, the number of optimal solutions obtained by each heuris-489 tic algorithm are displayed in table 7. It can be seen from that table that HYBA is the490 algorithm that was able to obtain more optimal solutions. Also, it an be observed that491 FGPA obtained more optimal solutions for the case-study instances than EPIA, but for the492 synthetic instances the behavior was the opposite. These results confirm the suitability for493 combining both heuristic algorithms to create HYBA.494 Table 7: Number of optimal solutions obtained for each heuristic algorithm Instance Size EPIA FGPA HYBA Case-study 10 ×10 7 11 20 25 ×25 0 12 19 25 ×75 5 13 19 50 ×100 1 13 15 75 ×125 0 4 9 150 ×200 0 0 1 Synthetic 10 ×10 28 27 30 25 ×25 30 16 30 25 ×75 30 15 30 50 ×100 30 3 30 75 ×125 30 3 30 150 ×200 30 0 30 5.3. Using heuristic solutions to obtain the optimal495 The good performance of the heuristic algorithms lead us to analyze the idea of use the496 near-optimal obtained solutions as an input to Ref.2 seeking to enhance their process. By497 doing this, we expect to significantly reduce the computational time required to optimally498 solve an instance. The results obtained from this experimentation are shown in table 8.499 The columns with label “Ref.2”, “HYBA”, and “Ref.2 w/initial sol.” display the average500 22 required time for each solution scheme. The final column “Total” sums the time required501 for the hybrid algorithm and Ref.2 using an initial good solution. As it was expected, the502 advantages of using this scheme are more notorious for medium and large-size instances. The503 best example of this finding is given by the instances of size 150 ×200, in which the time504 was reduced from 2754.68s to 586.53s, and from 193.48s to only 7.28s, for the case-study505 and synthetic instances, respectively.506 Table 8: Average required time when Ref.2 uses an initial heuristic solution Instance Size Ref.2 HYBA Ref.2 w/initial sol. Total Case study 10 ×10 0.18 0.33 0.07 0.40 25 ×25 1.86 0.82 0.39 1.21 25 ×75 4.36 1.54 0.80 2.34 50 ×100 53.15 6.07 4.24 10.31 75 ×125 268.89 20.24 19.73 39.97 150 ×200 2754.68 196.38 390.15 586.53 Random 10 ×10 0.14 0.09 0.04 0.13 25 ×25 1.43 0.12 0.10 0.22 25 ×75 3.65 0.19 0.49 0.68 50 ×100 35.52 0.33 1.15 1.48 75 ×125 90.48 0.46 2.22 2.68 150 ×200 193.48 1.95 7.28 9.23 6. Conclusions and research directions507 This paper studies a market regulation situation, in which the government controls the508 distribution of raw material and competes against private firms in the production of final509 commodities. In this market, the government has a privileged position since it determines its510 production and the amount of raw material offered to private firms and its goal is to balance511 the market. Although this type of market situation is common in some economies, to the512 best of our knowledge and after an intensive literature revision, we did not find a similar513 problem in the literature. The situation that motivated our paper comes from the actual514 situation in Mexican petrochemical industry with PEMEX from 1958 till 2014. However,515 this case is not exclusive from the petrochemical industry. Also in the agricultural industry,516 the Mexican government monopolized the production, imports, and distribution of fertil-517 izers from 1970 to 1986 through the state-owned company named FERTIMEX [28]. The518 government also regulated the water supply for agricultural consumption by fixing prices,519 defining production goals, and restricting the land transactions [29]. In addition, this type520 of economic regulation has been applied in other countries. For example, in [3], it is stated521 that there is a tendency to use government instruments in developing countries, mainly522 in raw material industries. An indicator of the latter can be seen in the large amount of523 oil expropriations in the 70’s (see [4], [5], [6]). Also, nationalizations occurred in Bolivia,524 Ecuador, Venezuela, and Russia in 2006 (see [6]).525 526 23 Motivated by the lack of models to analyze these type of markets, this paper develops527 a bilevel programming approach that fits naturally to the problem. To solve the bilevel528 problem herein proposed, two single-level reformulations are presented. The first reformula-529 tion uses the lower level necessary and sufficient optimality conditions to ensure the global530 optimum of the bilevel problem. As a result of this reformulation, a continuous non-linear531 problem is obtained. The second reformulation substitutes the above-mentioned conditions532 by the complementarity slackness conditions generating a MILP. These reformulations are533 able to solve optimally limited size instances. Therefore, three heuristic algorithms are pro-534 posed to find good quality feasible solutions in a reasonable computational time. The first535 two algorithms (EPIA and FGPA) are tailored for this problem, and exploits the fact that536 the polyhedron associated to the dual problem of the lower level remains the same for any537 leader’s decision. The third algorithm (HYBA) is a combination of the previous ones.538 539 Extensive computational experimentation is performed to test the exact and heuristic540 approaches proposed in this paper. Two sets of instances are used: case-study instances,541 that arise from the Mexican petrochemical industry, and synthetic instances adapted from542 the previous ones. As a result from the computational experimentation, it can be stated that543 the reformulation that applies the complementarity slackness constraints is more efficient for544 the tested instances. On the other hand, the performance of EPIA and FGPA strongly de-545 pends on the characteristics of the instance. In addition, the hybridization of both heuristic546 algorithms (HYBA) yields to the best results in terms of effectiveness and solutions quality.547 Moreover, HYBA found the optimal solution for all the synthetic instances, and obtained548 optimality gaps less than 8% in the case-study ones. It is worth to mention that HYBA549 found the optimal value in at least 50% for the first four types of instance sizes.550 551 Finally, it can be concluded from our computational experiment, that the most efficient552 manner to find optimal solutions for the bilevel problem is by obtaining a good quality553 feasible solution through HYBA and then using it as an initial solution to solve Ref.2. By554 doing this, a significant computational time reduction is achieved.555 556 Note that this bilevel problem may have multiple optimal solutions, each of them offers557 different alternatives to the upper level decision-maker (government) for producing and558 offering raw material to the lower level decision-makers (private firms). Therefore, this559 characteristic is economically worthy to be explored. Another possible research direction560 is to neglect, in the model, the assumption there exists an organism that manages the561 cooperation among private firms. Hence, a new element will emerge in the model since562 competition among private firms will also exist. As a result of this, a bilevel problem with563 one leader and multiple followers will appear. Then, in a natural way, a Stackelberg game564 in which the follower’s problem consists of a generalized Nash game fits to analyze this565 situation.566 24 Acknowledgements567 Jos´e-Fernando Camacho-Vallejo has been partially supported by the program of profes-568 sional development of professors with the grant PRODEP/511-6/17/7425 for research stays569 during his sabbatical year. Justo Puerto has been partially supported by Spanish/FEDER570 grants number MTM2016-74983-C02-01 (MINECO). Martine Labb´e has been partially sup-571 ported by the Fonds de la Recherche Scientique - FNRS under Grant(s) no PDR T0098.18.572 References573 [1] E. G. Wiens, Government firm regulation of a vertically integrated industry, Carleton Economic Paper574 (1978) 78–109.575 [2] J. E. Stiglitz, Regulation and failure, in: D. Moss, J. Cisternino (Eds.), New Perspectives on Regulation,576 Tobin Project, 2009.577 [3] R. Vernon, Uncertainty in the resource industries: the special role of state-owned enterprises, in: D. W.578 Pearce, H. Siebert (Eds.), Risk and the Political Economy of Resource Development, Springer, 1984,579 pp. 207–223.580 [4] S. J. Kobrin, The nationalisation of oil production, 1918-80, in: D. W. Pearce, H. Siebert (Eds.), Risk581 and the Political Economy of Resource Development, Springer, 1984, pp. 137–164.582 [5] M. S. Minor, The demise of expropriation as an instrument of ldc policy 1980-1992, Journal of Inter-583 national Business Studies 25 (1) (1994) 177–188.584 [6] S. Guriev, A. Kolotilin, K. Sonin, Determinants of nationalization in the oil sector: A theory and585 evidence from panel data, The Journal of Law, Economics, and Organization 27 (2) (2011) 301–323.586 [7] W. C. Merrill, N. Schneider, Government firms in oligopoly industries: A short-run analysis, The587 Quarterly Journal of Economics 80 (3) (1966) 400–412.588 [8] B. Blackwell, The state and the macro-industrial economy: Lessons from the aerospace sector, Omega589 14 (6) (1986) 421–442.590 [9] R. G. Harris, E. G. Wiens, Government enterprise: An instrument for the internal regulation of industry,591 The Canadian Journal of Economics 13 (1) (1980) 125–132.592 [10] M. R. Sertel, Regulation by participation, Journal of Economics 48 (2) (1988) 111–134.593 [11] H. Cremer, M. Marchand, J.-F. Thisse, The public firm as an instrument for regulating an oligopolistic594 market, Oxford Economic Papers 41 (2) (1989) 283–301.595 [12] G. De Fraja, F. Delbono, Game theoretic models of mixed oligopoly, Journal of Economic Surveys 4 (1)596 (1990) 1–17.597 [13] G. De Fraja, F. Delbono, Mixed oligopoly: An overview, Tech. rep., Quaderni-Working Paper DSE598 (1988).599 [14] L. Nett, Mixed oligopoly with homogeneous goods, Annals of Public and Cooperative Economics 64 (3)600 (1993) 367–393.601 [15] E. Z. Demirci, N. K. Erkip, Designing an intervention strategy for public-interest goods: The california602 electric vehicle market case, Omega 69 (2017) 53–69.603 [16] G. Whittaker, R. F¨are, S. Grosskopf, B. Barnhart, M. Bostian, G. Mueller-Warrant, S. Griffith, Spatial604 targeting of agri-environmental policy using bilevel evolutionary optimization, Omega 66 (2017) 15–27.605 [17] S. Dempe, Bilevel programming: A survey, Dekan der Fak. f¨ur Mathematik und Informatik, 2003.606 [18] J. F. Bard, Practical Bilevel Optimization, Nonconvex Optimization and Its Applications, Springer US,607 1998.608 [19] Reglamento de la ley reglamentaria del art´ıculo 27 constitucional en el ramo del petr´oleo, en materia609 de petroqu´ımica, Diario Oficial, m´exico, 9 de febrero de 1971.610 [20] Ley reglamentaria del art´ıculo 27 constitucional en el ramo del petr´oleo, Diario Oficial, m´exico, 29 de611 noviembre de 1958.612 25