On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts

1 Introduction

• Non-convex quadratic integer followers define the ILP-QILP class, where non-convexity prevents KKT- or duality-based reformulations and leaves follower optimization NP-hard even without integer variables.The paper notes that KKT conditions are not sufficient for global optimality when the follower objective is non-convex.Source: §1 · p. 2

1.1 Previous and related work

• Existing work leaves this class comparatively under-served: prior disjunctive-cut methods for integer nonlinear bilevel problems assume a convex quadratic follower or incur computational costs for greater generality.The cited general frameworks can in principle handle non-convex integer followers, but their computational cost limits practical reach to instances with very few variables and constraints.Source: §1.1 · pp. 2–3, §1 · p. 2
• The paper develops bilevel-free sets containing no bilevel-feasible solutions in their interior and uses them to derive disjunctive cuts through a cut-generating LP, including for non-convex quadratic followers.This contrasts with Gaar et al. [2024], whose cuts use an SOCP-based procedure for convex quadratic followers.Source: §1.1 · p. 3

1.2 Contribution and Outline

• The main contribution is an exact branch-and-cut algorithm for ILP-QILP problems, with enhancements and a computational study comparing it with state-of-the-art algorithms.The paper is organized around improving-direction bilevel-free sets, cut generation, improving-direction strategies, and computational evaluation.Source: §1.2 · p. 3

2.1 Basic definitions and assumptions

• The single-level relaxation drops the follower-optimality condition; the algorithm separates integer bilevel-infeasible solutions, while separation at fractional solutions is heuristic.The paper assumes the SLR feasible region is a bounded polyhedron.Source: §2.1 · p. 4

2.2 Improving-solution bilevel-free sets and disjunctive cuts

• Gaar et al. [2024]’s improving-solution cuts use an objective-comparison quadratic disjunct that becomes non-convex when R is not positive semidefinite, preventing SOCP-based cut generation.This limitation motivates the improving-direction bilevel-free sets introduced in the section.Source: §2.2 · p. 5

2.3 Improving-direction bilevel-free sets

• For any integer direction with R∆y ≠ 0 or g^T∆y < 0, T+(∆y) is a polyhedron with bilevel-free interior, and some such direction places every bilevel-infeasible solution inside it.The extension remains polyhedral even for a non-convex quadratic follower objective.Source: §2.3 · p. 6

2.4 Improving-direction disjunctive cuts

• The relative-improvement set yields m2+2n2+1 linear disjuncts, including follower constraints and bounds; its CGLP generates cuts by LP, unlike Gaar et al. [2024]’s m2+1-disjunct SOCP.The additional disjuncts arise because the set checks whether a shifted follower solution improves on the current one.Source: §2.4 · p. 7

2.5 A branch-and-cut algorithm

• At an extreme point of a branch-and-cut node relaxation, the CGLP yields a valid violated cut for a bilevel-infeasible solution, and the algorithm finitely converges.The extreme-point condition holds when a simplex-type LP solver returns the node-relaxation optimum.Source: §2 · p. 3, §2.5 · p. 9
• For an infeasible separation LP, the normalized CGLP attains a strictly positive finite optimum whose coefficients define the disjunctive cut.Source: §2.5 · p. 9
• At each integer-feasible node extreme point, IDG checks bilevel feasibility and seeks a guaranteed improving direction for infeasible points, then CGLP separation adds a violated cut.If IDG finds no improving direction, the point is bilevel-feasible; a simple IDG solves the follower problem.Source: §2.5 · p. 9
• Under Assumption 1, the branch-and-cut algorithm solves problem (1) optimally in finitely many iterations.The cuts preserve all bilevel-feasible solutions, and boundedness ensures a finite search tree with finitely many separation rounds per node.Source: §2.5 · p. 10
• Fractional extreme points may also be separated to strengthen node relaxations, but this separation is heuristic and is not guaranteed to find a violated cut.Source: §2.5 · p. 10

3.1 Redundant disjuncts

• Redundant disjuncts can be removed when no relevant bilevel-feasible solution remains in them, reducing the CGLP size and potentially strengthening its cut.The correctness guarantee is preserved when removed disjuncts cannot contain a bilevel-feasible solution better than the current incumbent.Source: §3.1 · pp. 10, 12
• Redundancy checks range from sufficient feasibility conditions to incumbent-bound tests, with tighter local variable bounds also usable at a branch-and-cut node.Bilevel-feasibility checks are strongest but as hard as solving the original problem; closed-form LP-feasibility conditions avoid solving an LP.Source: §3.1 · p. 11

3.2 Improving-direction generation

• The section presents four improving-direction generation strategies: two redundancy-targeting MINLPs, a follower-problem MINLP, and a heuristic that reuses previous directions.The heuristic is not guaranteed to find a direction when one exists; any direction it does find certifies bilevel infeasibility.Source: §3.2 · p. 12, §3.2.3 · p. 14

3.2.1 Exploiting redundancy by solving MINLPs

• Two MINLP formulations seek an improving direction while maximizing redundant disjuncts, using continuous slacks in one and binary indicators in the other.A feasible solution yields a better feasible follower response; infeasibility implies the tested solution is bilevel-feasible, relying on integer R and g.Source: §3.2.1 · pp. 12–13

3.2.2 Using an improving follower solution obtained by solving an MINLP

• A follower-problem MINLP can instead find a better feasible follower response, whose difference from the current response gives an improving direction.If the optimal follower objective equals q(y*), the current solution is bilevel-feasible.Source: §3.2.2 · p. 14

3.2.3 Using a heuristic approach by utilizing previous improving directions

• The heuristic searches a pool of previously found directions for one that is feasible and improving, then can pass it to the CGLP for separation.If the pool contains no suitable direction, an exact approach can be used and its new direction added to the pool.Source: §3.2.3 · p. 14

4.1 Improving-direction generation strategy

• The implementation offers slack-MINLP, binary-MINLP, follower-problem, and pool-based improving-direction strategies, each solvable optimally or greedily.At the root, separation continues until no significantly violated cuts are found; elsewhere, fractional solutions receive one separation round.Source: §4.1 · pp. 14–15

4.2 Identifying redundant disjuncts

• Redundancy checks combine simple inspections with optional ILP-based tests, while the large check is costly because it tests each disjunct individually.The medium strategy uses ILPs for the objective and lower-level disjuncts but skips bound disjuncts, whose more costly checks rarely found additional redundancy in preliminary computations.Source: §4.2 · p. 15

4.3 Constructing and solving the CGLP

• The CGLP uses the current node relaxation and excludes disjuncts identified as redundant; prior cuts are included at the root and may be added elsewhere if initial separation fails.Including prior cuts is theoretically required for successful separation of bilevel-infeasible integer solutions, but can enlarge CGLPs; for purely binary problems it is not mandatory.Source: §4.3 · pp. 15–16

4.4 Maintaining the improving-direction pool for heuristic DC generation

• The improving-direction pool has a capacity limit and replaces directions with low utilization; selection cycles after the most recently used direction.Fractional solutions receive pool-based heuristic separation without exact separation, except at the root after the pool is exhausted; multiple-cut settings can add several DCs at once.Source: §4.4 · pp. 16–17

5 Computational study

• The study uses a 600-second run limit and a single-core setup, and evaluates tuning, state-of-the-art comparisons on convex instances, and performance on non-convex instances.The implementation uses CPLEX 22.1, with the CGLP feasibility tolerance reduced to 10^-8.Source: §5 · p. 17

5.1 Test instances

• The testbed contains 640 instances across seven classes, including 380 established convex benchmarks, 80 denser-linking QBCovMulti instances, and 180 new non-convex BNQKP instances.BNQKP instances vary in matrix density, item-weight/profit correlation, and quadratic-coefficient magnitude.Source: §5.1 · pp. 17–18

5.2 Results for instances with convex follower objective function

• Increasing redundancy-check effort reduces generated cuts and B&C nodes while leaving S and B solve counts largely unchanged; SO/BO with RL are selected as reliable settings.The Table 3 results cover 414 instances identified as feasible.Source: §5.2 · pp. 18–19, Table 3 · p. 19
• Adding heuristic direction reuse and multiple-cut separation cuts B&C nodes by over 70% for SO and BO; the resulting S+ and B+ settings use both enhancements.The multiple-cut variant strengthens the node LP relaxation; heuristic separation lowers time spent solving the improving-direction problem.Source: Table 4 · p. 19, §5.2 · p. 19
• Across five convex instance sets, S+ and B+ outperform SOCP in solve count, runtime, and tree size; Figure 1 shows about 75% solved within 50 seconds and nearly 85% by the time limit, versus about 70% for SOCP.Table 5 reports 40/40 solved on each QBCov set, with average runtime at most 12 seconds; on QBMKPInt, S+ and B+ solve 64 and 65 instances, versus 40 for SOCP.Source: Figure 1 · p. 20, §5.2 · p. 20, Table 5 · p. 21

5.3 Results for instances with non-convex follower objective function

• On 180 non-convex BNQKP instances, FO solves 109 in 279.3 seconds on average with a 13.0% gap, versus MIX++ at 100, 351.5 seconds, and 18.8%.MIX++ performs better at 10% matrix density, but FO maintains runtimes of about 276–288 seconds and gaps near 8.5% at 50% and 100% density.Source: Table 6 · p. 21, §5.3 · p. 21

• The branch-and-cut algorithm uses disjunctive cuts based on improving-direction bilevel-free sets, obtained through a cut-generating LP rather than a cut-generating SOCP.The approach also identifies conditions for redundant disjuncts and compares strategies for generating improving directions and separating cuts, including a pool-based heuristic.Source: §6 · p. 22
• On QBCov-1 and QBCov-2, our best setting solved all 80 instances with average runtime at most 12 seconds, while Gaar et al. [2024] missed several within 600 seconds.Source: §6 · p. 22
• On QBMKPInt, our best setting solved 65 of 99 instances, compared with 40 for Gaar et al. [2024].Source: §6 · p. 22
• On the new non-convex BNQKP set, our best setting solved 109 of 180 instances, compared with 100 for Fischetti et al. [2017].Source: §6 · p. 22
• Future work includes analyzing cut dominance across improving directions, speeding up separation, and testing whether the bilevel-free sets extend beyond quadratic follower objectives.Source: §6 · p. 22