BOBILib: Bilevel Optimization (Benchmark) Instance Library

BOBILib contains bilevel optimization instances that are all part of the class of MILP-MILP bilevel problems. This means that both the upper- and the lower-level problem is a mixed integer linear problem (MILP). In particular, this includes the possibility that both the upper- and the lower-level problem can be

• a continuous linear problem,
• a pure integer linear problem,
• a mixed integer linear problem.

More formally, the class of problems considered is defined by \begin{align} \min_{x,y} \quad & c_u^\top x + d_u^\top y \\ \text{s.t.} \quad & Ax + By \geq a, \\ & x_i \in \mathbb{Z} \cap [x_i^-, x_i^+] \quad \text{for all } i \in I_u \subseteq \{1, \ldots, n_x\},\\ & y \in S(x), \end{align} where \(S(x)\) is the set of solutions of the \(x\)-parameterized lower-level problem \begin{align} \min_y \quad & e^\top y \\ \text{s.t.} \quad & Cx + Dy \geq b,\\ & y_i \in \mathbb{Z} \cap [y_i^-, y_i^+] \quad \text{for all } i \in I_l \subseteq \{1, \ldots, n_y\}. \end{align}

The instances in the instance tables (benchmark, collection) can be sorted with respect to the following statistics of the instances.

Symbol	Explanation
\(n_x\)	Number of upper-level variables
\(|I_u|\)	Number of upper-level integer variables
\(|B_u|\)	Number of upper-level binary variables
\(n_y\)	Number of lower-level variables
\(|I_l|\)	Number of lower-level integer variables
\(|B_l|\)	Number of lower-level binary variables
\(n_\mathrm{Link}\)	Number of linking variables
\(n_\mathrm{Link}^C\)	Number of continuous linking variables
\(n_\mathrm{Link}^I\)	Number of integer linking variables
\(n_\mathrm{Link}^B\)	Number of binary linking variables
\(m_u\)	Number of upper-level constraints
\(m_l\)	Number of lower-level constraints
\(m_\mathrm{Coup}\)	Number of coupling constraints

All instances in the BOBILib use the (name-based) MibS input file format and are thus given as pairs of mps and aux files. For more information about the MPS file format, read the respective MPS (format) wikipedia page. A detailed explanation with an example is given in section 4 of the BOBILib report. There, you also find the definition and an example for the solution format.