Exact Approaches for the Maximum Mortality Rate Clique Problem

Abstract

This paper develops exact solution methods for the Maximum Mortality Rate Clique Problem (MMRCP), which aims to identify clusters of diseases in a comorbidity graph associated with the highest mortality rates among patients whose healthcare encounters are recorded in electronic health records. We establish the NP-hardness of the problem and propose two mixed-integer linear programming formulations, a combinatorial branch-and-bound algorithm, and a logic-based Benders decomposition (LBBD) framework. A hybrid LBBD variant that strategically invokes the combinatorial algorithm to strengthen node relaxations offers a computationally effective approach. The framework accommodates side constraints on the discovered cliques, such as age-based restrictions, revealing qualitatively distinct lethal disease combinations that are unlikely to be driven solely by elevated baseline mortality in elderly populations. The proposed optimization framework provides a practical and flexible tool for medical researchers seeking to identify lethal multimorbidity patterns and investigate disease progression and interactions.