  Decades of research on the 0-1 knapsack problem led to very efficient
algorithms that are able to quickly solve large problem instances to
optimality. This prompted researchers to also investigate whether relatively
small problem instances exist that are hard for existing solvers and
investigate which features characterize their hardness. Previously the authors
proposed a new class of hard 0-1 knapsack problem instances and demonstrated
that the properties of so-called inclusionwise maximal solutions (IMSs) can be
important hardness indicators for this class. In the current paper, we
formulate several new computationally challenging problems related to the IMSs
of arbitrary 0-1 knapsack problem instances. Based on generalizations of
previous work and new structural results about IMSs, we formulate polynomial
and pseudopolynomial time algorithms for solving these problems. From this we
derive a set of 14 computationally expensive features, which we calculate for
two large datasets on a supercomputer in approximately 540 CPU-hours. We show
that the proposed features contain important information related to the
empirical hardness of a problem instance that was missing in earlier features
from the literature by training machine learning models that can accurately
predict the empirical hardness of a wide variety of 0-1 knapsack problem
instances. Using the instance space analysis methodology, we also show that
hard 0-1 knapsack problem instances are clustered together around a relatively
dense region of the instance space and several features behave differently in
the easy and hard parts of the instance space.
