Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A general bilevel optimization problem is defined as

$$\begin{aligned} \min _{x\in {\mathbb {R}}^{n_1},y\in {\mathbb {R}}^{n_2}}&F(x,y) \end{aligned}$$
(1)
$$\begin{aligned}&G(x,y) \le 0 \end{aligned}$$
(2)
$$\begin{aligned}&y \in \arg \min _{y'\in {\mathbb {R}}^{n_2} } \{ f(x,y') : g(x,y') \le 0 \, \} , \end{aligned}$$
(3)

where \(F,f: {\mathbb {R}}^{n_1 + n_2} \rightarrow {\mathbb {R}}\), \(G: {\mathbb {R}}^{n_1+n_2} \rightarrow {\mathbb {R}}^{m_1}\), and \(g: {\mathbb {R}}^{n_1+n_2} \rightarrow {\mathbb {R}}^{m_2}\). Let \(n=n_1+n_2\) denote the total number of decision variables.

We will refer to F(x, y) and \(G(x,y)\le 0\) as the leader objective function and constraints, respectively, and to (3) as the follower subproblem. In case the follower subproblem has multiple optimal solutions, we assume that one with minimum leader cost among those with \(G(x,y)\le 0\) is chosen—i.e. we consider the optimistic version of bilevel optimization.

By defining the follower value function for a given \(x \in {\mathbb {R}}^{n_1}\)

$$\begin{aligned} \varPhi (x) = \min _{y\in {\mathbb {R}}^{n_2} } \{ f(x,y) : g(x,y) \le 0 \, \}, \end{aligned}$$
(4)

one can restate the bilevel optimization problem as follows:

$$\begin{aligned} \min F(x,y)&\end{aligned}$$
(5)
$$\begin{aligned} G(x,y)&\le 0 \end{aligned}$$
(6)
$$\begin{aligned} g(x,y)&\le 0 \end{aligned}$$
(7)
$$\begin{aligned} (x,y)&\in {\mathbb {R}}^n \end{aligned}$$
(8)
$$\begin{aligned} f(x,y)&\le \varPhi (x). \end{aligned}$$
(9)

Note that the above optimization problem would be hard (both theoretically and in practice) even if one would assume convexity of F, G, f and g (which would imply that of \(\varPhi \)), due to the intrinsic nonconvexity of (9).

Dropping condition (9) leads the so-called High Point Relaxation (HPR). As customary in the bilevel context, we assume that HPR is feasible and bounded, and that the minimization problem in (4) is bounded for each feasible solution of HPR—while its feasibility follows directly from the definition of HPR. As HPR contains all the follower constraints, any HPR solution (x, y) satisfies \(f(x,y) \ge \varPhi (x)\), hence (9) actually implies \(f(x,y) = \varPhi (x,y)\).

A point \((x,y) \in {\mathbb {R}}^n\) will be called bilevel infeasible if it violates (9). A point \((x,y) \in {\mathbb {R}}^n\) will be called bilevel feasible if it is satisfies all constraints (6)–(9).

2 Literature Overview

In this paper we will mainly focus on Mixed-Integer Bilevel Linear Programs (MIBLP’s) where some/all variables are required to be integer, and all HPR constraints (plus objective function) are linear.

The first generic branch-and-bound approach to the MIBLP’s has been given in [7], where the authors propose to solve HPR embedded into a branch-and-bound scheme and basically enumerate bilevel feasible solutions. Recently, [4, 5] proposed a sound branch-and-cut approach that builds upon the ideas from [7] and cuts off integer bilevel infeasible solutions, by adding cuts that exploit the integrality property of the leader and the follower variables. The authors provide an open-source MIBLP solver MibS [8]. More recently, [3] again propose to embed HPR into a branch-and-bound tree, bilevel infeasible solutions being cut off by adding a continuous follower subproblem into HPR, each time a new bilevel infeasible solution is detected. Continuous follower subproblems are then reformulated using KKT conditions and linearized in a standard way. Another generic approach for MIBLP’s is a branch-and-sandwich method in [6], where the authors propose novel ideas for deriving lower and upper bounds of the follower’s value function.

As this is usually the case with intersection cuts for MILPs, our IC’s for MIBLP’s also use disjunctive arguments. Disjunctive cuts in connection to bilevel linear programming have been investigated in [1], where the continuous follower subproblem is reformulated using KKT conditions, and disjunctive cuts are used to enforce complementary slackness conditions.

3 Bilevel-Free Sets

The following result is valid for generic bilevel problems and was implicit in some early references (including [9]) where it was only used as a guide for branching.

Lemma 1

For any \(\hat{y}\in {\mathbb {R}}^{n_2}\), the set

$$\begin{aligned} S(\hat{y}) = \{ (x,y) \in {\mathbb {R}}^n: f(x,y) \ge f(x,\hat{y}), \, g(x,\hat{y}) \le 0 \} \end{aligned}$$
(10)

does not contain any bilevel feasible point in its interior.

Proof

It is enough to prove that no bilevel feasible (x, y) exists such that f(x, y) > \(f(x,\hat{y})\) and \(g(x,\hat{y}) < 0\). We will in fact prove a tighter result where the latter condition is replaced by \(g(x,\hat{y}) \le 0\), as this will be required in the proof of the next theorem. Indeed, for any bilevel feasible solution (x, y) with \(g(x,\hat{y})\le 0\), one has \(f(x,y) \le \varPhi (x) = \min _{y'} \{ f(x,y') : g(x,y') \le 0\} \le f(x,\hat{y})\).

In some relevant settings, the above result can be strengthened to obtain the following enlarged bilevel-free set.

Theorem 1

Assume that g(x, y) is integer for all HPR solutions (x, y). Then, for any \(\hat{y}\in {\mathbb {R}}^{n_2}\), the extended set

$$\begin{aligned} S^+(\hat{y}) = \{ (x,y) \in {\mathbb {R}}^n: f(x,y) \ge f(x,\hat{y}), \, g(x,\hat{y}) \le 1 \} \end{aligned}$$
(11)

does not contain any bilevel feasible point in its interior, where 1 denotes a vector of all ones.

Proof

To be in the interior of \(S^+(\hat{y})\), a bilevel feasible (x, y) should satisfy f(x, y) > \(f(x,\hat{y})\) and \(g(x,\hat{y}) < 1\). By assumption, the latter condition can be replaced by \(g(x,\hat{y}) \le 0\), hence the claim follows from the proof of previous lemma.

As far as we know, the above result is new. In spite of its simplicity, it will play a fundamental role in our solution method.

4 Mixed-Integer Bilevel Linear Programming

In the remaining part of the paper we will focus on the case where some/all variables are required to be integer, and all HPR constraints (plus objective function) are linear. This leads to the following Mixed-Integer Bilevel Linear Program (MIBLP):

$$\begin{aligned} \min F(x,y) \end{aligned}$$
(12)
$$\begin{aligned} G(x,y)&\le 0 \end{aligned}$$
(13)
$$\begin{aligned} g(x,y)&\le 0 \end{aligned}$$
(14)
$$\begin{aligned} (x,y)&\in {\mathbb {R}}^{n} \end{aligned}$$
(15)
$$\begin{aligned} f(x,y)&\le \varPhi (x) \end{aligned}$$
(16)
$$\begin{aligned} x_j&~ \text {integer}, \ \ \forall j \in J_1 \end{aligned}$$
(17)
$$\begin{aligned} y_j&~ \text {integer}, \ \ \forall j \in J_2, \end{aligned}$$
(18)

where F, G, f, g are now assumed to be affine functions, sets \(J_1\subseteq \{1,\cdots ,n_1\}\) and \(J_2\subseteq \{1,\cdots ,n_2\}\) identify the (possibly empty) indices of the integer-constrained variables in x and y, respectively, and the value function reads

$$\begin{aligned} \varPhi (x) = \min _{y\in {\mathbb {R}}^{n_2} } \{ f(x,y) : g(x,y) \le 0, \ y_j \in {\mathbb {Z}}\ \ \forall j \in J_2 \}. \end{aligned}$$
(19)

Dropping (16) leads to the HPR, which is a MILP in this setting. Dropping integrality conditions as well leads to the LP relaxation of HPR, namely (12)–(15), an LP which will be denoted by \(\overline{\hbox {HPR}}\).

Our main goal is to solve the above MIBLP by using a standard simplex-based branch-and-cut algorithm where the hard constraint (16) is enforced, on the fly, by adding cutting planes. The minimal requisite for the correctness of such an approach is the ability of cutting any vertex, say \((x^*,y^*)\), of \(\overline{\hbox {HPR}}\) which satisfies the integrality requirements (17) and (18) but is bilevel infeasible because

$$\begin{aligned} f(x^*,y^*) > \varPhi (x^*), \end{aligned}$$
(20)

thus preventing a wrong update of the incumbent. To this end, we will propose a novel application of Balas’ intersection cuts [2] in the MIBLP context.

5 A New Family of Cuts for MIBLP

Intersection cuts (IC’s) for a given \((x^*,y^*)\) require the definition of two sets: (1) a cone pointed at \((x^*,y^*)\) that contains all the bilevel feasible solutions, and (2) a convex set \(S^*\) that contains \((x^*,y^*)\) but no bilevel feasible solutions in its interior. The reader is referred to [2] for technical details.

As customary in mixed-integer programming, IC’s are generated for vertices \((x^*,y^*)\) of an LP relaxation of the problem to be solved, so a suitable cone is just the corner polyhedron associated with the corresponding optimal basis. All relevant information in this cone is readily available in the “optimal tableau” and requires no additional computational effort.

As to the convex set \(S^*\), we propose to use the set defined in Lemma 1 (or, better, in Theorem 1 if applicable) by choosing

$$\begin{aligned} \hat{y}= \arg \min _y \{ f(x^*, y) : g(x^*,y) \le 0, \ y_j \in {\mathbb {Z}}\ \forall j \in J_2 \} \end{aligned}$$
(21)

(assuming this problem is not unbounded). Indeed, such a set \(S^*\) does not contain any bilevel feasible point in its interior, as required, while \((x^*, y^*) \in S^*\) because of (20) and \(\varPhi (x^*) = f(x^*, \hat{y})\) by definition. Note that \(\hat{y}\) is well defined when \((x^*,y^*)\) is a solution of HPR, and that \(S^*\) is a convex polyhedron in the MIBLP case.

However, an important property is still missing, namely, \((x^*, y^*)\) must belong to the interior of \(S^*\) if we want to generate a violated intersection cut. This is always the case for MILBP’s for which \(S^*\) is the extended set defined as in Theorem 1. This includes problems with all-integer follower where \(J_2=\{1,\cdots ,n_2\}\), all g-coefficients are integer, and \(j \in J_1\) for all \(x_j\)’s appearing with nonzero coefficient in some follower constraint.

A relevant consequence of the above discussion is that, at least in the all-integer follower case, an exact branch-and-cut MIBLP solver can be obtained from a MILP solver by just adding a separation function for IC’s based on the extended set \(S^+(\hat{y})\) defined by (11) and (21). Indeed, observe that an exact MIBLP solver can be obtained by applying a general-purpose simplex-based MILP solver to HPR. To avoid the incumbent be updated with bilevel infeasible solutions, it is enough to cut any HPR solution \((x^*,y^*)\) with \(f(x^*,y^*)\) > \(\varPhi (x^*)\). Without loss of generality, by disabling internal MILP heuristics, we can assume that \((x^*,y^*)\) is a vertex of the current \(\overline{\hbox {HPR}}\) so we can always cut it by an (locally-valid) IC as, by definition, \((x^*,y^*)\) is in the interior of the extended \(S^+(\hat{y})\) when \(\hat{y}\) is defined as in (21). In addition, assuming that all leader’s variables x are integer and bounded, the number of HPR solutions to cut is finite, so a finite number of branching nodes (and hence of IC’s) will be generated, i.e., the method converges in a finite number of iterations.

In the heuristic attempt of producing violated IC’s for a generic vertex \((x^*,y^*)\) of the \(\overline{\hbox {HPR}}\) polyhedron, one could also consider the following alternative definition of the point \(\hat{y}\) that defines the bilevel-free set \(S^+(\hat{y})\):

$$\begin{aligned}&(\hat{y},\hat{d}) = \arg \max _{y,d} \{ d : f(x^*,y) + \varphi \, d \, \le f(x^*,y^*), \nonumber \\&\qquad \qquad \qquad \qquad \quad g(x^*,y) + \gamma d \le 1, \ y_j \in {\mathbb {Z}}\ \forall j \in J_2 \}, \end{aligned}$$
(22)

where \(\varphi \in {\mathbb {R}}_+\) and \(\gamma \in {\mathbb {R}}^{m_2}_+\) are suitable normalization factors, e.g., the Euclidean norm of the corresponding left-hand-side coefficient vectors. The rationale of this definition is that one wants to detect a bilevel-free set \(S(\hat{y})\) whose closest face to \((x^*,y^*)\) has a maximum distance from it.

Example

Figure 1 illustrates the application of IC’s on an example given in [7], which is frequently used in the literature:

$$\begin{aligned} \min _{x\in {\mathbb {Z}}} \ -x - 10y \end{aligned}$$
(23)
$$\begin{aligned} \ \ y \in \arg \min _{y'\in {\mathbb {Z}}}&\{ \ y' : \end{aligned}$$
(24)
$$\begin{aligned} -25x +20y'&\le 30 \end{aligned}$$
(25)
$$\begin{aligned} x +2 y'&\le 10 \end{aligned}$$
(26)
$$\begin{aligned} 2 x - y'&\le 15 \end{aligned}$$
(27)
$$\begin{aligned} 2 x + 10y'&\ge 15 \ \}. \end{aligned}$$
(28)

In this all-integer example, there are 8 bilevel feasible points (depicted as crossed squares in Fig. 1), and the optimal bilevel solution is (2, 2). The drawn polytope corresponds to the \(\overline{\hbox {HPR}}\) feasible set.

We first apply the definition of the bilevel-free set from Lemma 1 with \(\hat{y}\) defined as in (21). After solving the first \(\overline{\hbox {HPR}}\), the point \(A=(2,4)\) is found. This point is bilevel infeasible, as for \(x^*=2\) we have \(f(x^*,y^*) = y^*=4\) while \(\varPhi (x^*) = 2\). From (21) we compute \(\hat{y}= 2\) and the intersection cut derived from the associated \(S(\hat{y})\) is depicted in Fig. 1(a). In the next iteration, the optimal \(\overline{\hbox {HPR}}\) solution moves to \(B =(6,2)\). Again, for \(x^*=6\), \(f(x^*,y^*) = y^*=2\) while \(\varPhi (x^*) = 1\). So we compute \(\hat{y}= 1\) and generate the IC induced by the associated \(S(\hat{y})\), namely \(2x + 11y \le 27\) (cf. Fig. 1(b)). In the next iteration, the fractional point \(C=(5/2,2)\) is found and \(\hat{y}=1\) is again computed. In this case, C is not in the interior of \(S(\hat{y})\) so we cannot generate an IC cut from C but we should proceed and optimize HPR to integrality by using standard MILP tools such as MILP cuts or branching. This produces the optimal HPR solution (2, 2) which is bilevel feasible and hence optimal.

We next apply the definition of the enlarged bilevel-free set from Theorem 1 (whose assumption is fulfilled) with \(\hat{y}\) defined again as in (21); see Fig. 1(c) and (d). After the first iteration, the point \(A=(2,4)\) is cut off by a slightly larger \(S^+(\hat{y}=2)\), but with the same IC as before (\(y \le 2\)). After the second iteration, from the bilevel infeasible point \(B=(6,2)\) we derive a larger set \(S^+(\hat{y}=1)\) and a stronger IC (\(x +6y \le 14\)). In the third iteration, solution \(D=(2,2)\) is found which is the optimal bilevel solution, so no branching at all is required in this example.

Fig. 1.
figure 1

Illustration of the effect of alternative intersection cuts for a notorious example from [7]. Shaded regions correspond to the bilevel-free sets for which the cut is derived.

Full size image

6 Informed No-Good Cuts

A known drawback of IC’s is their dependency on the LP basis associated with the point to cut, which can create cut accumulation in the LP relaxation and hence shallow cuts and numerical issues. Moreover, IC’s are not directly applicable if the point to cut is not a vertex of a certain LP relaxation of the problem at hand, as it happens e.g. when it is computed by the internal MILP heuristics.

We next describe a general-purpose variant of IC’s whose derivation does not require any LP basis and is based on the well-known interpretation of IC’s as disjunctive cuts. It turns out that the resulting inequality is valid and violated by any bilevel infeasible solution of HPR in the relevant special case where all x and y variables are binary.

Suppose we are given a point \(\xi ^* =(x^*,y^*) \in {\mathbb {R}}^n\) and a polyhedron \(S^*=\{ \xi \in {\mathbb {R}}^n: \alpha _i^T \xi \le \alpha _{i0}, \, i=1,\cdots ,k\}\) whose interior contains \(\xi ^*\) but no feasible points. Assume that variable-bound constraints \(l \le \xi \le u\) are present, where some entries of l or u can be \(-\infty \) or \(+\infty \), respectively. Given \(\xi ^*\), define \(L :=\{ j : \xi ^*_j - l_j \le u_j - \xi ^*_j\}\) and \(U := \{1,\cdots ,n\}\setminus L\) and the corresponding linear mapping \(\xi \mapsto \overline{\xi }\in {\mathbb {R}}^n\) with \(\overline{\xi }_j := \xi _j-l_j\) for \(j\in L\), and \(\overline{\xi }_j := u_j - \xi _j\) for \(j\in U\) (variable shift and complement).

By assumption, any feasible point \(\xi \) must satisfy the disjunction

$$\begin{aligned} \bigvee _{i=1}^k \ \{ \, \xi \in {\mathbb {R}}^n: \sum _{j=1}^n\alpha _{ij} \xi _j \ge \alpha _{i0} \,\}, \end{aligned}$$
(29)

whereas \(\xi ^*\) violates all the above inequalities. Now, each term of (29) can be rewritten in terms of \(\overline{\xi }\) as

$$\begin{aligned} \sum _{j=1}^n \, \overline{\alpha }_{ij} \, \overline{\xi }_j \ge \overline{\beta }_i := \alpha _{i0} - \sum _{j\in L} \alpha _{ij} l_j - \sum _{j\in U} \alpha _{ij} u_j, \end{aligned}$$
(30)

with \(\overline{\alpha }_{ij} := \alpha _{ij}\) if \(j\in L\), \(\overline{\alpha }_{ij}=-\alpha _{ij}\) otherwise. If \(\overline{\beta }_i > 0\) for all \(i=1,\cdots ,k\), one can normalize the above inequalities to get \(\sum _{j=1}^n (\overline{\alpha }_{ij}/\overline{\beta }_i)\, \overline{\xi }_j\) \(\ge 1\) and derive the valid disjunctive cut in the \(\overline{\xi }\) space

$$\begin{aligned} \sum _{j=1}^n \overline{\gamma }_j \overline{\xi }_j \ge 1, \end{aligned}$$
(31)

where \(\overline{\gamma }_j := \max \{\overline{\alpha }_{ij}/\overline{\beta }_i: i=1,\cdots ,k\}\), and then one can transform it back to the \(\xi \) space in the obvious way. It is easy to see that, in case \(\xi ^*_j \in \{l_j,u_j\}\) for all \(j=1,\cdots ,n\), the above cut is indeed valid (because \(\overline{\beta }> 0\)) and obviously violated as \(\overline{\xi }^*=0\). In all other cases, the above cut separation is just heuristic.

Inequality (31) will be called Informed No-Good (ING) cut as it can be viewed as a strengthening of the following no-good cut often used for bilevel problems with all-binary variables—and in many other Constraint Programming (CP) and Mathematical Programming (MP) contexts:

$$\begin{aligned} \sum _{j\in L} \xi _j + \sum _{j \in U} (1-\xi _j) \ge 1. \end{aligned}$$
(32)

The cut above corresponds to the very generic choice

$$S^*=\{ \xi \in {\mathbb {R}}^n: \xi _j \le 1 \, \forall j \in L, \ 1-\xi _j \le 1 \, \forall j \in U \}$$

and is violated by \(\xi ^*\) but is satisfied by any other binary point, hence resulting into a very weak cut. To the best our knowledge, ING cuts are new; they will hopefully be useful in other CP and MP contexts.

7 Preliminary Computational Results

To evaluate the performance of our new cuts, we embedded them within the general-purpose MILP solver IBM ILOG Cplex 12.6.2 using callbacks, resulting into a branch-and-cut (B&C) MIBLP approach. Internal Cplex’s heuristics as well preprocessing have been deactivated in all experiments. IC separation is applied at the root node on all LP solutions (in the so-called usercut callback), while for the remaining nodes it is only applied to integer solutions (lazycut callback). For fractional solutions, IC’s whose normalized violation is too small are just skipped. All generated cuts are treated as local cuts (even if no-good and ING cuts would be globally valid) as this reduces the node LP size and significantly improves node throughput. To improve the quality of IC cuts, the bilevel-free set is enlarged by removing all its defining inequalities \(\alpha ^T (x,y) \le \alpha _0\) (say) such that imposing the reverse condition \(\alpha ^T (x,y) \ge \alpha _0\) would trivially lead to an infeasible HPR relaxation due to the current bounds on the x and y variables (this step turns out to be very important for the success of our method). More implementation details will be given in the full paper.

We first compared our code with the one in [3] on the testbed proposed therein. All such instances turned out to be very easy, both for our approach and for MibS. More precisely, each instance could be solved in less than a second by our code and in at most 3 s by MibS, i.e., both codes were 2–3 orders of magnitude faster than the one in [3]. Therefore we addressed more difficult instances, obtained according to the following procedure.

We took a familiar testbed (MILPLIB 3.0) that contains instances that are easily solvable by modern MILP solvers (except instance seymour which is very hard even as a MILP). As we planned to also run the open-source MIBLP solver MibS [8] to check our code, we skipped all instances involving equations or continuous variables, as well as those involving noninteger coefficients—all the above cases being not supported by the current release of MibS. This produced a set of 10 basic 0–1 MILP instances, that we converted into bilevel problems by labeling the first \(Y\%\) (rounded up) variables as y’s, and the remaining ones as x’s. In our test, we considered the three cases with \(Y\in \{10,50,90\}\) leading to instances named name-0.1.mps, name-0.5.mps, and name-0.9.mps, respectively. All constraints in the resulting model belong to the follower subproblem, as MibS cannot handle leader-specific constraints \(G(x,y)\le 0\), while the objective function is used as the leader’s objective F(x, y). Finally, the follower’s objective is defined as \(f(x,y)=-F(x,y)\).

In Table 1, we use MibS to assess the computational difficulty of the instances we generated. The table also reports results for our basic B&C code (with IC’s but not ING cuts) when run in single-thread mode and with internal Cplex cuts disabled. Note that the two solvers cannot be compared directly, as they are based on a different underlying MILP code, namely: Cplex for our code, and COIN-OR (BLIS) plus Cplex for MibS. For both codes, we report in Table 1 the following values: the best obtained upper bound (UB), the best obtained lower bound (LB), the final percentage gap (%gap) calculated as (UB - LB) / UB \(\times \) 100. Computing times (t.[s]) are wall-clock seconds on an Intel Xeon E5-2670v2 @ 2.5 Ghz computer with 12 GB ram. The timelimit was set to 600 s as larger values produced memory issues for some instances where the number of tree nodes is very large. If the time-limit was reached, this is notified as “TL” in the time column. These results clearly indicate that we managed to generate a testbed which is sufficiently challenging for state-of-the-art MIBLP solvers.

Table 1. Instance difficulty when using two different MIBLP solvers
Full size table

Table 2 compares four settings for our code: (1) only no-good cuts are generated, (2) only ING cuts are generated, (3) only IC’s are generated, and (4) IC’s are generated for fractional solutions at root node, while only ING cuts generated for integer ones. Note that all settings lead to an exact method as all instances in our testbed are pure binary. All versions were run in 4-thread opportunistic mode, without disabling internal Cplex cuts, on a Intel Xeon E3-1220V2 quadcore PC @ 3.10 GHz with 16 GB of RAM. Setting (1) is intended to assess the difficulty of the created data set for a method built on top of Cplex, but using the most basic MIBLP cuts (no-good). Setting (2) is intended to measure the performance improvement obtained by replacing generic no-good cuts with bilevel-specific ING cuts, while the impact of IC’s is addressed in setting (3). Finally, setting (4) combines IC’s and ING cuts to limit the negative effect of cut accumulation in the LP basis.

Table 2. Comparison of different settings of our B&C approach.
Full size table

For each of the four setting and for each instance, in Table 2 we report the same information as in Table 1, plus the overall number of branch-and-bound nodes (#nodes).

The influence of IC’s to the performance of the B&C can be measured by comparing the quality of lower bounds of the setting (3), with the settings (1) and (2). In 14, respectively 11 cases, the LBs obtained by IC’s are strictly stronger than those obtained by pure no-good and ING cuts, respectively. The quality of lower bounds when IC’s are combined with ING cuts remains roughly the same across all instances. As expected, the setting (1) exhibits the worst performance with 22 instances remaining unsolved within the given time-limit. ING cuts perform better (in particular considering the quality of lower bounds), but still with 20 instances remaining unsolved. Both settings with IC’s and IC’s with ING cuts manage to solve 12 instances to optimality. The number of enumerated branch-and-bound nodes varies strongly between the instances, even between those being derived from the same MIPLIB source. This indicates that, despite the fact that some instances are derived from the identical HPR formulation, the difficulty is mainly determined by the structure of the follower subproblem.