PaperlayerView exact revision on arXiv

Source-linked AI summary

A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

Sahar Tahernejad, Ted K. Ralphs, Scott T. DeNegre

arXiv:2104.09010v1math.OCcs.GT

TL;DR

MIBLPs are difficult to solve because checking a candidate solution’s feasibility is NP-complete, and standard integrality relaxation does not necessarily yield a valid relaxation. This paper presents a generalized branch-and-cut framework implemented in MibS, and reports effective solver-option choices across its tested problem classes.

  • Problem

    MIBLPs are difficult because feasibility checking is NP-complete and relaxing the follower problem may invalidate solutions that were previously feasible.

    Source: §1.3 · p. 6

  • Method

    The paper presents a generalized branch-and-cut framework for MIBLPs, using bounds to prune subproblems in a recursive partitioning search and implementing the framework in MibS.

    Source: §1.5 · p. 8, §2.2 · p. 15, §5 · p. 35

  • Results

    The tested settings favored whenLFixed-LFixed and whenXYIntOrLFixed-LFixed for solving the second-level problems, while branching-strategy performance depended on the ratio of leader to follower variables.

    Source: §4.1 · p. 30, §4.2 · p. 31

  • Takeaways & Limitations

    MibS provides a flexible, open-source solver that the authors report can robustly solve generic MIBLPs of modest size.

    Source: §5 · p. 35

    The experiments omit the effectiveness of valid-inequality classes and their control parameters, leaving their evaluation to future work.

    Source: §4 · p. 29

Abstract

from arXiv · show

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.

1 Introduction

MIBLPs model sequential decisions by multiple, possibly competing decision-makers, a setting that single-decision optimization does not capture. The paper presents MibS as an open test bed and solver for this class of practical problems.

1 Introduction

  • A single-decision, single-objective optimization framework is inadequate for an increasing range of these applications.The paper motivates multilevel optimization as a framework for representing decisions made in sequence.Source: §1 · p. 1
  • MIBLPs model applications where multiple decision-makers make sequential decisions that affect the options and outcomes of later decision-makers.Earlier decisions must account for how later decision-makers respond.Source: §1 · p. 2
  • MibS was developed as an open test bed for algorithmic ideas and a platform for solving practical multilevel optimization problems.The paper notes that practical solution methods have become more realistic alongside improvements in traditional optimization and open-source solvers.Source: §1 · p. 2

1.1 Mixed Integer Bilevel Optimization

MIBLPs have two levels, with first-level decisions shaping the follower’s problem; this section defines their feasible solutions and optimistic risk function. It also introduces linking variables, whose fixation can reduce a value-function formulation to an MILP.

1.1 Mixed Integer Bilevel Optimization

  • A MIBLP has two decision levels, with first-level variables controlled by the leader and second-level variables by the follower.The general form permits second-level variables in first-level constraints, although the paper notes that many ideas simplify when G1 = 0.Source: §1.1 · pp. 2–3
  • The optimistic risk function selects a follower-optimal response that is feasible for the first-level constraints and evaluates the resulting first-level objective.The formulation also permits other risk-function variants, including a pessimistic one.Source: §1.1 · p. 3
  • Fixing first-level variables that affect second-level constraints makes the value-function formulation’s remaining minimization an MILP.The variables with nonzero coefficients in the second-level constraints are called linking variables; the paper assumes these are integer.Source: §1.1 · p. 4
  • The paper assumes the constraint-defined set P is bounded for exposition, and notes that this assumption is easy to relax in practice.It also assumes away a second-level unbounded direction that can be detected in preprocessing.Source: §1.1 · p. 5
  • The paper’s formulation targets optimal first-level decisions, even though a bilevel-feasible follower response need not minimize the first-level objective for that decision.The second-level variables are reintroduced in the branch-and-cut relaxation and used when evaluating the risk function.Source: §1.1 · pp. 3–5
  • Bilevel feasibility requires first-level feasibility and a second-level response that is both first-level feasible and rational.The paper distinguishes the feasible set in first-level variables from the full feasible region and warns that the continuous relaxation need not contain the integer-feasible region.Source: §1.1 · p. 5

1.2 Special Cases

MibS includes specialized methods for special cases, including zero-sum problems and mixed integer interdiction problems. The latter have binary leader variables corresponding one-to-one with follower variables.

1.2 Special Cases

  • Mixed integer interdiction problems are a zero-sum subclass with binary first-level variables corresponding one-to-one with second-level variables.Fixing a first-level variable to one prevents its associated second-level variable from taking a nonzero value; the paper notes that this structure can support specialized methods.Source: §1.2 · p. 6

1.3 Computational Challenges

MIBLPs are difficult because checking feasibility is NP-complete, and relaxing integrality does not necessarily produce a valid relaxation. The paper illustrates these challenges with a bilevel linear optimization example.

1.3 Computational Challenges

  • Relaxing integrality can fail to produce a relaxation because relaxing the follower problem may make previously feasible solutions infeasible.The feasible region of the resulting bilevel linear problem need not contain the MIBLP feasible region, so a solution in the relaxed domain need not be MIBLP-optimal.Source: §1.3 · p. 6, Figure 1 · p. 7
  • Checking whether a given MIBLP solution is feasible is NP-complete, making these problems inherently harder to solve than MILPs.Even evaluating the risk function for a given first-level decision is NP-hard.Source: §1.3 · p. 6

1.4 Previous Work

Earlier MIBLP algorithms often exploited special structure, while later work extended branch-and-cut and proposed other approaches for broader problem classes. The section traces these developments and their convergence or scope conditions.

1.4 Previous Work

  • Moore and Bard’s branch-and-bound method converges when all first-level variables are integer or all second-level variables are continuous.Source: §1.4 · p. 7
  • Earlier computational work often targeted binary-variable cases, using exact algorithms, tabu search, or a multiparametric reformulation of the follower problem.The cited studies respectively considered all-binary variables, binary first-level with continuous second-level variables, or all discrete variables binary.Source: §1.4 · p. 7
  • Later approaches included branch-and-cut for integer bilevel problems, decomposition, specialized cuts, branching, reformulations, and algorithms for particular applications.DeNegre and Ralphs introduced integer no-good cuts; subsequent work also addressed general MIBLPs and specialized settings.Source: §1.4 · pp. 7–8

1.5 Overview of Branch and Cut

The overview presents branch-and-cut as recursive partitioning and removal of regions that cannot contain improving solutions. Bounds guide pruning and termination, while branching and cutting impose valid disjunctions or inequalities.

1.5 Overview of Branch and Cut

  • Branch-and-cut recursively partitions the feasible region and removes regions proven to contain no improving feasible solutions, using branching or cuts.Subproblems form a search tree; upper and lower bounds support pruning rather than complete enumeration.Source: §1.5 · pp. 8–9

Bounding.

  • Bounds for each subproblem support efficient search: relaxations typically provide lower bounds, while feasible solutions provide upper bounds.Global bounds aggregate leaf-node bounds and are updated as the algorithm progresses; equality of the global bounds terminates the algorithm.Source: Bounding · pp. 9–10

Pruning.

  • A node is pruned when its lower bound is at least the incumbent, and changing global bounds can make additional nodes eligible for pruning.Source: Pruning · p. 10

Branching.

  • Branching partitions a node’s feasible region with a valid disjunction; integer-variable disjunctions split an integer expression around an integer threshold.A variable disjunction can exclude a fractional relaxation solution, though MIBLPs may require more than these standard disjunctions.Source: Branching · p. 10

Cutting.

  • Cutting strengthens the relaxation by adding valid inequalities, typically removing the current relaxation solution and a surrounding region without improving solutions.Choosing among many possible cuts matters because adding too many can reduce relaxation effectiveness; cutting aims to improve the lower bound.Source: Cutting · p. 11

1.6 Outline

The paper proceeds from branch-and-cut components to the overall MibS algorithm and implementation, then computational results and concluding thoughts.

1.6 Outline

  • The paper covers branch-and-cut components, the MibS algorithm and implementation, computational results, and concluding thoughts in Sections 2–5.Source: §1.6 · p. 11

2 A Branch-and-cut Algorithm

The section presents MibS’s branch-and-cut framework for mixed integer bilevel problems, including specialized procedures for bounding, pruning, branching, and cutting. It describes relaxations, value-function checks, valid inequalities, and primal heuristics to address infeasible, repeated, or suboptimal solutions and seek improved bilevel-feasible solutions.

2 A Branch-and-cut Algorithm

  • MibS tracks previously seen linking-variable values to avoid repeating value-function evaluations that can arise at multiple search nodes.The pool also supports eliminating first-level solutions that share a linking-variable assignment already shown infeasible.Source: §2 · p. 12

2.1 Bounding

  • The algorithm uses the tractable, warm-startable (LR) relaxation for bounds, then checks first-level integrality and second-level optimality to establish bilevel feasibility.The more expensive (SL-MILP) check can be deferred; solving it can establish feasibility or eliminate linking assignments, while solving the MILP for Ξ(xt) yields a valid upper bound.Source: §2.1 · pp. 12–15

2.2 Pruning

  • Nodes are pruned when their lower bound reaches the global upper bound; when linking variables are fixed, solving (UB) or (UBt) also permits pruning.Solving (UB) can provide information about bilevel feasible solutions sharing the same linking-variable values, including solutions outside the current node.Source: §2.2 · pp. 15–16

2.3 Branching

  • Branching may be needed even when a relaxation solution appears feasible, so MibS can branch on linking variables or, when needed, use fractional variables more broadly.Candidate selection offers pseudocost, strong branching, and reliability branching; branching on non-linking variables may not always perform well empirically.Source: §2.3 · pp. 16–18

2.4 Cutting

  • Cutting iteratively adds valid inequalities that separate the current relaxation solution from the convex hull of improving bilevel-feasible solutions.The paper introduces improving valid inequalities relative to the current global upper bound and allows cuts generated at ancestor nodes to be applied in a node’s relaxation.Source: §2.4 · pp. 18–19
  • MibS classifies cuts as feasibility, optimality, or projected optimality cuts, though these categories can overlap.Projected optimality cuts can remove solutions sharing particular first-level values; MibS includes separation routines for multiple classes of valid inequalities.Source: §2.4 · p. 19
  • Integer no-good cuts remove a single integral but bilevel-infeasible solution under integer-data assumptions, while generalized no-good cuts exclude fixed binary linking-variable values.Intersection cuts can remove infeasible solutions under specified integrality conditions; hypercube intersection cuts are violated by the current solution but need not remove every solution with the same linking values.Source: §2.4 · pp. 19–20
  • Increasing objective cuts use a value-function-bound disjunction for binary linking variables and A2 ≥ 0, while Benders cuts apply to a more restricted binary-linking structure.The Benders-cut conditions include nonpositive second-level coefficients in constraints without linking variables and a specified linking-variable/second-level-variable relationship; new cuts can be added when feasible solutions are found.Source: §2.4 · p. 20

2.5 Primal Heuristics

  • The improving objective cut heuristic combines a good first-level solution with a likely bilevel-feasible alternative, then checks feasibility to seek an improved solution.The alternative is not necessarily good for the first-level objective, and a separate feasibility check is required.Source: §2.5 · p. 21
  • The second-level priority heuristic uses an MILP objective that encourages bilevel feasibility while an upper-bound constraint targets solution quality, but the produced solution is not guaranteed bilevel feasible.Replacing the current upper bound with a chosen target can seek incumbent improvement but removes the stated feasibility assurance for the heuristic problem.Source: §2.5 · p. 21
  • The weighted sums heuristic uses multi-objective optimization to find efficient solutions through a weighted-sum subproblem as candidates for bilevel-feasible solutions.Efficient solutions cannot improve one objective without degrading the other while maintaining feasibility.Source: §2.5 · p. 21

3 Software Framework

This section describes MibS’s branch-and-cut framework and its parameters for coordinating search, branching, cuts, and second-level solves. It also covers node processing, pessimistic-risk feasibility checking, fractional branching, and supported solvers for the computationally demanding second-level MILPs.

3.1 Design of MibS

  • MibS is open-source C++ branch-and-cut software built on BLIS, and it analyzes instance structure to disable user-selected cuts that are invalid for the problem.Its classes cover model extraction, bilevel-feasibility checking, node processing, cut generation, branching, and primal heuristics.Source: §3.1 · pp. 22–23

3.2 Parameters

  • Parameters allow linking-only or fractional-variable branching, default to pseudocost scoring and best-first search, and automatically select applicable cuts and their generation frequency.Cut applicability is analyzed from instance structure, while generation frequency is selected by default from early-stage statistics.Source: §3.2 · pp. 23–24

Primal Heuristics.

  • The linking-solution pool caches linking assignments and status tags, with associated solutions when available, to avoid repeating SL-MILP and UB solves.The pool is stored in a hash table for efficient membership checks.Source: Primal Heuristics · p. 24
  • An unseen linking assignment at an integer-feasible point with no branching candidates requires an SL-MILP solve; under linking branching, fixed linking variables also require UB if SL-MILP is feasible.An infeasible SL-MILP permits removing solutions with that linking assignment; solving UB establishes that none can improve and lets the solver reuse its solution information globally through the pool.Source: Primal Heuristics · p. 25

3.3 Outline of the Algorithm

  • Node processing solves the relaxation, uses linking-pool information and conditional SL-MILP or UB checks, then branches or adds valid inequalities to eliminate the candidate point.When no branching candidates are available, the algorithm must add valid inequalities; otherwise it may branch or, in specified cases, choose between branching and cuts.Source: §3.3 · p. 26
  • For RF-PES, feasibility requires checking whether d1yt equals the optimal MILP value; fractional branching avoids solving a new bilevel problem for fixed xL = γ.Unlike the optimistic case, d2yt = φ(A2xt) alone does not guarantee feasibility.Source: §3.3 · p. 28

3.4 Solving the Second-level Problem

  • Solving (SL-MILP) and (UB) accounts for much, and often most, of the algorithm’s computational effort.Reducing time spent on these problems is a major focus of ongoing work.Source: §3.4 · p. 28
  • MibS supports SYMPHONY, CPLEX, and Cbc for solving (SL-MILP) and (UB), with feasCheckSolver selecting the MILP solver.A warm-start method for sequences of MILPs differing only in the right-hand side can reuse a single branch-and-bound tree and, under mild conditions, construct a complete description of φ; it is implemented in SYMPHONY (Hassanzadeh and Ralphs, 2014; Ralphs et al., 2019; Ralphs and G¨uzelsoy, 2006, 2005).Source: §3.4 · p. 28

4 Computational Results

The computational study compares MibS settings for subproblem-solving schedules, branching, the linking solution pool, primal heuristics, and MILP solvers. Results identify default settings and show that performance depends on branching strategy and instance characteristics.

4 Computational Results

  • The experiments use three data sets totaling 171 instances, while plots and tables include 125 instances meeting the stated time and solve-time filters; valid-inequality testing is deferred.The plots use instances solved by at least one method within 3600 seconds and taking over 5 seconds for at least one method.Source: §4 · pp. 28–30

4.1 Impact of Strategy for Solving (SL-MILP) and (UB)

  • whenLFixed-LFixed and whenXYIntOrLFixed-LFixed outperform the other tested subproblem-solving schedules, with roughly the same performance; the latter becomes MibS’s default.Figure 2a covers IBLP-DEN and IBLP-FIS, while Figure 2b covers MIBLP-XU.Source: §4.1 · p. 30, Figure 2 · p. 31

4.2 Impact of Branching Strategy

  • Linking branching performs better when r1 ≤ r2, whereas fractional branching performs better when r1 > r2; MibS defaults to those respective strategies.The authors note that predicting the better strategy for an individual instance is difficult.Source: Figure 3 · p. 31, §4.2 · pp. 31–32

4.3 Impact of Linking Solution Pool

  • The linking solution pool reduces (SL-MILP) and (UB) solves and solution time with fractional branching, but does not reduce solved instances with linking branching; it is enabled by default.The reported performance varies across data sets, and the table compares subproblem counts and their share of total solution time.Source: Table 2 · p. 33, §4.3 · p. 33

4.4 Impact of Primal Heuristics

  • The primal heuristics tested so far do not improve solution time; the authors note that parameter tuning might improve their performance, but no serious tuning effort has been made.The frequency of heuristic use was set to 100.Source: Figure 5 · p. 34, §4.4 · p. 34

4.5 Impact of MILP Solver

  • When required MILPs are easy or take little total time, changing the solver has little impact; for more effortful MILPs, CPLEX cuts MILP-solving time by roughly half on average.The exact reduction depends highly on the instance.Source: §4.5 · p. 35

5 Conclusions

The paper presents a generalized branch-and-cut algorithm for MIBLPs and implements it in the open-source solver MibS. It reports a robust solver for generic MIBLPs of modest size and identifies further methodological development as future work.

5 Conclusions

  • The generalized branch-and-cut algorithm is designed to solve a wide range of MIBLPs.Source: §5 · p. 35
  • MibS implements the algorithm as an open-source solver with a comprehensive, flexible framework of algorithmic options.Source: §5 · p. 35
  • Computational results demonstrate MibS as a robust solver for generic MIBLPs of modest size.Source: §5 · p. 35
  • Future work will describe cut generation in greater detail and consider additional valid-inequality techniques and alternative algorithms.Source: §5 · p. 35

Appendices

The appendices provide detailed results for tables used to plot Figures 2–5.

Appendices

Related papers

Loading 2104.09010v1…