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

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

Contact the author: Please use for correspondence this email.
Submission date: 06. Oct. 2014 (revised version: October 2014)
Pages: 43
published 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. - P. 891 - 897 
DOI number (of the published article): 10.1109/ICTAI.2014.136
Bibtex
Keywords and phrases: Combinatorial Optimization, Set Partitioning Problem, Structural and Semantical Constraints, Algebraic Structure of Partition Lattices, Dynamic Programming, Specialized Optimization Algorithms, Artificial Intelligence, Operational Research
Download full preprint: PDF (530 kB)

Abstract:
Given a set of individuals, a collection of admissible subsets, and a cost associated to each of these subsets, the 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 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 Hierarchical SPP and the Ordered SPP, thus opening a unified approach to solve versions that might arise in the future.