Parametric Region Search: A Mixed-Integer Bilevel Optimization Problem Primal Heuristic

Meng-Lin Tsai, Parth Brahmbhatt, Styliani Avraamidou · 2026

Read Parametric Region Search: A Mixed-Integer Bilevel Optimization Problem Primal Heuristic by Meng-Lin Tsai, Parth Brahmbhatt, Styliani Avraamidou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00214.txt.

Introduction

Tsai, Brahmbhatt, and Avraamidou present Parametric Region Search, a primal heuristic for mixed-integer bilevel optimization that hunts high-quality feasible solutions quickly. The method draws on multi-parametric optimization, exploring step by step regions set by the lower-level problem's critical regions. Tests show it often finds strong primal solutions against known derivative-free metaheuristics such as DOMINO-COBYLA and DOMINO-ISRES. It also pairs with other methods such as DOMINO-COBYLA to improve overall discovery.

Catalog record

CREATORMeng-Lin Tsai, Parth Brahmbhatt, Styliani Avraamidou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51943
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00214

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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-

Read the complete text