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 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}^I\)	Number of integer linking variables
\(n_\mathrm{Link}^B\)	Number of binary linking variables
\(n_\mathrm{Link}^C\)	Number of continuous linking variables
\(m_u\)	Number of upper-level constraints
\(m_l\)	Number of lower-level constraints
\(m_\mathrm{Coup}\)	Number of coupling constraints
\(m_\mathrm{Link}\)	Number of linking constraints
\(\alpha\)	Objective function alignment w.r.t. \(y\), i.e. \( d_u^\top e / (\|d_u\|_2 \|e\|_2) \)

The status of the instances in BOBILib and the best known solutions reported have been obtained from a limited number of sources and should not be interpreted as definitive. It is possible that instances we report here as "open" have been reported as solved in papers we have yet to mine for results or that better solutions are known for some instances. Please let us know if you are aware of any such cases. Over time, as we engage with the community and mine the literature for additional information, BOBILib may become a more definitive source, but for now, please refrain from using BOBILib as a definitive source with regard to the status of a given instance.

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.

All instances are licensed under the Creative Commons CC BY-SA 4.0 license.