CET 97 DOI: 10.3303/CET2297060 Paper Received: 14 June 2022; Revised: 12 August 2022; Accepted: 14 August 2022 Please cite this article as: Tan R.R., Aviso K.B., 2022, A Bilevel Mixed-Integer Linear Programming Model for Emissions Reduction, Chemical Engineering Transactions, 97, 355-360 DOI:10.3303/CET2297060 CHEMICAL ENGINEERING TRANSACTIONS VOL. 97, 2022 A publication of The Italian Association of Chemical Engineering Online at www.cetjournal.it Guest Editors: Jeng Shiun Lim, Nor Alafiza Yunus, Jiří Jaromír Klemeš Copyright © 2022, AIDIC Servizi S.r.l. ISBN 978-88-95608-96-9; ISSN 2283-9216 A Bilevel Mixed-Integer Linear Programming Model for Emissions Reduction Raymond R. Tan*, Kathleen B. Aviso Department of Chemical Engineering, De La Salle University, 2401 Taft Avenue, 0922 Manila, Philippines raymond.tan@dlsu.edu.ph Government-industry interactions for emissions control can be modelled as Stackelberg or leader-follower games. Government acts as the leader by setting regulations and economic incentives, while industry as the follower reacts to these policies by selecting cost-optimal emissions reduction techniques. The problem for the leader is to calibrate policies in anticipation of the follower’s rational reaction. In this work, a bilevel mixed integer linear programming (BMILP) model is developed for the deployment of a finite set of emissions reduction techniques. Government controls the emissions reduction target and subsidy rate for each emissions reduction technique, while industry selects which techniques to implement. The latter also has to pay a penalty if actual emissions exceed the regulatory target. An interactive fuzzy optimization algorithm is also developed for finding an approximate satisficing solution. The model and solution algorithm are illustrated using a case study. 1. Introduction Bringing climate change under control will require the massive scale-up of different greenhouse gas (GHG) mitigation measures in a short period of time (IPCC, 2022). This goal can be achieved through concerted deployment of different technologies (e.g., renewables, CO2 removal, energy efficiency improvements), but investment decisions need to be optimized to ensure maximum benefit given prevailing resource limits. Mathematical Programming (MP) models can be used to provide effective decision support for this purpose. A special class of MP models known as 0-1 programming is particularly useful for technology selection (Kantardgi et al., 2006). Also known as knapsack models, these MPs use binary variables to signify decisions, and have seen a wide range of engineering applications and extensions in the literature (Cacchiani et al., 2022a). Conventional MPs rely on the implicit assumption that there is a single decision-maker controlling the system. This assumption is unrealistic in many applications that involve interactions between government and industry. Game theory provides a rigorous modelling framework for the conflicts of interest that arise from such interactions. It allows governments, acting on behalf of public good, to calibrate policies and instruments that induce profit-motivated companies to make environment-friendly decisions (Chin et al., 2021). Government- industry interactions can be framed as leader-follower or Stackelberg games. These games can be formulated as bilevel MPs, where the follower’s optimization model is nested within the leader’s model as a constraint (Bard, 1998). The solution of a bilevel MP is known as the Stackelberg strategy, which represents the leader’s optimum given the assumption of a self-optimal response by the follower. In general, the Stackelberg strategy cannot be determined by direct use of solution algorithms meant for conventional MPs (Moore and Bard, 1990). Bilevel MPs have been developed for many environmental applications. Aviso et al. (2010) developed a model to optimize water recycling networks in Eco-Industrial Parks (EIPs). Gao and You (2017) formulated a bilevel MP for energy supply chains considering both economics and GHG emissions. Chalmardi et al. (2019) considered the problem of incentivizing clean technology investments in supply chains. Cobo et al. (2020) proposed a game theoretic model to optimize the utilization of organic fertilizers within a Circular Economy (CE) framework. Aviso et al. (2021) developed a game-theoretic technology selection model for alternative CO2 removal methods with subsidy calibration, while Tan et al. (2021) proposed the use of P-graph to solve network games involving interdependent technologies for reducing GHG emissions. 355 Stackelberg games involving technology selection can be formulated as bilevel knapsack problems (Anastasiadis et al., 2019). However, specialized algorithms are needed to solve these problems (Moore and Bard, 1990). One approach involves reformulation as conventional single-level MPs with the aid of dynamic programming (Brotcorne et al., 2010). These reformulation strategies rely on exploiting unique features that occur in special cases (Della Croce and Scatamacchia, 2020), and are not generally applicable. Interactive algorithms based on fuzzy set theory can be used as an alternative to determine approximate or satisficing solutions (Zheng et al., 2014). These procedures rely on initially determining bounding solutions of single-level MPs from the perspectives of the leader and follower, followed by a second step of determining a compromise solution between these extremes. This approach has also been adapted for bilevel MPs with general integer variables (Emam, 2006). Alternative formulations and solution algorithms for bilevel knapsack problems are reviewed in a recent paper (Cacchiani et al., 2022b). Metaheuristic or stochastic algorithms used in Artificial Intelligence (AI) can also be used to find near-optimal solutions for these models (Sinha et al., 2018). Despite these developments, one clear gap in the research literature is the absence of bilevel MP models of government- industry interactions for the large-scale deployment of technologies to achieve deep cuts in GHG emissions. In this paper, this research gap is addressed through the development of a Bilevel Mixed-Integer Linear Programming (BMILP) model for optimal subsidy and selection of technology options considering GHG emissions and cost limits. The interactive fuzzy algorithm proposed by Emam (2006) is modified to handle binary variables. The rest of this paper is organized as follows. Section 2 gives the formal problem statement. Section 3 discusses the model formulation, while Section 4 describes the interactive solution algorithm. Section 5 demonstrates the modelling framework on a cement industry case study. Finally, Section 6 gives the conclusions and suggests promising directions for future research. 2. Problem statement The formal problem statement is as follows. Given: • A set of GHG emissions mitigation options, each with specified techno-economic (i.e., performance and cost) parameters; • Government (i.e., leader) that seeks to minimize total cost to the public (including externalities) by mandating the GHG emissions limit, setting a penalty for failing to meet this target, and selecting technologies eligible for fractional subsidy; • Industry (i.e., follower) that seeks to minimize total private costs incurred from investments (including subsidies) and penalties for exceeding the mandated GHG emissions limit; The problem is to identify the government’s Stackelberg strategy, which consists of the mandated GHG emissions limit and technology-targeted subsidy, to which industry’s rational, cost-minimizing response gives the lowest total external cost to the public. The latter consists of the external cost of GHG emissions plus expenditure of public funds for subsidies. 3. BMILP model The model is initially formulated as follows in Eq(1) to Eq(5): max 𝑆𝑆𝑆𝑆𝑆𝑆(𝑅𝑅 − 𝑉𝑉) − �𝑠𝑠𝑖𝑖𝑥𝑥𝑖𝑖𝑦𝑦𝑖𝑖 𝑖𝑖 (1) subject to: min �(𝑐𝑐𝑖𝑖𝑦𝑦𝑖𝑖 − 𝑠𝑠𝑖𝑖𝑥𝑥𝑖𝑖𝑦𝑦𝑖𝑖) 𝑖𝑖 + 𝑃𝑃𝑉𝑉 (2) �𝑒𝑒𝑖𝑖𝑦𝑦𝑖𝑖 𝑖𝑖 + 𝑉𝑉 ≥ 𝑅𝑅 (3) 𝑥𝑥𝑖𝑖 ∈ {0,1} ∀𝑖𝑖 (4) 𝑦𝑦𝑖𝑖 ∈ {0,1} ∀𝑖𝑖 (5) where SCC is the external cost factor per unit of GHG, R is the emission reduction target as defined by the leader, V is the excess GHG emission from the desired target or violation, si is the fixed subsidy provided for technology i, ci is the investment cost for technology i, xi is a binary variable that indicates the leader’s selection (xi = 1) or non-selection (xi = 0) of technology i, and yi is a binary variable that indicates the follower’s selection (yi = 1) or non-selection (yi = 0) of technology i. All economic parameters should be normalized for dimensional 356 consistency. The leader’s objective function (𝐿𝐿) as defined by Eq(1) seeks to maximize the benefits from emissions reduction, consisting of the external benefits of actual realized GHG emissions reduction minus public funds spent on subsidies. The leader’s optimization problem is constrained by the follower’s objective function defined by Eq(2), which seeks to minimize direct incurred costs consisting of investment costs plus penalty payments for exceeding allowable emission levels. Actual emissions reduction achieved by the follower depends on selected technologies, and may fall short of mandated targets as shown by Eq(3). The binary decision variables of both players are formally defined by Eq(4) and Eq(5). This model can be linearized into a BMILP formulation by applying the transformation indicated in Eq(6) to Eq(9) to remove the quadratic terms in both objective functions. The dummy binary variable zi. replaces the bilinear product 𝑥𝑥𝑖𝑖𝑦𝑦𝑖𝑖 and reduces investment cost if the follower selects a subsidized technology (zi = 1). The solution algorithm is discussed in the next section. 𝑧𝑧𝑖𝑖 = 𝑥𝑥𝑖𝑖𝑦𝑦𝑖𝑖 ∀𝑖𝑖 (6) 𝑧𝑧𝑖𝑖 ≤ 𝑥𝑥𝑖𝑖 ∀𝑖𝑖 (7) 𝑧𝑧𝑖𝑖 ≤ 𝑦𝑦𝑖𝑖 ∀𝑖𝑖 (8) 𝑧𝑧𝑖𝑖 ∈ {0,1} ∀𝑖𝑖 (9) 4. Interactive solution algorithm This section describes the solution algorithm adapted from the one proposed by Emam (2006). The goal is to find a satisficing compromise solution between the extremes defined by the preferred solutions of the two players in the leader-follower game (Aviso et al., 2010). This interactive approach requires the decision-maker to be engaged in the use of the model rather than treating it as a black box (Geoffrion, 1976), and is consistent with the underlying philosophy of procedures such as Pinch Analysis (Klemeš et al., 2018). The main steps in the interactive algorithm are: (S1) Determine the follower’s preferred solution. This step is accomplished by optimizing the follower’s objective function under the assumption that all system variables are under the follower’s control. The leader’s objective function is excluded from this optimization step, but is evaluated afterwards from the partial solution identified. For this problem, the follower will generally prefer to maintain the status quo, without any mandated GHG emissions cuts, nor the need for investment in GHG emissions mitigation technologies. (S2) Determine the leader’s preferred solution. This step is accomplished by optimizing the leader’s objective function under the assumption that all system variables are under the leader’s control. The follower’s objective function is excluded from this optimization step but is evaluated afterwards from the partial solution identified. For this problem, the leader will generally prefer to implement all available GHG emissions reduction technologies without subsidies, maximizing total external benefits to the public from GHG emissions cuts. max 𝜆𝜆 (10) �L−L′ L∗−L′ � ≥ 𝜆𝜆 (11) �EL−EL′ EL∗−EL′ � ≥ 𝜆𝜆 (12) �N−N′ N∗−N′ � ≥ 𝜆𝜆 (13) � F−F ∗ F∗∗−F∗ � ≥ 𝜆𝜆 (14) 0 ≤ 𝜆𝜆 ≤ 1 (15) (S3) Formulate the auxiliary single-level fuzzy MP using the partial solutions of (S1) and (S2). In this model, the leader relinquishes control of the system to the follower, but also sets bounds in the form of fuzzy membership functions for the leader’s objective function and variables (Eq(11)–(13)). L is the leader’s objective function, L′ is an exogenously defined “worst-case” limit of the leader’s objective, and L∗ is the 357 leader’s ideal objective as determined in (S2); EL is the resulting emissions reduction target, EL′ is an exogenously defined “worst-case” emissions reduction target of the leader, and EL∗ is the leader’s ideal emissions reduction target as determined in (S2); N is the number of subsidized technologies, N′ is an exogenously defined “worst-case” limit on the number of technologies that can be subsidized, and N∗ is the ideal number of technologies to be subsidized as determined in (S2). The membership functions serve to push the follower’s choices towards values that approach the leader’s preferences. These membership functions are assumed to be linear here. The follower sets a fuzzy goal corresponding to its original objective function (Eq(14)) and then seeks to maximize the max-min aggregate membership degree in these fuzzy sets, λ (Eq(10)). F is the resulting objective function of the follower, F∗ is the follower’s “worst-case” objective function when the leader achieves its ideal solution in (S2), and F∗∗ is the follower’s ideal objective in (S1). Variable λ is bounded as defined by Eq(15). (S4) Solve the auxiliary model in (S3) to give the approximate Stackelberg solution to the problem. The solution resulting from steps (S1) to (S4) should be examined for plausibility and practicality. Parameters in (S3) may have to be adjusted interactively and the procedure repeated until a satisficing solution is determined. Note that there may be cases where a feasible solution does not exist (e.g., when targeted emissions reductions are physically impossible given available technologies). 5. Cement industry case study A cement industry case study is solved here as a test case. Production of Portland cement is highly GHG- intensive, with approximately 1 t CO2 being generated per t of product based on conventional technology (Huang and Wu, 2021). Major investments are needed to achieve deep emissions cuts in this sector. Table 1 shows the twelve GHG emissions reduction options based on electricity conservation measures. The techno-economic data is adapted from the review by Huang and Wu (2021) based on a hypothetical average grid GHG intensity of 0.55 kg/kWh. Only capital costs are considered in this illustrative case. It is also assumed that there is no mutual exclusivity or other forms of interaction among selected technologies, so that all benefits and costs are additive. The last column shows the potential subsidy of 10 % being considered by the government for each technology. All computations are normalized per t of clinker product to ensure dimensional consistency. It is assumed that the external cost of GHG emissions and the penalty for exceeding the mandated cut are both 100 EUR/t CO2. Table 1: Techno-economic parameters of GHG emissions reduction options (Huang and Wu, 2021) Technology option GHG emissions reduction (t CO2/t) Normalized capital cost (EUR/t) Potential subsidy (EUR/t) (1) High-efficiency classifiers/separators for grinding raw materials 0.0028 2.11 0.21 (2) Efficient homogenizing silo 0.0015 3.55 0.36 (3) Replacing ball mills with vertical roller mills 0.0061 7.63 0.76 (4) Adjustable speed drives for raw mill fans 0.0002 0.03 0.00 (5) High-temperature waste heat recovery for power generation 0.0169 4.22 0.42 (6) Low-temperature waste heat recovery for power generation 0.0122 3.17 0.32 (7) Organic Rankine Cycle 0.0046 5.09 0.51 (8) Adjustable speed drives for kiln fans 0.0027 0.22 0.02 (9) Adjustable speed drives for clinker cooler fans 0.0001 0.01 0.00 (10) High-pressure roller presses for pre-grinding before ball milling 0.0134 4.80 0.48 (11) Advanced grinding technologies 0.0107 11.58 1.16 (12) Adjustable speed drives for fans used in cement grinding 0.0001 0.01 0.00 Table 2 shows the players’ preferred solutions as the intermediate steps (S1) and (S2) of the interactive algorithm described in the previous section. Industry (i.e., the follower) prefers the status quo, without mandated emissions cuts nor any investment in GHG emissions mitigation technologies. The government (i.e., leader) prefers industry to implement all technologies simultaneously without any subsidy, leading to maximum cuts in GHG emissions without expending public funds. Both of these preferred solutions are highly unrealistic and cannot be implemented in practice. 358 The auxiliary model is formulated assuming that the leader requires that (a) both its objective function value and the mandated emissions limit are at least half of the values determined in (S2) and (b) that no more than three technologies are subsidized. Solving the auxiliary model described in the previous section yields the approximate Stackelberg strategy (with λ = 0.63) in the rightmost column of Table 2. The government’s best strategy is to mandate GHG emissions cut of 0.058 t CO2/t while subsidizing Technology 8 (Adjustable speed drives for kiln fans). In response, industry invests in the subsidized technology, as well as Technologies 1 (High- efficiency classifiers/separators for grinding raw materials), 5 (High-temperature waste heat recovery for power generation), 6 (Low-temperature waste heat recovery for power generation), and 10 (High-pressure roller presses for pre-grinding before ball milling). These measures have a combined subsidized investment cost of 14.50 EUR/t, but fall short of meeting the mandated GHG emissions cut by 0.010 t CO2/t. It is more economical for industry to pay the penalty rather than to invest in additional technologies. In this approximate Stackelberg strategy, the leader’s objective (monetized benefit to the general public per unit of product) is just 4.79 EUR/t due to industry’s violation of the mandated GHG emissions limit and the expenditure of public funds for subsidies. The actual emissions cut is 0.048 t CO2/t. Table 2: Players’ preferred solutions and approximate Stackelberg strategy Follower’s preferred solution Leader’s preferred solution Approximate Stackelberg strategy Leader’s objective function (EUR/t) 0 5.70 4.79 Follower’s objective function (EUR/t) 0 42.44 15.51 Mandated GHG emissions reduction (t CO2/t) 0 0.071 0.058 Actual GHG emissions reduction (t CO2/t) 0 0.071 0.048 GHG emissions limit violation (t CO2/t) 0 0 0.010 Base investment cost (EUR/t) 0 42.44 14.52 Total subsidy (EUR/t) 0 0 0.02 Subsidized investment cost (EUR/t) 0 42.44 14.50 6. Conclusions A BMILP has been developed in this work to model a class of Stackelberg games for inducing industry investment in pollution reduction measures. In the model, government (acting as the leader) provides targeted subsidies to influence industry (acting as the follower) to select GHG mitigation measures from a set of alternatives with predefined performance and cost parameters. An interactive fuzzy algorithm is presented to determine satisficing heuristic solutions. The BMILP reflects the interplay of decision-making that is present in real systems, where government does not have direct control over investment decisions by industry. A cement industry case study illustrates how the model can be used to generate better insights for cost-effective subsidy policies. These principles can be extended to other GHG-intensive industries to facilitate climate change mitigation. Future work should focus on the development of alternative solution methods for the BMILP. Deterministic procedures can be developed using dynamic programming; alternatively, AI-based metaheuristic algorithms can be explored. Nomenclature Parameters Leader variables ci Investment cost for technology i, EUR/t si Subsidy for technology i, EUR/t ei GHG reduction of technology i, t CO2/t xi Binary variable for the leader’s selection or non-selection of technology i, dimensionless P Penalty cost for excess GHG emission, EUR/t V Amount of GHG emissions in violation of desired target reduction, t CO2/t SCC External cost factor of GHG emissions, EUR/t R Carbon emission reduction target, t CO2/t Follower variables yi Binary variable for the follower’s selection or non-selection of technology i, dimensionless Auxiliary model parameters Auxiliary model variables L* Leader’s ideal objective function λ Aggregate degree of membership L’ Leader’s worst-case objective function L Leader’s objective function EL* Leader’s ideal emissions reduction target EL Emissions reduction target 359 EL’ Leader’s worst-case emissions reduction target N Number of subsidized technologies N* Leader’s ideal number of subsidized technologies F Follower’s objective function N’ Leader’s worst-case number of subsidized technologies F* Follower’s worst-case objective function F** Follower’s ideal objective function References Anastasiadis E., Deng X., Krysta P., Li M., Qiao H., Zhang J., 2019, Network pollution games, Algorithmica, 81, 124–166. Aviso K.B., Tan R.R., Culaba A.B., Cruz Jr. J.B., 2010, Bi-level fuzzy optimization approach for water exchange in eco-industrial parks, Process Safety and Environmental Protection, 88, 31–40. Aviso K.B., Chiu A.S.F., Ubando A.T., Tan R.R., 2021, A bi-level optimization model for technology selection, Journal of Industrial and Production Engineering, 38, 573–580. Bard J.F., 1998, Practical bilevel optimization: Algorithms and applications, Springer, Dordrecht, Netherlands. Brotcorne L., Hanafi S., Mansi R., 2010, One-level reformulation of the bilevel knapsack problem using dynamic programming, Discrete Optimization, 10, 1–10. Cacchiani V., Iori M., Locatelli A., Martello S., 2022a, Knapsack problems — An overview of recent advances. Part I: Single knapsack problems, European Journal of Operational Research, 143, 105692. Cacchiani V., Iori M., Locatelli A., Martello S., 2022b, Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems, European Journal of Operational Research, 143, 105693. Chalmardi K., Camacho-Vallejo J.-F., 2019, A bi-level programming model for sustainable supply chain network design that considers incentives for using cleaner technologies, Journal of Cleaner Production, 213, 1035– 1050. Chin H.H., Varbanov P.S., Klemeš J.J., Bandyopadhyay S., 2021, Subsidised water symbiosis of eco-industrial parks: A multi-stage game theory approach, Computers & Chemical Engineering, 155, 107539. Cobo S., You F., Dominguez-Ramos A., Irabien A., 2020, Noncooperative game theory to ensure the marketability of organic fertilizers within a sustainable circular economy, ACS Sustainable Chemistry and Engineering, 8, 3809–3819. Della Croce F., Scatamacchia R., 2020, An exact approach for the bilevel knapsack problem with interdiction constraints and extensions, Mathematical Programming, 183, 249–281. Emam O.E., 2006, A fuzzy approach for bi-level integer non-linear programming problem, Applied Mathematics and Computation, 172, 62–71. Gao J., You F., 2017, 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. Geoffrion A.M., 1976, The purpose of mathematical programming is insight, not numbers, Interfaces, 7, 81–92. Huang Y.-H., Wu J.-H., 2021, Bottom-up analysis of energy efficiency improvement and CO2 emission reduction potentials in the cement industry for energy transition: An application of extended marginal abatement cost curves, Journal of Cleaner Production, 296, 126619. IPCC, 2022, Summary for Policymakers. In: Climate Change 2022: Mitigation of Climate Change. Contribution of Working Group III to the Sixth Assessment Report of the Intergovernmental Panel on Climate Change. Cambridge University Press. Cambridge, UK and New York, NY, USA. Kantardgi I., Purvis M.R.I., Cherviakov L., Khudoshina M., 2006, Approaches to the modelling of energy utilisation in product life cycles, Clean Technologies and Environmental Policy, 8, 77 – 84. Klemeš J.J., Varbanov P.S., Walmsley T.G., Jia X., 2018, New directions in the implementation of Pinch Methodology (PM), Renewable and Sustainable Energy Reviews, 98, 439–468. Moore J.T., Bard J.F., 1990, The mixed integer linear bilevel programming problem, Operations Research, 38, 911–921. Sinha A., Malo P., Deb K., 2018, A review on bilevel optimization: From classical to evolutionary approaches and applications, IEEE Transactions of Evolutionary Computation, 22, 276–295. Tan R.R., Aviso K., Walmsley T., 2021, P-graph approach to solving a class of Stackelberg games in carbon management, Chemical Engineering Transactions, 89, 463–468. Zheng Y., Liu J., Wan Z., 2014, Interactive fuzzy decision making method for solving bilevel programming problem, Applied Mathematical Modelling, 38, 3136–3141. 360 060.pdf A Bilevel Mixed-Integer Linear Programming Model for Emissions Reduction