Parametric Region Search: A Mixed-Integer Bilevel Optimization Problem Primal Heuristic Meng-Lin Tsai, Parth Brahmbhatt, Styliani Avraamidou Abstract Bilevel optimization is a mathematical modeling formulation for hierarchical systems and two-player interactions, with wide-ranging applications in environmental, energy, and control engineering. Despite its utility, the mixed-integer bilevel optimization (MIBO) problem is exceptionally challenging to solve. While numerous exact and metaheuristic methods exist, the development of specialized primal heuristics for MIBO, aimed at quickly identifying high-quality feasible solutions, remains an underexplored area. This paper introduces the Parametric Region Search (PRS), a new primal heuristic for MIBO. The PRS method leverages insights from multi-parametric optimization by iteratively exploring regions defined by the lower-level problem’s critical regions. We formally define the MIBO structure and the necessary parametric region formulations, and then detail the proposed heuristic’s initialization and iterative search mechanism. Computational results demonstrate that the PRS heuristic consistently locates high-quality primal solutions compared to established derivative-free metaheuristics, including DOMINO-COBYLA and DOMINO-ISRES. Furthermore, we illustrate how the PRS can be effectively integrated with other heuristics like DOMINO-COBYLA to enhance the overall solution discovery process for MIBO. 1 Introduction As a mathematical framework for hierarchical interactions, bilevel optimization has become essential in fields ranging from industrial scheduling [ 2 ] and hierarchical control [ 1 ] to electricity market pricing [ 11 ] . However, the nested nature of these problems makes them NP-hard [ 14 ] and exceptionally difficult to solve. Solving bilevel problems is inherently complex, but the challenge intensifies significantly when the lower-level problem also contains discrete variables [ 10 , 17 ] . To address these challenges, researchers have developed various approaches, ranging from decomposition techniques like Benders [ 23 ] , and column generation [ 29 ] to multiparametric (mp) optimization [ 3 , 5 , 18 ] , branch-and-bound [ 19 ] , and branch-and-cut [ 12 , 26 ] . Despite their theoretical rigor, these exact methods often fail to scale effectively when applied to large-scale problems. This computational bottleneck motivates a shift toward strategies that prioritize the rapid identification of high-quality feasible solutions rather than insisting on exact and global optimality. In this context, primal heuristics provide a practical alternative. Primal heuristics are algorithms designed to quickly identify good feasible solutions for optimization problems, thereby establishing an upper bound on the optimal objective value. Although commonly utilized in standard Mixed-Integer Programming (MIP) [ 6 ] , to our knowledge, the development and application of primal heuristics for the more complex domain of Mixed-Integer Bilevel Optimization (MIBO) are research areas that have received limited attention. Several heuristics have been developed to enhance the efficiency of solving bilevel optimization problems. For instance, the Improving Objective Cut heuristic [ 9 , 26 ] identifies promising candidates by solving a restricted first-level problem, utilizing an objective cut from a known feasible follower response to narrow the search space. In contrast, the Second-level Priority heuristic [ 9 , 26 ] , reverses this focus; rather than optimizing the first-level objective directly, it prioritizes the second-level objective to improve the chances of achieving bilevel feasibility. Beyond these approaches, local search techniques employing weak approximations of lower-level optimality have been proposed to facilitate the discovery of high-quality neighborhood solutions [ 8 ] . Additionally, the DOMINO framework [ 7 ] treats the lower-level optimization as a “black box," allowing upper-level variables to be optimized using standard, off-the-shelf metaheuristic methods. The weighted sum heuristic [ 26 , 9 ] combines the upper- and lower-level objectives using a variable weight to relax the bilevel optimization problem into a bi-objective optimization; it then solves for the lower-level responses to obtain a bilevel-feasible primal solution. Similarly, Goal Programming for Bi-level Optimization (GPBLO) [ 25 ] introduces a normalization step prior to weighting. GPBLO produces primal solutions that outperform Particle Swarm Optimization (PSO) in terms of both solution quality and computational efficiency in the computational study. This paper introduces Parametric Region Search (PRS), a new heuristic designed to solve Mixed-Integer Bilevel Optimization (MIBO) problems with binary variables at the upper and lower level. The PRS approach is inspired by the multiparametric reformulation [ 4 , 3 , 5 , 18 ] The upper-level parameter space is partitioned into critical regions (CRs), each defined by a set of linear inequalities that form a convex polyhedral set. Within each region, the set of active constraints remains constant. This allows the lower-level optimal value to be expressed as a piecewise linear function of the upper-level variables by the sensitivity theorem. By substituting the lower-level optimal value with the upper-level variable in each critical region, the original bi-level problem is transformed into a series of single-level optimization problems. A primary challenge with this method is that the number of critical regions grows exponentially as the problem size increases [ 24 ] . This rapid expansion creates a bottleneck, resulting in poor scalability when attempting to solve larger problems. Instead of exhaustively enumerating all critical regions in the entire parameter space as required by multiparametric reformulation methods, our proposed PRS approach selectively targets individual regions likely to contain high-quality bilevel feasible solutions. This strategy addresses a key inefficiency in standard multiparametric programming, where many identified critical regions fail to provide competitive solutions yet still require significant computational effort to resolve. By focusing the search on restricted high-potential single-level solution spaces while leveraging the underlying structure provided by multiparametric programming, the PRS avoids the overhead of a full reformulation. This approach scales more effectively than exhaustive methods, which often become computationally prohibitive. This targeted strategy reduces the required processing time, though it trades the guarantee of global optimality for increased practical efficiency. The remainder of the paper is structured as follows. Section 2 formally defines the mixed-integer bilevel problem structure and the formulation of the multiparametric critical regions derived from the lower-level problem. Section 3 then describes the PRS heuristic, outlining its initialization and iterative region-based search mechanism. In Section 4, computational results are presented, comparing the PRS method against established local and global derivative-free metaheuristics. This comparison demonstrates that the PRS approach, utilizing fundamentally different logic rooted in structural analysis, consistently locates high-quality solutions. Section 5 explores two use cases, illustrating how the PRS can be coupled with other heuristics to enhance the discovery of better primal solutions for challenging mixed-integer optimization problems. Finally, Section 6 concludes the article with a discussion of the method’s contribution and outlines promising avenues for future research in bilevel optimization. 2 Bilevel Optimization and Multi-parametric (mp) Optimization This section establishes the theoretical context needed for the proposed PRS heuristic by introducing bilevel optimization and the multiparametric reformulation [ 3 , 18 ] that motivates this work. 2.1 MILP-MILP bilevel optimization formulation The general Mixed-Integer Linear Program MILP-MILP bilevel problem can be formulated as follows: \displaystyle\min_{x_{C},x_{I},y_{C},y_{I}}\quad F(x,y)=c_{1}^{\top}x+d_{1}^{\top}y (1) \displaystyle\text{s.t.}\quad A_{1}x+B_{1}y\leq b_{1} \displaystyle y\in\arg\min_{z_{C},z_{I}}\quad f(x,z)=c_{2}^{\top}x+d_{2}^{\top}z \displaystyle\text{s.t.}\quad A_{2}x+B_{2}z\leq b_{2} \displaystyle\text{where}\quad x_{C}\in\mathbb{R}^{n_{xC}},\ x_{I}\in\mathbb{Z}^{n_{xI}} \displaystyle y_{C},z_{C}\in\mathbb{R}^{n_{yC}},\ y_{I},z_{I}\in\mathbb{Z}^{n_{yI}} In this formulation, the upper-level variables are denoted by x=(x_{C},x_{I}) , where x_{C}\in\mathbb{R}^{n_{xC}} represents continuous decisions and x_{I}\in\mathbb{Z}^{n_{xI}} represents discrete decisions. z is the dummy variable for the lower-level problem to avoid a circular definition of the lower-level variable y . Both are similarly partitioned into continuous ( y_{C},z_{C} ) and integer ( y_{I},z_{I} ) components. The upper- and lower-level constraints, A_{1}x+B_{1}y\leq b_{1} and A_{2}x+B_{2}z\leq b_{2} , define the feasible region. While F(x,y)=c_{1}^{\top}x+d_{1}^{\top}y and f(x,z)=c_{2}^{\top}x+d_{2}^{\top}z define the upper- and lower-objective. Note that equality constraints are omitted for brevity, as they can be expressed as pairs of inequalities. The proposed framework requires all lower-level integer variables, z_{I} , to be binary. If the lower-level variables are general integers, they can be converted into binary form using standard expansion techniques, such as adding binary slack variables. Consequently, the terms “integer” and “binary” are used interchangeably throughout the remainder of this text. 2.2 Lower-level subproblem (Inner Problem) For a fixed upper-level decision \hat{x}=(\hat{x_{C}},\hat{x_{I}}) , the lower-level problem reduces to a standard MILP, with the c_{2}^{\top}\hat{x} term in the objective function being a constant that can be neglected. To analyze this subproblem, we decompose the lower-level cost vector d_{2} and the constraint matrix B_{2} based on the variable types. Specifically, we let d_{2}=[d_{2C}^{\top},d_{2I}^{\top}]^{\top} and B_{2}=[B_{2C},B_{2I}] , where the subscripts C and I correspond to the continuous and integer (binary) dimensions, respectively. The inner problem is then expressed as: \displaystyle\min_{y_{C},y_{I}}\quad d_{2C}^{\top}y_{C}+d_{2I}^{\top}y_{I} (2) \displaystyle\text{s.t.}\quad B_{2C}y_{C}+B_{2I}y_{I}\leq b_{2}-A_{2}\hat{x} \displaystyle y_{C}\in\mathbb{R}^{n_{yC}},\ y_{I}\in\mathbb{Z}^{n_{yI}} In Equation ( 2 ), the term b_{2}-A_{2}\hat{x} represents the effective right-hand side, showing how the leader’s decision \hat{x} restricts the follower’s feasible space. A bilevel problem is only feasible if this lower-level subproblem yields an optimal solution. However, if the lower level is degenerate, meaning multiple solutions y minimize the follower’s objective but result in different values for F(x,y) , the tie-breaking rule becomes critical. To handle this non-uniqueness, two standard approaches are used: the optimistic approach, which selects the variables that minimize the upper-level objective, and the pessimistic approach, which selects those that maximize it (the worst-case scenario) [ 28 ] . 2.3 Multiparametric (mp) Optimization Overview Before detailing the specific application to bilevel problems, we first introduce the general framework of multiparametric programming. The optimization formulation of a general mp linear programming (mp-LP) problem can be expressed as: \displaystyle Z(\theta)= \displaystyle\min_{t}\ c^{\top}t+\theta^{\top}H^{\top}t (3a) s.t. \displaystyle~At\leq b+F\theta (3b) \displaystyle\theta\in\Theta:=\{\theta\in\mathbb{R}^{q}\mid A_{\theta}\theta\leq b_{\theta}\} (3c) \displaystyle t\in\mathbb{R}^{n_{c}}\times\mathbb{Z}^{n_{i}} (3d) Here, the objective function is linear in the decision variables t and is influenced by the parameters \theta through the term \theta^{\top}H^{\top}t . The inequality constraints At\leq b+F\theta show that the right-hand side limits are affine functions of the parameters \theta . The constraint \theta\in\Theta defines the space of feasible parameters as a polytope bounded by the linear inequalities A_{\theta}\theta\leq b_{\theta} . In this general formulation, the decision vector t can contain both continuous and integer variables, allowing the problem to be structured as a MILP. This formulation seeks an optimal solution t for every possible value of \theta within its defined bounds \Theta . For instances where the problem is continuous (or once the integer variables in x are fixed), the explicit parametric solution to Eq. ( 3 ) maps the parameter space into distinct geometric partitions known as critical regions. The solution can be expressed as a piecewise affine function of the parameters: \displaystyle{t}^{*}(\theta)=A^{v}\theta+b^{v}\quad\text{if}\quad\theta\in CR^{v}:=\{\theta\mid E^{v}\theta\leq f^{v}\} (4) \displaystyle\forall\ v=1,2,3,\dots,n_{CR} where t^{*}(\theta) is the optimal solution profile, A^{v} and b^{v} define the affine function for a specific critical region v , E^{v} and f^{v} represent the inequality matrices defining the critical region polytope CR^{v} , and n_{CR} denotes the total number of critical regions. 2.4 Critical Region Formulation In the context of the bilevel optimization framework addressed in this work, the lower-level subproblem operates exactly as a multiparametric programming problem. Specifically, the upper-level decisions x act as the varying parameters \theta , while the lower-level variables y act as the decision variables. Once the lower-level integer variables y_{I} are fixed to values \hat{y}_{I} , and a feasible upper-level point x_{0} is selected, the lower-level problem reduces to a standard linear programming (LP) problem. We can reformulate the bilevel problem into a number of single-level problems in the associated CRs using the multiparametric linear programming. 2.4.1 Identification of the Active Set Consider the fixed upper-level nominal point x_{0} , which transforms the multiparametric problem into a standard LP. Solving this LP yields the nominal lower-level solution y_{C,0} and the corresponding Lagrange multipliers \lambda_{0} . Based on these values, the Active Set \mathcal{A} is identified as the set of indices for constraints that satisfy strict equality: \displaystyle B_{2C,\mathcal{A}}y_{C,0}=\hat{b}_{\mathcal{A}}-A_{2,\mathcal{A}}x_{0} (5) \displaystyle\lambda_{0,\mathcal{A}}>0 where \hat{b}_{2,\mathcal{A}}=b_{2,\mathcal{A}}-B_{2I,\mathcal{A}}\hat{y}_{I} represents the effective right-hand side accounting for the fixed lower-level integers. We assume the Linear Independence Constraint Qualification (LICQ) holds, meaning the matrix A_{2,\mathcal{A}} has full rank and is invertible. 2.4.2 Parametric Solution According to the Basic Sensitivity Theorem for linear programming, the optimal basis (defined by \mathcal{A} ) remains invariant in a neighborhood around the nominal point x_{0} . Consequently, the optimal continuous variables y_{C}(x) can be expressed as an affine function of the parameter x : y_{C}^{*}(x)=B_{2C,\mathcal{A}}^{-1}\left(\hat{b}_{2,\mathcal{A}}-A_{2,\mathcal{A}}x\right) (6) Furthermore, for multiparametric LP (mp-LP) problems, the Lagrange multipliers \lambda(x) do not change as a function of the parameter x within the critical region; they remain equal to the nominal values \lambda_{0} . 2.4.3 Generation of the Critical Region (CR) To ensure the affine function y_{C}^{*}(x) remains the optimal solution, the solution must remain feasible. Since the dual variables \lambda(x) are constant and non-negative by definition at the nominal point, the dual feasibility condition is naturally satisfied. Therefore, the critical region is defined strictly by the Primal Feasibility requirements of the inactive constraints. Substituting the parametric solution y_{C}^{*}(x) into the original constraints yields the polyhedral representation of the critical region: CR_{\mathcal{A}}=\left\{x\in\mathbb{R}^{n_{x}}\ \middle|\begin{array}[]{l}\ \left[-B_{2C}B_{2C,\mathcal{A}}^{-1}A_{2C,\mathcal{A}}+A_{2}\right]x\leq\left[\hat{b_{2}}_{\mathcal{A}}-B_{2C}B_{2C,\mathcal{A}}^{-1}\hat{b}_{\mathcal{A}}\right]\\ \ \left[-B_{1C}B_{2C,\mathcal{A}}^{-1}A_{2C,\mathcal{A}}+A_{1}\right]x\leq\left[\hat{b_{1}}_{\mathcal{A}}-B_{1C}A_{2C,\mathcal{A}}^{-1}\hat{b}_{\mathcal{A}}\right]\end{array}\right\} (7) This formulation is modified from Eq. (2.7) in [ 20 ] , adapted to the bilevel optimization context such that the parameter \theta corresponds to upper-level variable x and the constraint matrices are mapped to the bilevel problem structure. Within this compact polytope, the lower-level reaction y_{C}^{*}(x) is uniquely determined and linear, allowing for the efficient single-level reformulation of the bilevel problem. 2.4.4 mp-Reformulated Single-Level Problem Within a Critical Region CR , the optimal continuous response y_{C}^{*}(x) is affine in x : y_{C}^{*}(x)=B_{2C,\mathcal{A}}^{-1}\left(\hat{b}_{2,\mathcal{A}}-A_{2,\mathcal{A}}x\right)=K_{C}x+h_{C} (8) Substituting y_{C}^{*}(x) and the assumed fixed integer solution \hat{y}_{I} into the upper-level problem yields the single-level mp-reformulated MILP: \displaystyle\min_{x_{C},x_{I}}\quad F(x,y^{*}(x)) (9) \displaystyle\text{s.t.}\quad A_{1}x+B_{1C}(K_{C}x+h_{C})+B_{1I}\hat{y}_{I}\leq b_{1} \displaystyle x\in CR \displaystyle x_{C}\in\mathbb{R}^{n_{xC}},\ x_{I}\in\mathbb{Z}^{n_{xI}} The final bilevel solution is determined by identifying the minimum upper-level objective value across all critical regions. However, the number of these regions can grow exponentially with the bilevel optimization problem size [ 24 ] , making the exhaustive enumeration of all CRs computationally prohibitive for large-scale applications. This challenge motivates the present work, which introduces a novel heuristic designed to strategically explore promising critical regions rather than enumerating them all, efficiently identifying high-quality solutions. 3 Method The Parametric Region Search (PRS) is a new primal heuristic developed to efficiently identify high-quality feasible solutions for MIBO problems given an initial starting point. To obtain a good starting point, Subsection 3.1 details the high-point relaxation response method. The heuristic is a three-step process described in Subsection 3.2 , which consists of lower-level optimization, critical region (CR) generation, and regional upper-level optimization. 3.1 Initialization (High-point Relaxation Response) To obtain a starting feasible point, we solve the High-Point Relaxation (HPR) and determine the follower’s response according to the procedure in Algorithm 1 . HPR is a bilevel optimization relaxation that removes the lower-level optimality constraints. By solving the resulting single-level MILP, a divided solution pair (\hat{x},\hat{y}) is identified within the relaxed feasible region \Omega . Since the relaxed response \hat{y} may not be optimal for the follower at the fixed leader decision \hat{x} , a feasibility response step is executed. The leader’s decision is fixed, and the lower-level problem is solved in isolation to determine the true optimal response y^{*} . This process yields a bilevel feasible point (\hat{x},y^{*}) , providing a starting point for local or global search heuristics. While Step 1 is sufficient for determining the initial upper-level variables \hat{x} , the subsequent Step 2 is included as an optional procedure to facilitate the gap analysis described in Section 4.2 . Algorithm 1 High-Point Relaxation (HPR) Response Initialization 1: Bilevel formulation parameters (c_{1},d_{1},A_{1},B_{1},b_{1},c_{2},d_{2},A_{2},B_{2},b_{2}) 2: Initial feasible candidate (\hat{x},y^{*}) 3: Step 1: Relax Lower-Level Optimality 4: Solve the relaxed upper-level MILP as a single-level problem: (\hat{x},\hat{y})\leftarrow\arg\min_{x,y}\{c_{1}^{\top}x+d_{1}^{\top}y\mid(x,y)\in\Omega\} \triangleright Where \Omega represents all upper and lower constraints 5: Step 2: Feasibility Response (Optional) 6: Fix x\leftarrow\hat{x} and solve the lower-level problem: y^{*}\leftarrow\arg\min_{y}\{f(\hat{x},y)\mid g(\hat{x},y)\leq 0\} 7: return Initial candidate (\hat{x},y^{*}) 3.2 Parametric Region Search (PRS) Heuristic This subsection presents the proposed methodology, which is detailed in Figure 1 . Following the methodology and providing a detailed step-by-step procedure via the pseudo-code in Algorithm 2 . We conclude with a numerical example to illustrate the process. The methodology utilizing a multi-parametric reformulation structure involves N variants of the upper-level variable x -space, where N represents the total number of possible combinations of lower-level binary variables. Within the schematic representation, these variants are visualized as stacked planes, where each plane (x,\widehat{y_{I,n}}) denotes an upper-variable space corresponding to a specific configuration of lower-level integer variable combinations. Each variant is further partitioned into multiple critical regions, represented by different colors in Figure 1 . A challenge of solving this structure is that N grows combinatorially with the number of lower-level binary variables, which can lead to an exceptionally large search space. While traditional multi-parametric bilevel solvers typically require an exhaustive search of every critical region across all planes to ensure global optimality [ 3 , 18 ] , the algorithm presented here iterates only through selected regions. Figure 1: Schematic diagram of PRS heuristic. (a) Step 1, lower level optimization with a fixed set of upper variables, highlighted in red dashed vertical arrows. (b) Step 2, Critical region generation, highlighting in dashed border lines. (c) Step 3, regional upper level optimization, highlighted by the red arrow. (d) Repeat Step 1, Step 2, and Step 3 in a new iteration. (e) Repeat Step 1 and converge. The algorithm starts with a fixed upper-level point x_{0} , which is established using the high-point relaxation response, algorithm 1 , discussed in Section 3.1 . To verify bilevel feasibility, Step 1.1 involves solving the lower-level subproblem (defined in Eq. 2 ) to identify the true follower response. In Figure 1 (a), this lower-level optimization process is represented by vertical dashed red lines that span the stacked planes. The procedure identifies a bilevel feasible point, which is distinguished by a red-bordered circle. In contrast, other points sharing the same fixed value x but possessing different \hat{y}_{I,n} values are identified as bilevel infeasible and are marked with black borders. In Step 1.2, the algorithm performs a lexicographic update to maintain the current best solution. The candidate solution (x_{k},y_{k}) is accepted as the new global optimum (x^{*},y^{*}) if it provides a strictly better upper-level objective value ( F_{curr}