11institutetext: Institute of Mathematics, Technische Universität Berlin,
Germany 22institutetext: Zuse Institute Berlin, Germany33institutetext: Fair
Isaac Deutschland GmbH, Berlin, Germany
33email: {turner, besancon<EMAIL_ADDRESS>33email<EMAIL_ADDRESS>
# Cutting Plane Selection with Analytic Centers and Multiregression

Mark Turner 1122 Timo Berthold 1133
Mathieu Besançon 22 Thorsten Koch 1122

(August 2022)

###### Abstract

Cutting planes are a crucial component of state-of-the-art mixed-integer
programming solvers, with the choice of which subset of cuts to add being
vital for solver performance. We propose new distance-based measures to
qualify the value of a cut by quantifying the extent to which it separates
relevant parts of the relaxed feasible set. For this purpose, we use the
analytic centers of the relaxation polytope or of its optimal face, as well as
alternative optimal solutions of the linear programming relaxation. We assess
the impact of the choice of distance measure on root node performance and
throughout the whole branch-and-bound tree, comparing our measures against
those prevalent in the literature. Finally, by a multi-output regression, we
predict the relative performance of each measure, using static features
readily available before the separation process. Our results indicate that
analytic center-based methods help to significantly reduce the number of
branch-and-bound nodes needed to explore the search space and that our
multiregression approach can further improve on any individual method.

##  1 Introduction

Branch-and-cut is the algorithm at the core of most Mixed-Integer Programming
(MIP) solvers. A key component of branch-and-cut is the resolution of Linear
Programming (LP) relaxations of the original problem over partitions of the
variable domains. _Cutting planes_ – or cuts – tighten those relaxations
around integer-feasible points. Given a MIP:

$\displaystyle\underset{\mathbf{x}}{\text{argmin}}\\{\mathbf{c}^{\intercal}\mathbf{x}\;\;|\;\;\mathbf{A}\mathbf{x}\leq\mathbf{b},\;\;\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\;\;\mathbf{x}\in\mathbb{Z}^{|\mathcal{J}|}\times\mathbb{R}^{n-|\mathcal{J}|}\\}$
(P)

a cut is an inequality $\boldsymbol{\alpha}^{\intercal}\mathbf{x}\leq\beta$
that is violated by at least one solution of the LP relaxation but that does
not increase the optimal value of the problem when added i.e. it is valid for
(P). Thereby, the inequality added as a constraint to (P) tightens the
relaxation, potentially increasing the relaxation’s optimal value. The use of
cutting planes is one of the crucial aspects to solving MIPs efficiently
[achterberg2013mixed]. A well-designed cutting plane separation procedure
often helps to reduce the branch-and-bound tree size while accelerating the
overall solving process.

In MIP solvers, two key algorithms related to cuts are their generation and
their selection. Cut generation is the problem of computing a set of cuts that
tighten the relaxation and separate the current continuous relaxation solution
from the feasible MIP solutions. Modern MIP solvers implement various general-
purpose and specialised cutting plane generation algorithms. Since the
generation of cuts is, in general, far less expensive than solving the LP
relaxation, many cuts are generated from the same relaxation. The cut
selection algorithm takes the set of all cut candidates generated so far and
selects a subset that is actually added to the LP relaxation. This two-step
process of generation and selection constitutes a single _separation round_.

At the root node, the MIP solver interleaves separation rounds with solving
the enhanced LP relaxation until the branch-and-bound search is started. At
other search tree nodes, the solver often only performs a limited cut loop, if
at all. We focus in this paper on globally-valid cuts, i.e. cuts that are
valid for the original problem, as opposed to _local cuts_ , which are
generated with additional local bounds at a node.

Cut selection is a classical trade-off problem: too little cutting leads to
large enumeration trees; too much cutting to a small node throughput and
numerical instability. However, carefully selected cuts can help improve both
the dual and the primal bound simultaneously by bringing the relaxation closer
to the convex hull of feasible solutions. Since proximity to the convex hull
is inherently hard to measure, cut selection methods often try to approximate
it by various cheap measures, e.g., efficacy.

_Efficacy_ , or _cutoff distance_ , is used in commercial MIP solvers as one
of the main criteria for whether to add a cut or not
[achterberg2007constraint, scip8]111Confirmed as a main criterion in FICO
Xpress 8.14. Efficacy measures the shortest distance between the LP optimal
solution $\mathbf{x}^{LP}$ and the cut hyperplane
$\boldsymbol{\alpha}^{\intercal}\mathbf{x}\leq\beta$. The function
$\mathtt{eff}$ that maps a cut, and the LP solution $\mathbf{x}^{LP}$ to the
efficacy is defined as:

$\displaystyle\mathtt{eff}(\boldsymbol{\alpha},\beta,\mathbf{x}^{LP}):=\frac{\boldsymbol{\alpha}^{\intercal}\mathbf{x}^{LP}-\beta}{\|\boldsymbol{\alpha}\|}$

Introduced in [scip6], _directed cutoff distance_ is the signed distance
between the LP solution $\mathbf{x}^{LP}$ and the cut hyperplane in the
direction of a primal solution, $\mathaccent 28766{\mathbf{x}}$. The measure
has the property that the directed projection of $\mathbf{x}^{LP}$ onto the
cut hyperplane is inside of the feasible region, and by using the best primal
solution available, aims to cut in the direction of the optimal solution. We
define the directed cutoff distance, with the function $\mathtt{dcd}$ as
follows:

$\displaystyle\mathtt{dcd}(\boldsymbol{\alpha},\beta,\mathbf{x}^{LP},\mathaccent
28766{\mathbf{x}}):=\frac{\boldsymbol{\alpha}^{\intercal}\mathbf{x}^{LP}-\beta}{|\boldsymbol{\alpha}^{\intercal}\mathbf{y}|},\;\text{where}\quad\mathbf{y}=\frac{\mathaccent
28766{\mathbf{x}}-\mathbf{x}^{LP}}{||\mathaccent
28766{\mathbf{x}}-\mathbf{x}^{LP}||}$

The last measure we consider, although not based on a distance, is _expected
improvement_ , see [wesselmann2012implementing], which corresponds to the
difference in objective between $\mathbf{x}^{LP}$ and its orthogonal
projection onto the hyperplane of a cut. We denote the measure as
$\mathtt{exp}\text{-}\mathtt{improv}$, and define it as:

$\displaystyle\mathtt{exp}\text{-}\mathtt{improv}(\boldsymbol{\alpha},\beta,\mathbf{c},\mathbf{x}^{LP}):=$
$\displaystyle\;||\mathbf{c}||\;\cdot\;\frac{\boldsymbol{\alpha}^{\intercal}\mathbf{c}}{||\boldsymbol{\alpha}||||\mathbf{c}||}\;\cdot\;\mathtt{eff}(\boldsymbol{\alpha},\beta,\mathbf{x}^{LP})$

In this paper, we propose new distance-based measures for the quality of cuts.
These measures are designed to retain soundness properties in common cases
that hinder the applicability, and to reduce the size of the search space,
without focusing on runtime improvement. To this end, we perform extensive
computational experiments to analyse the effects of our newly introduced
measures and those that exist in the literature. Unlike previous beliefs, the
choice of distance measure significantly impacts solver performance both in
time and number of nodes, with different measures performing better on
different groups of instances. Motivated by this observation, we design a
multi-output regression model, which predicts the relative performance of each
measure using static features readily available before the separation process.
Finally, in Appendix LABEL:sec:density, we complement our investigation of cut
selection with an analysis of the impact of dense cutting planes on solver
performance. The scope of this paper is to establish a model that aims at
reducing search space size rather than runtime.

##  2 Related Work

There is a prevailing sentiment in the MIP community, supported by a set of
older computational studies, see [achterberg2007constraint, zerohalf,
wesselmann2012implementing], that inexpensive heuristics are sufficient for
cut selection. Specifically, these studies suggest that cheap ranking metrics,
predominantly efficacy, are sufficiently effective when combined with
filtering mechanisms that ensure no two overly parallel cuts are added. The
studies [achterberg2007constraint, wesselmann2012implementing] argue that a
weighted sum of different metrics is most effective for ranking cuts as
opposed to any single metric.

Recently, the research focus for cuts in MIP has been on using deep learning
to either calculate scores directly from a set of measures or to predict
parameter values in scoring functions, see [baltean2019scoring,
tang2020reinforcement, huang2021learning, balcan2021sample,
turner2022adaptive, paulus2022learning]. In [baltean2019scoring] and
[paulus2022learning] a neural network is trained to predict the objective
value improvement of cuts when added. In [tang2020reinforcement], a neural
network is trained using evolutionary strategies to select Gomory cuts. A
neural network is also trained in [huang2021learning], this time using
multiple instance learning, to map a set of aggregate cut features to a
scoring function. In [balcan2021sample], the cut selection parameter space is
shown to be partitionable into a set of regions, such that all parameter
choices within a region select the same set of cuts. Finally, for cut scores
based on weighted criteria, [turner2022adaptive] provides an illustrative
example of worst-case scenario for parameter grid search in the cut selection
parameter space, and phrases learning cut selection parameters as a
reinforcement learning problem.

Closest to our work are papers that introduced cut selection measures other
than efficacy, which were still based on a notion of measuring distances.
_Directed cutoff distance_ was introduced in SCIP 6.0 [scip6], other measures
such as _rotated cutoff distance_ and _distance with bounds_ were explored in
[wesselmann2012implementing], and _depth_ was introduced in [depth]. Measures
based on non-distance arguments are also prevalent in cut selection, albeit
often as smaller weighted complements to a distance measure, see _objective
parallelism_ and _integer support_ in [achterberg2007constraint,
wesselmann2012implementing], and enumeration of lattice points in
[latticepoints].

In the presented distance measures of Section 1, an LP-optimal solution is
used as a reference point. Note, however, that this optimum is not necessarily
unique, with the set of minimisers frequently being a higher-dimensional face
of the LP-feasible region due to dual degeneracy [mipdegeneracy]. The optimal
solution used in these degenerate cases inevitably has a large impact on cut
generation [lexicographicgomory], and therefore cut selection. This has been
noted in previous research, with work such as [multiplelpcutting] using
multiple LP solutions from different LP random seeds to generate different
sets of cuts. Additionally, the patent [cplexpatent], proposes using a second
LP optimal solution at the same cutting round to filter cuts derived from the
original LP solution. They provide an example, where a second LP solution that
prioritises integrality is found, which then filters all cuts that do not
separate it. Dual degeneracy is one major aspect motivating some of the newly-
proposed measures in our work.

Finally, analytic centers have been used in other aspects of MIP solving,
namely, presolving [berthold2018four], cut generation [fischetti2009yoyo],
branching [berthold2018four], and heuristics [BAENA2011310,
naoum2014recursive], motivating the measures introduced in this paper.

##  3 Contributions and methodology

The contribution of the present paper is threefold. First, we introduce new
distance-derived cut quality measures, the most important of which utilise
analytic centers, and analyse properties of interest for these measures in
cases of dual degeneracy and infeasible projections. Secondly, we present an
extensive set of computational experiments on the effectiveness of our new
measures and those commonly found in practice, showing that the choice of cut
selection measure does have a strong influence on root-node and tree-wide
performance. Thirdly, we introduce a multi-output regression model that
predicts a ranking of distance measures per instance from a set of root node
features.

###  3.1 Analytic Center-Based Methods

We propose two new methods for measuring cut quality: _analytic efficacy_ ,
and _analytic directed cutoff distance_. They are based on the analytic center
of the polytope and of the optimal face, respectively. For a given bounded MIP
formulation (P), the analytic center is unique and in the relative interior of
the feasible region.

When a constraint $\mathbf{a}^{\intercal}\mathbf{x}\leq b$ is tight for any
feasible solution or in the presence of equality constraints, the analytic
center is not well-defined due to a log-barrier term being $+\infty$. In
practice, algorithms relax all log-barriers with a fixed slack constant as
long as constraints are imposed on solutions.

While the analytic center is invariant under affine transformations of Problem
(P), it can change with reformulations. E.g., the analytic center can be
shifted by the presence of redundant inequalities. For our work, we assume
that the formulation has already been presolved by the MIP solver. Presolving
includes tightening both variable bounds and constraints, and removing both
redundant constraints and variables. It thereby limits the extent of such edge
cases.

####  3.1.1 Analytic efficacy

As opposed to using the $\mathbf{x}^{LP}$ extreme point returned by the MIP
solver for $\mathtt{eff}$ calculations, we propose a new measure that uses the
analytic center of the optimal face of the LP, $\mathbf{x}^{F}$. We define
$\mathbf{x}^{F}$ by the following using the notation from Problem (P), where
$\mathbf{A}_{i}$, $\mathbf{b}_{i}$, $\mathbf{u}_{i}$, and $\mathbf{l}_{i}$ are
the $i$-th row or $i$-th entry of their respective matrix or vector:

$\displaystyle\mathbf{x}^{F}$
$\displaystyle:=\underset{\mathbf{x}\;:\;\mathbf{c}^{\intercal}\mathbf{x}=\mathbf{c}^{\intercal}\mathbf{x}^{LP}}{\text{argmin}}\\{-\sum_{i=1}^{m}\log(\mathbf{b}_{i}-\mathbf{A}_{i}\mathbf{x})-(\sum_{i=1}^{n}\log(\mathbf{x}_{i}-\mathbf{l}_{i})+\log(\mathbf{u}_{i}-\mathbf{x}_{i}))\\}$

In practice, we find $\mathbf{x}^{F}$ using the barrier (or interior point)
algorithm on the LP relaxation without crossover, see [berthold2018four]. This
algorithm is available in all modern MIP solvers, and is often run
concurrently to the simplex at the root node, making our cut selection
algorithms of practical interest for MIP solving.

The obtained center $\mathbf{x}^{F}$ is different from $\mathbf{x}^{LP}$ only
if the current problem presents dual degeneracy. The purpose of evaluating
cuts with respect to how much they separate the center of the optimal face is
to favour those which cut a greater part or potentially all of the optimal
face, thereby more likely favouring an improvement in the dual bound. Compare
Figures 1(a) and 1(c) for the intuition behind analytic efficacy.

####  3.1.2 Analytic directed cutoff distance

This measure is inspired by directed cutoff distance, and uses the analytic
center of the feasible region, $\mathbf{x}^{C}$, as opposed to the best
incumbent solution $\mathaccent 28766{\mathbf{x}}$. Using the same notation as
in Section 3.1.1, we define the analytic center of the feasible region,
$\mathbf{x}^{C}$, as:

$\displaystyle\mathbf{x}^{C}$
$\displaystyle:=\underset{\mathbf{x}}{\text{argmin}}\\{-\sum_{i=1}^{m}\log(\mathbf{b}_{i}-\mathbf{A}_{i}\mathbf{x})-(\sum_{i=1}^{n}\log(\mathbf{x}_{i}-\mathbf{l}_{i})+\log(\mathbf{u}_{i}-\mathbf{x}_{i}))\\}$

$\mathbf{x}^{C}$ is often interpreted as the “central-most” point of the
polytope and can be computed efficiently by dropping the objective function
$\mathbf{c}^{\intercal}\mathbf{x}$ and solving the resulting LP relaxation
using the barrier algorithm without crossover. The motivation is that the
incumbent is not necessarily representative of the feasible set of the MIP
since it can be any point of the feasible set generated by heuristics.
Furthermore, it introduces an additional source of variability in the cut
selection since the best primal solution is prone to updates, particularly
during root node cutting when many primal heuristics are employed. By
contrast, $\mathbf{x}^{C}$ is unique and deterministically determined for the
LP relaxation. Compare Figures 1(b) and 1(d) for the intuition behind analytic
directed cutoff distance.

For computational efficiency, we further introduce _approximate analytic
directed cutoff distance_ , which re-uses the analytic center,
$\mathbf{x}^{C}$, from the previous separation round provided it is still LP-
feasible. This is motivated by the intuition that the analytic center, as the
“central-most” point, is rarely separated and remains close to the new
analytic center after cuts have been added.

$\mathbf{x}^{LP}$ (a) Efficacy

$\mathaccent 28766{\mathbf{x}}$$\mathbf{x}^{LP}$ (b) Directed cutoff distance

$\mathbf{x}^{LP}_{1}$$\mathbf{x}^{F}$ $\mathbf{x}^{LP}_{2}$ (c) Analytic
efficacy

$\mathbf{x}^{LP}$$\mathbf{x}^{C}$ (d) Analytic directed cutoff distance

Figure 1: A visualisation of distance measures. Note that in Figure 1(c) we
see that there are two alternative optimal vertices.

###  3.2 Multiple LP solutions

We also introduce two distance measures, which mitigate cases of dual
degeneracy and do not rely on analytic centers, but rather rely on multiple
LP-optimal vertices. Let $\mathcal{X}^{LP}$ be a set of LP optimal solutions.
We propose the measures _average efficacy_ , denoted $\mathtt{avgeff}$, and
_minimum efficacy_ , denoted $\mathtt{mineff}$, which respectively take the
average and minimum efficacy over all LP solutions in $\mathcal{X}^{LP}$.

$\displaystyle\mathtt{avgeff}(\boldsymbol{\alpha},\beta,\mathcal{X}^{LP})$
$\displaystyle:=\sum_{\mathbf{x}^{LP}\in\mathcal{X}^{LP}}\frac{\mathtt{eff}(\boldsymbol{\alpha},\beta,\mathbf{x}^{LP})}{|\mathcal{X}^{LP}|}$
$\displaystyle\mathtt{mineff}(\boldsymbol{\alpha},\beta,\mathcal{X}^{LP})$
$\displaystyle:=\text{min}\\{\mathtt{eff}(\boldsymbol{\alpha},\beta,\mathbf{x}^{LP})\;\;|\;\;\mathbf{x}^{LP}\in\mathcal{X}^{LP}\\}$

$\mathbf{x}^{LP}_{1}$$\mathbf{x}^{LP}_{2}$ (e) The dashed cut removes the
entire optimal face, and thereby is likely preferable. Efficacy however scores
the dotted cut higher (black lines). Analytic, minimum, and average efficacy
prefer the dashed cut.

$\mathbf{x}^{LP}$ (f) The projection from $\mathbf{x}^{LP}$ onto the dashed
cut is LP-infeasible, limiting its usefulness as a measure. The dotted cut is
dominated but would still be selected by efficacy.

Figure 2: Two cases showing the limitation of efficacy, in the presence of
dual degeneracy 2, and infeasible projection 2. The blue polytope represents
the LP feasible region, the black dots integer solutions, the red lines are
proposed cuts, and $\mathbf{x}^{LP}$ represents a LP optimal solution. In both
cases, the dotted cut has a higher efficacy even though it is likely not
preferable.

###  3.3 Properties and limitations of the distance measures

In this section, we highlight situations in which the standard interpretations
of some distance measures are limited; we introduce dominance consistency, a
soundness property for distance measures, and establish cases under which it
holds and under which it does not. Examples of dominance consistency also
offer valuable insight into the geometry of different measures.

Efficacy, similarly expected improvement, uses the orthogonal projection of
$\mathbf{x}^{LP}$ onto the cut to measure distance. Unlike measures such as
directed cutoff distance, the projection point might not be LP feasible,
potentially making efficacy non-representative of the strength of the cut. A
larger efficacy does not necessarily correspond to a larger part of the
polyhedron being cut off nor to a better improvement in dual bound, see Figure
2. Note that minimum and analytic efficacy would not assign the dotted cut a
positive score. Efficacy would prefer the dotted cut even though it does not
improve the dual bound while the dashed cut does. Figure 2 visualises a basic
example of when the orthogonal projection used for efficacy is LP-infeasible
and thus not necessarily a good proxy for cut quality. Analytic efficacy,
minimum efficacy, and average efficacy help overcome some limitations of
efficacy, namely the dependence on the vertex returned by the LP solve. They
are, however, equivalent when the current relaxation is not dual-degenerate
since they then compute the distance to the cut using the same, unique optimal
vertex.

Directed cutoff distance heavily depends on the incumbent solution, which is
typically obtained from a primal heuristic.222At the root node, in particular,
the incumbent – if existing – will always come from a heuristic, otherwise
there would be no more cut rounds. This primal solution may be sub-optimal and
near a corner of the feasible region, biasing cuts in an unfavourable
direction. Additionally, the primal solution may be LP-infeasible for local
relaxations of the branch-and-bound tree, reducing the applicability of
directed cutoff distance.

Ultimately, one would like a distance measure to be a surrogate for solver
efficiency, in our case: the size of the search space in terms of branch and
bound nodes. Such a measure is impossible to quantify however, with solution
fractionality being insufficient, and the closest analogue, ‘strong cutting’,
which measures the dual bound improvement of an added cut, see
[paulus2022learning], being computationally intractable. The holy grail of cut
selection is to either identify a computationally tractable measure that is a
reasonably good proxy for solver performance, or to learn to adaptively select
a suitable measure based on the input instance.

In the following, we will formalise these considerations. Therefore, we first
recall the basic concepts of cut dominance and feasible rays. A cut
$(A)=(\boldsymbol{\alpha}_{A},\beta_{A})$ _dominates_ another cut
$(B)=(\boldsymbol{\alpha}_{B},\beta_{B})$ if all points of the polytope cut by
$(A)$ are cut by $(B)$ and there exists a point cut by $(A)$ not cut by $(B)$.
We highlight that this definition of dominance is more general than, e.g.,
[wolsey2020integer, Definition 9.2.1] since it only requires dominance to hold
in the polytope and not in the whole space or the positive orthant. We define
a _feasible ray_ as a ray $\mathbf{r}$ starting from an LP-feasible point
$\mathbf{x}$ for which there exists $\lambda>0$ such that
$\mathbf{x}+\lambda\mathbf{r}$ is LP-feasible. Such a ray always exists by
convexity if the polyhedron is not a single point.

######  Definition 1 (Dominance consistency)

Given a MIP (P) and a relaxation point to cut off $\mathbf{x}$, a distance
measure noted $d(\mathbf{x},\boldsymbol{\alpha}_{X},\beta_{X})$ is _dominance-
consistent_ w.r.t. a set of cuts iff for any cut $(A)$ and $(B)$ in the set,
$d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})>d(\mathbf{x},\boldsymbol{\alpha}_{B},\beta_{B})$
implies that $(A)$ is not dominated by $(B)$.

Note that with this definition, for a given MIP and LP solution $\mathbf{x}$,
one set of cuts (e.g., from one separation round) can imply dominance
consistency for a measure while another set of cuts (e.g., from another
separation round) might not. We will see that for some measures, dominance
consistency applies for all sets of cuts, all relaxation points, and all MIPs.
Dominance consistency is a desirable property for a cut selection measure
since a fully dominated cut will systematically be inferior to the dominating
cut from the cut strength perspective.333Note that we disregard other cut
properties such as density, numerical stability, or orthogonality here.

######  Proposition 1 (Consistency of Euclidean distance measures)

All measures consisting of the Euclidean distance of a given point
$\mathbf{x}$ to the cut hyperplane are dominance-consistent with respect to
any set of cuts if, for any two cuts in the set, the cut with the smallest
distance measure cuts off $\mathbf{x}$ and the projection of $\mathbf{x}$ onto
its hyperplane is LP-feasible.

###### Proof

Let $(A)$ and $(B)$ be the two cuts of the set. The proof directly applies to
more cuts by induction. We assume w.l.o.g. that
$d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})>d(\mathbf{x},\boldsymbol{\alpha}_{B},\beta_{B})$.
The set of cuts with distance measure
$d(\mathbf{x},\cdot,\cdot)=d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})$ is
a subset of the hyperplanes tangent to the sphere of radius
$d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})$ centered at $\mathbf{x}$.
The cut $(B)$ does not separate the projection of $\mathbf{x}$ onto its own
hyperplane, which is by assumption LP-feasible. The projected point lies on
the sphere of radius $d(\mathbf{x},\boldsymbol{\alpha}_{B},\beta_{B})$
centered at $\mathbf{x}$, and is contained in the open ball of radius
$d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})$ centered at $\mathbf{x}$. As
a tangent hyperplane to the sphere of radius
$d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})$, $(A)$ therefore cuts off
the projected point by at least
$d(\mathbf{x},\boldsymbol{\alpha}_{A},\beta_{A})-d(\mathbf{x},\boldsymbol{\alpha}_{B},\beta_{B})$
and can therefore not be dominated.∎

Proposition 1 directly applies to efficacy and analytic efficacy, with the key
restriction that the projection of the relaxation point onto the cut must be
LP-feasible, which excludes a majority of real instances. Furthermore, since
$\mathtt{eff}$ is a linear function of $\mathbf{x}^{LP}$, the property also
applies to $\mathtt{avgeff}$ as a distance measure, with the point to project
$\mathbf{x}$being the average of the multiple LP solutions. Finally, we can
construct counter-examples where dominance-consistency does not hold for
measures based on the Euclidean projection of a point onto the cut hyperplane
in cases where the projection is not LP-feasible, as shown in Figure 2.

######  Proposition 2 (Consistency of the minimum efficacy)

Given the set of LP solutions $\mathcal{X}^{LP}$, we define the active
solutions for a cut $(\boldsymbol{\alpha},\beta)$ as the subset
$\operatorname*{arg\,min}_{\mathbf{x}\in\mathcal{X}^{LP}}\mathtt{eff}(\boldsymbol{\alpha},\beta,\mathbf{x})$.
$\mathtt{mineff}$ is dominance-consistent with respect to a set of cuts if for
any two cuts $(A)$ and $(B)$ such that $(B)$ has a strictly lower
$\mathtt{mineff}$, there exists an active solution $\mathbf{x}_{0}$ separated
by $(B)$ such that its projection onto the hyperplane of $(B)$ is LP-feasible.