  Solving large-scale Mixed Integer Programs (MIP) can be difficult without
advanced algorithms such as decomposition based techniques. Even if a
decomposition technique might be appropriate, there are still many possible
decompositions for any large MIP and it may not be obvious which will be the
most effective. This paper presents a comprehensive analysis of the predictive
capabilities of a Machine Learning ranking (ML) function for predicting the
quality of Mixed Integer Programming (MIP) decompositions created via
constraint relaxation. In this analysis, the role of instance similarity and ML
prediction quality is explored, as well as the benchmarking of a ML ranking
function against existing heuristic functions. For this analysis, a new dataset
consisting of over 40000 unique decompositions sampled from across 24 instances
from the MIPLIB2017 library has been established. These decompostions have been
created by both a greedy relaxation algorithm as well as a population based
multi-objective algorithm, which has previously been shown to produce high
quality decompositions. In this paper, we demonstrate that a ML ranking
function is able to provide state-of-the-art predictions when benchmarked
against existing heuristic ranking functions. Additionally, we demonstrate that
by only considering a small set of features related to the relaxed constraints
in each decomposition, a ML ranking function is still able to be competitive
with heuristic techniques. Such a finding is promising for future constraint
relaxation approaches, as these features can be used to guide decomposition
creation. Finally, we highlight where a ML ranking function would be beneficial
in a decomposition creation framework.
