Mixed-integer bilevel optimization for capacity planning with rational markets

• Capacity expansion planning formulated as a bilevel optimization problem.
• Higher level involves industrial company, lower level the market.
• Formulation is a mixed-integer bilevel linear program with an LP at lower level.
• Reformulation single-level problem with KKT or duality-based reformulation.
• Application industrial gases shows duality-based reformulation much faster.

We formulate the capacity expansion planning as a bilevel optimization to model the hierarchical decision structure involving industrial producers and consumers. The formulation is a mixed-integer bilevel linear program in which the upper level maximizes the profit of a producer and the lower level minimizes the cost paid by markets. The upper-level problem includes mixed-integer variables that establish the expansion plan; the lower level problem is an LP that decides demands assignments. We reformulate the bilevel optimization as a single-level problem using two different approaches: KKT reformulation and duality-based reformulation. We analyze the performance of these reformulations and compare their results with the expansion plans obtained from the traditional single-level formulation. For the solution of large-scale problems, we propose improvements on the duality-based reformulation that allows reducing the number of variables and constraints. The formulations and the solution methods are illustrated with examples from the air separation industry.