Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
105/2014

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

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

Abstract

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.

Received:
Oct 6, 2014
Published:
Oct 9, 2014
Keywords:
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

inBook
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