Optimising non-convex Choquet integrals using DC (difference of convex) algorithm

We address the problem of optimising piece-wise linear objectives based on the discrete Choquet integral, subject to multiple linear constraints. Such problems arise when aggregating interacting decision variables, which can show positive (synergies) or negative (redundancies) interactions. Non-additivity of fuzzy measures offers a sound mathematical framework to model various interactions, and the Choquet integral is a suitable generalisation of the traditional linear objectives. We deal with fuzzy measures which offer both kinds of interactions, and we decompose them into sub-and supermodular parts. This leads to optimising objectives represented as the sum of convex and concave parts. We employ the Difference of Convex (DC) functions algorithm instantiated and tailored for our specific kinds of objectives, and study its numerical scalability.