A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization

Furini F., Ljubić I., San Segundo P., Zhao Y.

• We design an exact algorithm for the Edge Interdiction Clique Problem (EICP). • The EICP aims at reducing the clique number by removing a subset of the edges. • We manage to solve the EICP in several sets of instances from the literature. • Extensive tests show that the algorithm outperforms the state-of-the-art approaches. Given a graph G and an interdiction budget k ∈ N , the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities . We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP.

Kleinert T., Grimm V., Schmidt M.

Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches.

Baggio A., Carvalho M., Lodi A., Tramontani A.

Multilevel programming can provide the right mathematical formulations for modeling sequential decision-making problems. In such cases, it is implicit that each level anticipates the optimal reaction of the subsequent ones. Defender–attacker–defender trilevel programs are a particular case of interest that encompasses a fortification strategy, followed by an attack, and a consequent recovery defensive strategy. In “Multilevel Approaches for the Critical Node Problem,” Baggio, Carvalho, Lodi, and Tramontani study a combinatorial sequential game between a defender and an attacker that takes place in a network. The authors propose an exact algorithmic framework. This work highlights the significant improvements that the defender can achieve by taking the three-stage game into account instead of considering fortification and recovery as isolated. Simultaneously, the paper contributes to advancing the methodologies for solving trilevel programs.

Kleinert T., Labbé M., Plein F., Schmidt M.

Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.

Ambrosius M., Grimm V., Kleinert T., Liers F., Schmidt M., Zöttl G.

In the course of the energy transition, load and supply centers are growing apart in electricity markets worldwide, rendering regional price signals even more important to provide adequate locational investment incentives. This paper focuses on electricity markets that operate under a zonal pricing market design. For a fixed number of zones, we endogenously derive the optimal configuration of price zones and available transfer capacities on a network in order to optimally govern investment and production decisions in the long run. In a multilevel mixed-integer nonlinear model that contains a graph partitioning problem on the first level, we determine welfare-maximizing price zones and available transfer capacities for a given electricity market and analyze their impact on market outcomes. Using a generalized Benders decomposition approach developed in Grimm et al. (2019) and a problem-tailored scenario clustering for reducing the input data size, we are able to solve the model to global optimality even for large instances. We apply the approach to the German electricity market as an example to examine the impact of optimal zoning on key performance indicators such as welfare, generation mix and locations, or electricity prices. It turns out that even for a small number of price zones, an optimal configuration of zones induces a welfare level that almost approaches the first best.

Leal M., Ponce D., Puerto J.

This paper presents novel bilevel leader-follower portfolio selection problems in which the financial intermediary becomes a decision-maker. This financial intermediary decides on the unit transaction costs for investing in some securities, maximizing its benefits, and the investor chooses his optimal portfolio, minimizing risk and ensuring a given expected return. Hence, transaction costs become decision variables in the portfolio problem, and two levels of decision-makers are incorporated: the financial intermediary and the investor. These situations give rise to general Nonlinear Programming formulations in both levels of the decision process. We present different bilevel versions of the problem: financial intermediary-leader, investor-leader, and social welfare; besides, their properties are analyzed. Moreover, we develop Mixed Integer Linear Programming formulations for some of the proposed problems and effective algorithms for some others. Finally, we report on some computational experiments performed on data taken from the Dow Jones Industrial Average, and analyze and compare the results obtained by the different models.

Kleinert T., Labbé M., Plein F., Schmidt M.

There's No Free Lunch in Bilevel Optimization

Tahernejad S., Ralphs T.K., DeNegre S.T.

In this paper, we describe a comprehensive algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) using a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range of bilevel optimization problems. The framework has been fully implemented in the open-source solver MibS. The paper describes the algorithmic options offered by MibS and presents computational results evaluating the effectiveness of the various options for the solution of a number of classes of bilevel optimization problems from the literature.

Kleinert T., Schmidt M.

Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, and so on. Often these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization, one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with a mixed-integer linear or quadratic upper level and a linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2,800 instances—which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method in terms of both running times and solution quality. This renders the method a suitable subroutine in global bilevel solvers as well as a reasonable standalone approach.Summary of Contribution: Bilevel optimization problems form a very important class of optimization problems in the field of operations research, which is mainly due to their capability of modeling hierarchical decision processes. However, real-world bilevel problems are usually very hard to solve—especially in the case in which additional mixed-integer aspects are included in the modeling. Hence, the development of fast and reliable primal heuristics for this class of problems is very important. This paper presents such a method.

Smith J.C., Song Y.

This paper discusses the development of interdiction optimization models and algorithms, with an emphasis on mathematical programming techniques and future research challenges in the field. After presenting basic interdiction concepts and notation, we recount the motivation and models behind founding research in the network interdiction field. Next, we examine some of the most common means of solving interdiction problems, focusing on dualization models and extended formulations solvable by row-generation techniques. We then examine contemporary interdiction problems involving incomplete information, information asymmetry, stochasticity, and dynamic play. We conclude by discussing several emerging applications in the field of network interdiction.

Aussel D., Brotcorne L., Lepaul S., von Niederhäusern L.

Demand-side management (DSM) is a powerful tool to efficiently manage the consumption of energy. DSM relies on various techniques and means. In this work, we propose a trilevel energy market model for load shifting induced by time-of-use pricing. Four kinds of actors are involved: electricity suppliers (sell energy), local agents (buy, sell and consume), aggregators (buy and sell) and end users (consume). The interactions among these actors lead to a trilevel multi-leader–multi-follower game. Solving such games is known to be hard, thus we assume that the decision variables of all electricity suppliers but one are known and optimize the decisions of the remaining supplier. This leads to a single-leader–multi-follower game, which aims to compute the leader’s best response to the decisions of his competitors. The trilevel model is first formulated as a bilevel problem using an explicit formula for the lowest optimization level. Solution algorithms are developed in the optimistic case and in a variant named “semi-optimistic” approach leading to more robust solutions. Finally, numerical results highlight the efficiency of the methods and the sensitivity of the solutions with respect to the model parameters.

Dan T., Lodi A., Marcotte P.

In the design of service facilities, whenever the behaviour of customers is impacted by queueing or congestion, the resulting equilibrium cannot be ignored by a firm that strives to maximize revenue within a competitive environment. In the present work, we address the problem faced by a firm that makes decisions with respect to location, service levels and prices and that takes explicitly into account user behaviour. This situation is modelled as a nonlinear mathematical program with equilibrium constraints that involves both discrete and continuous variables, and for which we propose an efficient algorithm based on an approximation that can be solved for its global optimum.

Burtscheidt J., Claus M., Dempe S.

We consider bilevel linear problems, where some parameters are stochastic, and the leader has to decide in a here-and-now fashion, while the follower has complete information. In this setting, the leader's outcome can be modeled by a random variable, which we evaluate based on some law-invariant convex risk measure. A qualitative stability result under perturbations of the underlying probability distribution is presented. Moreover, for the expectation, the expected excess, and the upper semideviation, we establish Lipschitz continuity as well as sufficient conditions for differentiability. Finally, for finite discrete distributions, we reformulate the bilevel stochastic problems as standard bilevel problems and propose a regularization scheme for bilevel linear problems.

Poirion P., Toubaline S., D’Ambrosio C., Liberti L.

We study a class of bilevel mixed-integer linear programs with the following restrictions: all upper level variables x are binary, the lower level variables y occur in exactly one upper level constraint γ x + β y ≥ c , and the lower level objective function is min y β y . We propose a new cut generation algorithm to solve this problem class, based on two simplifying assumptions. We then propose a row-and-column generation algorithm that works independently of the assumptions. We apply our methods to two problems: one is related to the optimal placement of measurement devices in an electrical network, and the other is the minimum zero forcing set problem, a variant of the dominating set problem. We exhibit computational results of both methods on the application-oriented instances as well as on randomly generated instances.

Paulavičius R., Gao J., Kleniati P.-., Adjiman C.S.

We describe BASBL , our implementation of the deterministic global optimization algorithm Branch-and-Sandwich for a general class of nonconvex/nonlinear bilevel problems, within the open-source MINOTAUR framework. The solver incorporates the original Branch-and-Sandwich algorithm and modifications proposed in (Paulavicius and Adjiman, J. Glob. Opt., 2019, Submitted). We also introduce BASBLib , an extensive online library of bilevel benchmark problems collected from the literature and designed to enable contributions from the bilevel optimization community. We use the problems in the current release of BASBLib to analyze the performance of BASBL using different algorithmic options and we identify a set of default options that provide good overall performance. Finally, we demonstrate the application of BASBL to a set of flexibility index problems including linear and nonlinear constraints.

Tang Y., Wang Y., Liu C., Wang Y., Gui W.

Benati S., Leal M., Puerto J.

Kwon S., Choi H., Park S.

Beck Y., Ljubić I., Schmidt M.

Because of their nested structure, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. To tackle the Γ-robust counterpart of the bilevel problem, we present heuristic methods that are based on the solution of a linear number of problems of the nominal type. Moreover, quality guarantees for heuristically obtained solutions as well as sufficient ex-post conditions for global optimality of the outcomes are provided. In an extensive computational study on 2,240 instances, we assess the performance of our heuristics and compare them with alternative methods—both heuristic and exact—from the literature. We observe that the optimality gap is closed for a significant portion of the considered instances and that our methods often practically outperform alternative approaches in terms of the solution quality. Moreover, for the special case of Γ-robust interdiction problems, we report considerable speed-up factors when compared with recently published problem-tailored and exact solution approaches while also solving more instances to global optimality. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0239 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0239 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Villegas J.G., Álvarez-López G., Jaramillo L.Y., Romero-Sáez M.

Biomass ash is a byproduct of renewable energy generation that can be used in the cement and concrete industries as a supplementary cementitious material (SCM) to reduce their environmental impact. However, using biomass ashes as an SCM presents challenges, such as the distant location of crops and processing plants from cement and concrete plants, the absence of a supply chain to connect the biomass ash and cement/concrete producers, and the lack of a mechanism to set the price of the ash. We adopted a supply chain perspective to evaluate the environmental and economic impact of incorporating biomass ashes as an SCM in the cement and concrete industries. We developed a bilevel optimization model considering the strategic behavior of the two stakeholders of the supply chain: the biomass ash generator, which maximizes its profits by setting the price of the ash, and the cement/concrete manufacturer and minimizes its total operating costs, including the processes necessary to adapt its supply chain for the use of new raw material. We validated the model using data from the Colombian context at a nationwide industrial level. Our results indicate that introducing SCMs can potentially reduce CO2 emissions without increasing the cost of the supply chain.

Che P., Zhang C., Liu Y., Zhang Y.

Huang E., Shelley L., Hashemi L.

Chan T.C., Mahmood R., Zhu I.Y.

A Review of Inverse Optimization In recent years, there has been an explosion of interest in the mathematics and applications of inverse optimization. Unlike traditional optimization, which seeks to compute optimal decisions given an objective and constraints, inverse optimization takes decisions as input and determines an objective and/or constraints that render these decisions approximately or exactly optimal. In “Inverse Optimization: Theory and Applications,” Chan, Rafid, and Zhu provide a comprehensive review of both the methodological and application-oriented literature. Specifically, the authors consolidate various model properties, reformulation techniques, and computational methods of different classes of inverse optimization problems. The authors also review a wide range of application areas that include, but are not limited to, transportation, logistics, healthcare, and energy systems. The paper concludes with several major directions for future research.

Yang Z., Li Z., Wang S., Zhen L.

Kis T., Kovács A., Mészáros C.

Ma Y., Xia X., Guo J., Zhang C.

Vaziri S.M., Kuzgunkaya O., Vidyarthi N.

In this paper, we study the multicommodity network design problem by considering the effects of disruptions under an uncertain interdiction budget. The goal is to install links between nodes to satisfy the demand for different commodities with minimum installation cost and the weighted sum of flow costs before and after interdictions. Using the designer-interdictor-designer framework, we present a trilevel mixed-integer stochastic network design model. In the first level, the designer selects a subset of links to install and route flows under normal conditions. Most studies in the literature assume that the interdiction budget is known to the decision maker (network designer) with certainty; however, in practice, the designer is not aware of interdiction capabilities. Therefore, the designer’s objective is to minimize the installation cost and the weighted sum of pre-interdiction and expected post-interdiction costs. In the second level, the interdictor interdicts a subset of installed arcs with a limited interdiction budget. In the third level, the designer optimizes the flow over the surviving links in the residual network. Furthermore, we extend the model to consider the uncertainty in the demand besides uncertain interdiction budget. We present a branch-and-Benders-cut algorithm to solve the proposed model. The algorithm is enhanced through the use of several features such as multicut reformulation, warm start, variable fixing, cut selection, penalty reformulation, generation of strong Pareto-optimal cuts, and supervalid and valid inequalities. Extensive computational experiments are performed to evaluate the efficiency and robustness of the proposed algorithmic refinements. We compare the performance of our algorithm with a state-of-the-art, general-purpose stochastic mixed-integer bilevel linear optimization solver and show that our algorithm is faster by orders of magnitude. Our results demonstrate that the branch-and-Benders-cut algorithm combined with some of these acceleration techniques solves large-scale instances with up to 20 nodes, 220 arcs, and 200 commodities. Furthermore, we present a sensitivity analysis to highlight the advantages of stochastic design over deterministic design when the interdiction budget is uncertain. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research was supported by grants from the National Science and Engineering Research Council of Canada (NSERC) [Grants 2017-06732, 2021-04139]. S. M. Vaziri acknowledges the support of the Fonds de recherche du Québec for an FRQNT doctoral research scholarship [Grant B2X/304415-2021]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0286 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0286 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Sadra M., Zaferanieh M., Yazdimoghaddam J.

In this paper, we propose a bi-level green traffic assignment with network design problem. At the upper level, the objective function evaluates a total traffic Carbon monoxide (CO) gas emissions problem to provide a macroscopic viewpoint of the system manager. At the lower-level, a traffic assignment network design problem is considered to individually optimize users’ travel times, with certain links being potential candidates for network addition. Although the lower-level objective function is convex with linear constraints, the proposed bi-level problem is np-hard, and even finding a near-optimal solution is an np-hard task. To address the solution approach, we applied an online supervised machine learning (SML) algorithm which solves the proposed bi-level problem within a reasonable running time. Additionally, a mat-heuristic algorithm is proposed to compare the results with the online SML algorithm. To validate the online SML algorithm, we conducted experiments using real urban transportation examples in medium and large-sized networks.

Jayaswal S., Sinha A.

Bilevel optimization is a difficult class of optimization problems, which contains an inner optimization problem as a constraint in an outer optimization problem. Such optimization problems are commonly referred to as Stackelberg games in the area of game theory, where a hierarchical interaction between a leader and a follower is modeled. This chapter presents several examples of bilevel optimization problems arising in various contexts, e.g., the product line selection problem and the shortest-path interdiction problem. Depending on the context of the problem, the leader and the follower may have the same objective function but with conflicting objectives (max-min in the shortest-path interdiction), or may have different objective functions (as in the product line selection problem). Under this hierarchical setting, the leader tries to optimize their own decision by taking into account the rational response of the follower. Bilevel optimization problems are NP-hard even in the simplest case in which the problems of the leader and the follower are both linear programs. This chapter discusses classical solution approaches that are based on the reformulation of the bilevel problem into a single-level problem. It also discusses several alternate single-level reformulations for the application problems considered in this chapter.

Lozano L., Borrero J.S.

We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which components to probe subject to a probing budget in a first decision stage. Then, the uncertainty realizes, and the planner observes the disruption status of the probed components, after which the planner solves the combinatorial problem in the second stage. In contrast to standard two-stage stochastic optimization, the planner does not have access to the full uncertainty realization in the second stage. Consequently, the planner cannot directly optimize the second-stage objective function, which is given by the actual cost after disruptions, and the decisions have to be made based on an estimate of the cost. By assuming that the estimate is given by the conditional expected cost given the information revealed by probing, we reformulate the probing optimization problem as a bilevel problem with multiple followers and propose an exact algorithm based on a value function reformulation and three heuristic algorithms. We derive theoretical results that bound the value of information and the price of not having full information and a bound on the required probing budget that attains the same performance as full information. Our extensive computational experiments suggest that probing a fraction of the components is sufficient to yield large improvements in the optimal value, that our exact algorithm is competitive for small- to medium-scale instances, and that the proposed heuristics find high-quality solutions in large-scale instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0236] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI 2145553]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0629 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0629 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .