(655d) Capacity Expansion with Rational Markets in the Industrial Gas Industry

The standard approach to develop capacity expansion plans leverages optimization tools in order to maximize the profit obtained during a finite time horizon. The problem with this formulation is that it assumes that companies decide what share of the market they satisfy. In reality, buyers select their providers from a pool of potential suppliers based on their own interest. Therefore, it is important to consider market preferences in order to develop reliable expansion plans.

We address the problem of establishing a capacity expansion plan that maximizes the net present value (NPV) of an industrial gas company with multiple facilities, subject to markets that determine the company’s income according to their own cost. The capacity expansion problem with a rational market resembles a strategic game in which companies establish their capacity expansion plans, and then the markets decide from which provider their demands are satisfied. We consider the strategic game with perfect information; the suppliers are aware of the decision criterion of the rational markets and the markets observe the actions of the suppliers before their decisions are made.

We formulate the capacity expansion problem with rational markets as a bilevel optimization problem. The upper level problem maximizes the leader’s NPV and the lower level problem minimizes the cost paid by the markets. The decisions in the upper level problem are the investment related to capacity expansion, while in the lower level the markets decide from which provider they buy. The lower level decisions are based on the economic interest of the markets and the prices offer by the different providers.

The resulting formulation is a mixed-integer bilevel linear programming (MIBLP) problem in which the upper level variables are mixed-integer, and the lower level variables are all continuous. In order to solve this problem, we develop two solution strategies that transform the bilevel problem into a single-level optimization problem. Both reformulations rely on the conditions met by linear programs (LPs) at the optimal solution.

The first strategy replaces the lower level problem with its Karush-Kuhn-Tucker (KKT) optimality conditions. KKT conditions ensure optimality of the lower level problem by satisfying stationarity, primal feasibility, dual feasibility, and complementary slackness of the solution. The main difficulty with this reformulation is the nonlinearities introduced with the complementary slackness conditions. We reformulate the nonlinear complementary slackness conditions as big-M constraints using the active-set approach. The final formulation is a single-level MILP problem that can be solved directly. However, the use of big-M constraints introduces a large number of binary variables that complicate the solution of the problem.

The second strategy leverages the strong duality property of linear programs. In this case, the lower level LP is replaced by both its primal and dual constraints; strong duality is enforced with a constraint that equates the primal and dual objective functions. The complication of this approach comes from the nonlinearities that appear in the dual objective function of the lower level problem. These nonlinearities arise because the upper level variables are treated as parameters in the lower level. Therefore, the single-level reformulation includes the multiplication of upper level variables and lower level dual variables. However, the nonlinearities can be reformulated using exact linearization when all the upper level variables are discrete.

The KKT and the Primal-Dual strategies are implemented in an instance of the capacity expansion problem with rational markets. The results show that both reformulations yield exactly the same solution as expected. However, the primal-dual reformulation is computationally much more efficient. The significant difference in solution times is a consequence of the large number of binary variables introduced in the KKT strategy. The KKT reformulation introduces one binary variable for each lower level inequality constraint, whereas the primal-dual reformulation does not introduce any new binary variables.

The expansion plan obtained from the bilevel formulation is also compared with the plan obtained from the standard single-level capacity expansion formulation. The results show that the single-level formulation yields higher investment cost because it overestimates the attainable market share. In comparison to the bilevel approach, such an expansion plan yields significantly lower NPV when evaluated in a rational market environment. These results clearly demonstrate the importance of considering markets’ behavior to develop capacity expansion plans that are more robust in the dynamic conditions of the markets.