MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

A Generic Algorithmic Framework to Solve Special Versions of the Set Partitioning Problem

Robin Lamarche-Perrin, Yves Demazeau and Jean-Marc Vincent


Given a set of individuals, a collection of admissible subsets, and a cost associated to each of these subsets, the \emph{Set Partitioning Problem} (SPP) consists in selecting admissible subsets to build a partition of the individuals that minimizes the total cost. This combinatorial optimization problem has been used to model dozens of problems arising in specific domains of Artificial Intelligence and Operational Research, such as coalition structures generation, community detection, multilevel data analysis, workload balancing, image processing, and database optimization. All these applications are actually interested in \emph{special versions} of the SPP: the admissible subsets are assumed to satisfy global algebraic constraints derived from topological or semantic properties of the individuals. For example, admissible subsets might form a hierarchy when modeling nested structures, they might be intervals in the case of ordered individuals, or rectangular tiles in the case of bidimensional arrays. Such constraints structure the search space and -- if strong enough -- they allow to design tractable algorithms for the corresponding optimization problems. However, there is a major lack of unity regarding the identification, the formalization, and the resolution of these strongly-related combinatorial problems. To fill the gap, this article proposes a generic framework to design specialized dynamic-programming algorithms that fit with the algebraic structures of any special versions of the SPP. We show how to apply this framework to two well-known cases, namely the \emph{Hierarchical SPP} and the \emph{Ordered SPP}, thus opening a unified approach to solve versions that might arise in the future.

Oct 6, 2014
Oct 9, 2014
Combinatorial Optimization, Set Partitioning Problem, Structural and Semantical Constraints, Algebraic Structure of Partition Lattices, Dynamic Programming, Specialized Optimization Algorithms, Artificial Intelligence, Operational Research

Related publications

2014 Repository Open Access
Robin Lamarche-Perrin, Yves Demazeau and Jean-Marc Vincent

A generic algorithmic framework to solve special versions of the set partitioning problem

In: 2014 IEEE 26th International Conference on Tools with Artificial Intelligence : ICTAI 2014, 10-12 November, Limassol, Cyprus, ; proceedings
Washington, DC [u.a.] : CPS, 2014. - pp. 891-897