Robin Lamarche-Perrin
email: robin.lamarche-perrin@mis.mpg.de

Yves Demazeau
email: yves.demazeau@imag.fr

Jean-Marc Vincent
email: jean-marc.vincent@imag.fr

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

Keywords: Combinatorial Optimization, Set Partitioning Problem, Structural and Semantical Constraints, Algebraic Structure of Partition Lattices, Dynamic Programming, Specialized Optimization Algorithms, Artificial Intelligence, Operational Research

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 enoughthey 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

Introduction

The Set Partitioning Problem (SPP) is a deeply-studied combinatorial optimization problem that naturally arises as soon as one wants to organize a set of objets into covering and pairwise disjoint subsets such that an additive objective is optimized. Within this setting, the population designates the finite set of individuals that needs to be partitioned. The set of admissible parts is the collection of nonempty subsets of the population that can be used to do so. It fully determines the set of admissible partitions, that is the set of all partitions of the population that can be built from these admissible parts, thus constituting the search space of the SPP. Finally, the cost function, associating a real value to each admissible part, is the objective that one wants to minimize. It is additively extended to the search space by associating to each partition the sum of the costs of its parts. For further details, the SPP will be fully formalized in Subsection 3.1.

This optimization problem has been used to model a colossal amount of problems in the neighboring fields of Artificial Intelligence and Operational Research. In each of these applications, the admissibility constraints are used to express the structural or semantic properties of the population that needs to be partitioned. This is for example the case in algorithmic game theory for coalition structure generation [START_REF] Bachrach | Optimal Coalition Structure Generation in Cooperative Graph Games[END_REF][START_REF] Bachrach | Cooperative Weakest Link Games[END_REF][START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]. A population of self-motivated agents must be partitioned into coalitions that optimally exploit the interagent synergies to achieve a given task. Because of compatibility constraints and the agent spatiotemporal locations, all coalitions are not necessarily feasible in practice. The set of admissible parts allows to express which coalitions can be actually considered to organize the agents depending on the system's structures and functions. Moreover, because of communication costs and (dys)synergies, some coalitions might be more effective than the others to perform the task. The cost function then expresses the social welfare of admissible coalitions. For another example, in data analysis, multilevel aggregation consists in partitioning a set of data points into homogeneous classes. In order to be meaningfully interpreted by the analyst, the classes often need to preserve the system's semantic or topological structure, expressed by the set of admissible parts [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF]. In this context, the cost function is usually defined according to a compression rate that should be maximized, leading to numerous applications such as time series analysis [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF], database optimization and image processing [START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF], multilevel community detection [START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF], performance analysis of distributed systems [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF], resource and task allocations for multiagent systems [START_REF] Sandholm | BOB: Improved winner determination in combinatorial auctions and generalizations[END_REF]. Subsection 2.1 will present in further details the whole range of application of the SPP.

The SPP is NP-complete in the general case [START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF]. This still holds when all admissible parts have the same cost [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF], when they do not contain more than three individuals [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF], when every individual is contained in exactly two admissible parts [START_REF] Lehmann | The Winner Determination Problem[END_REF], or when admissible partitions consist in exactly two admissible parts [START_REF] Anily | Structured Partitioning Problems[END_REF]. Hence, even with these very restrictive additional constraints, one cannot hope for a general-purpose algorithm that can efficiently solve every instance of the SPP. Among the strategies that have been proposed to tackle this computational challenge (see Subsection 2.2), this paper is interested in approaches that consider global constraints regarding the set of admissible parts in order to reduce and structure the search space. Such constraints, arising from global (semantic, structural, functional, or topological) properties of the modeled population, thus define tractable special versions of the SPP. For example, in data aggregation, the dataset's topological properties may allow to define a class of search spaces that are meaningful for the domain expert: e.g., assuming that admissible parts are intervals in the case of time series analysis [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF], that they form a hierarchy in the case of spatial analysis of nested structures [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF], or that they are rectangular tiles in the case of image processing, where the two-dimensional structure of the dataset implies very strong constraints for compression [START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF]. In this paper, we thus assume that the expert provides such global constraints to reduce the SPP computational complexity and provide tractable optimization algorithms.

Although many such special versions of the SPP have been addressed in the past (see Section 3), there is a major lack of unity regarding the identification, the formalization, and the resolution of these however strongly-related problems. Many of the articles herein referenced deal with special versions of the SPP with domain specific objectives and do not benefit from the research that have been extensively done by the combinatorial optimization community. Consequently, some results have been proven several times by independent work, such as the Ordered Set Partitioning Problem (see Subsection 3.4) that has been solved in quadratic time at least five times in 30 years [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF][START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Vidal | Optimal Partition of an Interval -The Discrete Version[END_REF]. Rothkopf et al. have addressed several versions of the SPP in an integrating work [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF], leading to deep results regarding their tractability in a unified applicative context, but without proposing any unified algorithmic framework to solve them. Some other work characterized the tractability of special versions of the SPP by identifying general algebraic prop-erties of the corresponding sets of admissible parts [START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF][START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF][START_REF] Nisan | Bidding and Allocation in Combinatorial Auctions[END_REF]. However, such models are often too general, and thus too weak in practice (meaning that more specific combinatorial algorithms might perform better on a special version than these general models) or, in some cases, they do not provide any practical algorithm [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF]. In order to fill the gap, this paper proposes to look more carefully at some particular classes of admissibility constraints and at the combinatorial algorithms that optimally exploit their algebraic structure. Then, we propose a generic algorithmic framework that can be applied to any special version of the SPP in order to design a specialized optimization algorithm.

This paper is organized as follows. Section 2 presents in further details the broad range of applications and methods of the SPP. Section 3 identifies several special versions that have been addressed in the past, along with the specialized algorithm that have been proposed. Section 4 presents our generic algorithmic framework that can be used to design such specialized algorithms. It relies on a proper understanding of the search space's algebraic properties and on dynamic programming to efficiently exploit them. Section 5 applies this framework to two special versions of the SPP, namely the Hierarchical Set Partitioning Problem (HSPP) and the Ordered Set Partitioning Problem (OSPP). We show that the computational complexity of the resulting optimization algorithms meets the one of past algorithms dedicated to the same problems [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Vidal | Optimal Partition of an Interval -The Discrete Version[END_REF], thus opening a unified approach to solve new versions of the SPP that might arise in the future. Section 6 discusses the limitation and possible generalizations of our framework when the admissibility constraints and the cost function are defined "at the partition level". Lastly, Section 7 summarizes the results and gives some research perspectives.

Related Work

This section introduces to related work regarding the SPP in two steps. Subsection 2.1 presents some major applications in Operational Research and in Artificial Intelligence. Subsection 2.2 then identifies three main categories of approaches that aim at solving the SPP. It also justifies the positioning of this paper regarding the third approach, detailed in Section 3. Table 2 provides a double entry summary of the articles making the connexion between the presented applications and approaches.

Applying the SPP

Relation to Other Combinatorial Optimization Problems

The prolific applicability of the SPP is partly explained by its closeness to the extensively-studied Set Packing (SP) and Set Covering (SC) problems [START_REF] Balas | Set Partitioning: A Survey[END_REF], respectively corresponding to the relaxation of the "covering" and the "pairwise disjoint" constraints regarding the concept of admissible partitioning. The SPP also generalizes numerous combinatorial optimization problems, in particular in computational graph theory where individuals are vertices of a graph and admissible parts are defined according to a specific subgraph structure: e.g., graph coloring, graph partitioning, domatic partitioning, weighted multiway cut, minimum set cover, partition into Hamiltonian subgraphs, forests, or perfect matching [START_REF] Björklund | Set Partitioning via Inclusion-Exclusion[END_REF][START_REF] Chekuri | Approximation Algorithms for Submodular Multiway Partition[END_REF][START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF], thus leading to a tremendous amount of other possible applications. However, since this paper focuses on applications where cost functions and sets of admissible parts are provided by expert knowledge regarding the analyzed population and its semantical or structural properties, this subsection only presents in further details applications in specialized fields of Artificial Intelligence and Operational Research.

The airline crew scheduling problem and other operational problems

Historically, the best-known application of the SPP in Operational Research is the airline crew scheduling problem [START_REF] Arabeyre | The Airline Crew Scheduling Problem: A Survey[END_REF][START_REF] Balas | Set Partitioning: A Survey[END_REF]: given a set of flight legs (individuals), a set of sequences of legs that are feasible by airline crews according to work policies (admissible parts), and a cost associated to each feasible sequence, the airline company would like to find a collection of feasible sequences minimizing the total cost such that each flight leg is covered by exactly one crew. This setting is easily generalizable to a broader class of transportation, delivery, routing, and location problems [START_REF] Balas | Set Partitioning: A Survey[END_REF][START_REF] Boschetti | A dual ascent procedure for the set partitioning problem[END_REF][START_REF] Hoffman | Set Covering, Packing and Partitioning Problems[END_REF][START_REF] Hoffman | Integer and Combinatorial Optimization[END_REF], and to other well-known operational problems such as the circuit partitioning problem, where a set of electronic components should be divided into clusters such that the number of intercluster connections is minimized [START_REF] Alpert | Recent developments in netlist partitioning: a survey[END_REF][START_REF] Chekuri | Approximation Algorithms for Submodular Multiway Partition[END_REF], or the political districting problem, where regions must be divided into voting districts such that every citizen is assigned to exactly one district [START_REF] Balas | Set Partitioning: A Survey[END_REF][START_REF] Hoffman | Set Covering, Packing and Partitioning Problems[END_REF]. Many other examples of such applications can be found in more exhaustive surveys: e.g., stock cutting, line and capacity balancing, facility location, capital investment, switching current design, marketing [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Balas | Set Partitioning: A Survey[END_REF].

The winner determination problem in combinatorial auctions

Given a set of assets (individuals) and a set of bids associating a price to groups of asset (admissible parts), the auctioneer wants to find an allocation of the assets to the bidders that maximizes her revenue [START_REF] Lehmann | The Winner Determination Problem[END_REF][START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF][START_REF] Nisan | Bidding and Allocation in Combinatorial Auctions[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF][START_REF] Sandholm | BOB: Improved winner determination in combinatorial auctions and generalizations[END_REF]. Due to the fact that several bidders may give a price to the same collection of assets, the winner determination problem is strictly-speaking more general than the SPP. However, Rothkopf et al. [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF] have shown that, when considering the classical OR bidding language1 to express the bidder objectives, the winner determination problem is equivalent to the Set Packing problem [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. Moreover, since the bids are always positive, and by interpreting the absence of bid on single assets as null prices [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF], there is always an optimal packing that is also an optimal partition. Hence, in this context, the winner determination problem is equivalent to the SPP.

The coalition structure generation problem in algorithmic game theory

A population of self-motivated agents (individuals) must collaborate with one another to perform a given task. Coalition structure generation consists in partitioning the agents into feasible teams (admissible parts) so as to achieve better result by maximizing the social welfare (expressed by the cost function) [START_REF] Bachrach | Optimal Coalition Structure Generation in Cooperative Graph Games[END_REF][START_REF] Bachrach | Cooperative Weakest Link Games[END_REF][START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]. This field itself leads to many applications in e-commerce (buyers form coalitions to purchase a product in bulk and take advantage of price discounts), e-business (groups form to satisfy particular market niches), distributed sensor network (sensors work together to track targets), distributed vehicle routing (coalition of delivery companies to reduce transportation costs), and information gathering (servers form coalitions to answer queries) [START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF].

The clustering problem for multilevel data analysis

The SPP can also be seen as a general formulation of the classical clustering problem: data points have to be partitioned into classes such that the intra-class similarity and/or the inter-class dissimilarity are maximized [START_REF] Björklund | Set Partitioning via Inclusion-Exclusion[END_REF][START_REF] Brucker | On the Complexity of Clustering Problems[END_REF][START_REF] Pintér | Set partition by globally optimized cluster seed points[END_REF]. Finding the optimal partition thus arises as soon as one wants to organize, to classify, or to abstract data. In this context, the SPP also relates to data aggregation problems, where data points are partitioned into homogeneous classes preserving the system's structure and optimizing a given compression rate, leading to applications in time series analysis [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF], spacial analysis [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF], multilevel community detection [START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF], database optimization, and image processing [START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF].

Solving the SPP

The SPP is usually tackled by one of the following strategies or by mixing several of them in a portfolio approach (for more detailed surveys regarding optimization algorithms for the SPP over the last forty years, see [START_REF] Balas | Set Partitioning: A Survey[END_REF][START_REF] Bilal | A New Formulation of the Set Covering Problem for Metaheuristic Approaches[END_REF][START_REF] Boschetti | A dual ascent procedure for the set partitioning problem[END_REF][START_REF] Chu | Constraint Handling in Genetic Algorithms: The Set Partitioning Problem[END_REF][START_REF] Hoffman | Set Covering, Packing and Partitioning Problems[END_REF][START_REF] Hoffman | Integer and Combinatorial Optimization[END_REF]).

Exploiting the Algebraic Structure of the General SPP

The set of parts and the set of partitions have several useful algebraic properties when one tries to directly tackle the general problem by going through the whole search space of admissible partitions. Strategies formalizing and exploiting such properties to efficiently run through the search space are usually based on integer programming [START_REF] Balas | Set Partitioning: A Survey[END_REF][START_REF] Eisenbrand | Set Covering with Ordered Replacement: Additive and Multiplicative Gaps[END_REF][START_REF] Hoffman | Set Covering, Packing and Partitioning Problems[END_REF][START_REF] Hoffman | Integer and Combinatorial Optimization[END_REF], dynamic programming [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF][START_REF] Yeh | A Dynamic Programming Approach to the Complete Set Partitioning Problem[END_REF], exhaustive enumeration [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF], implicit enumeration [START_REF] Balas | Set Partitioning: A Survey[END_REF][START_REF] Dom | Set Cover with Almost Consecutive Ones[END_REF][START_REF] Hoffman | Integer and Combinatorial Optimization[END_REF][START_REF] Mecke | Solving Geometric Covering Problems by Data Reduction[END_REF], and/or automatic reformulation of the linear description [START_REF] Hoffman | Integer and Combinatorial Optimization[END_REF][START_REF] Ruf | Set covering with almost consecutive ones property[END_REF][START_REF] Schöbel | Set covering problems with consecutive ones property[END_REF]. Again, since the SPP is NP-complete, one should not expect any worst-case polynomial algorithm to emerge from such strategies, unless P = NP.

Heuristics limiting the search space in some way have also been proposed to find suboptimal solutions in reasonable time, including genetic algorithms [START_REF] Chu | Constraint Handling in Genetic Algorithms: The Set Partitioning Problem[END_REF], dual ascent [START_REF] Boschetti | A dual ascent procedure for the set partitioning problem[END_REF], simulated annealing, and neural networks [START_REF] Hoffman | Set Covering, Packing and Partitioning Problems[END_REF], and other metaheuristic algorithms [START_REF] Bilal | A New Formulation of the Set Covering Problem for Metaheuristic Approaches[END_REF]. However, such approaches do not provide any worstcase guarantee regarding the closeness to optimality [START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF]. On the contrary, approximation algorithms provide provable solution quality and run-time bounds [START_REF] Bachrach | Optimal Coalition Structure Generation in Cooperative Graph Games[END_REF][START_REF] Bachrach | Cooperative Weakest Link Games[END_REF][START_REF] Björklund | Set Partitioning via Inclusion-Exclusion[END_REF][START_REF] Chekuri | Approximation Algorithms for Submodular Multiway Partition[END_REF][START_REF] Lehmann | The Winner Determination Problem[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF], but are still limited by severe inapproximability results [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF] and the absence of any polynomial-time approximation scheme [START_REF] Lehmann | The Winner Determination Problem[END_REF].

Exploiting Properties of the Cost Function

Much work has focused on special versions of the SPP by making additional assumptions regarding the cost function. For example, the SPP has been proved to be polynomially solvable when costs are defined by some aggregative measures (e.g., max-sum, min-sum, sum-max, sum-avg) applied to the attributes of the individuals [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF]. More constrained settings have been studied, such as aggregative measures applied to the edges of a weighted graph expressing the synergies, dissimilarities, communication costs, or interests in grouping couples of individuals [START_REF] Bachrach | Optimal Coalition Structure Generation in Cooperative Graph Games[END_REF][START_REF] Bachrach | Cooperative Weakest Link Games[END_REF][START_REF] Brucker | On the Complexity of Clustering Problems[END_REF][START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF][START_REF] Pintér | Set partition by globally optimized cluster seed points[END_REF]. However, in each of these cases, the considered cost function requires a dedicated treatment that can hardly be generalized to a broader context.

Other work has hence focused on more general properties of the cost function such as concavity [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF], symmetry [START_REF] Chekuri | Approximation Algorithms for Submodular Multiway Partition[END_REF], submodularity [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Chekuri | Approximation Algorithms for Submodular Multiway Partition[END_REF][START_REF] Lehmann | The Winner Determination Problem[END_REF][START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF][START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF], superadditivity [START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF], subadditivity [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF], and additivity with convex discounts [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF]. These approaches all assume that the costs are somehow monotonously defined with respect to the set inclusion. For example, superadditivity in coalition games implies that the synergies between agents cannot decrease when new agents join a coalition. Hence, applying additional cuts will never degrade the quality of a partitioning, and one usually search for a partition of a given fixed size that optimizes the superadditive cost function [START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF]. Subadditivity implies, on the contrary, that the agents are usually best of by operating alone. Although considerable results have been achieved for such settings, Sandholm et al. [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF] argue that, when some cost penalizes the coalition formation process itself (because of communication or anti-trust penalties), many applications of the coalition generation problem are neither superadditive nor subadditive. This is also the case in multilevel data analysis, where the information-theoretic measures are usually non-monotonous regarding the set inclusion, meaning that data points might be relatively homogeneous at some level, but heterogeneous at lower or higher levels [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF][START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF].

Exploiting Structures of the Admissible Parts

This paper focuses on a third category of strategies exploiting global constraints on the set of admissible parts to define easier versions of the SPP. Indeed, by assuming that admissible parts belong to a restraint and structured portion of the population power set, one can reduce the search space and thus provide tractable optimization algorithms. In this case, one should guarantee that the constraints do not exclude solutions that would be optimal otherwise. For example, in the winner determination problem, if the assets are known to be more valuable in given combinations, the auctioneer may anticipate the bids of greatest economic significance and only allow such valuable combinations. For example, in the presence of a topological structure, groups of neighboring assets may be more valuable than random groups [START_REF] Lehmann | The Winner Determination Problem[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. The auctioneer thus assumes that no bidder will prefer forbidden combinations during the auction process. Reducing the search space thus consists in "introducing patterns that have a meaningful auction interpretation" [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF]. However, constraints might also arise from semantics considerations when some subsets are not meaningful for the partition purposes. In data aggregation, for example, the partitioning should be consistent with the dataset's structural and topological properties so that the compressed data is usable by the domain expert [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF]. In particularly, in image processing, the two-dimensional structure implies very strong constraints for compression [START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF]. Some work has also been dedicated to the characterization of tractability by studying general algebraic properties of the sets of admissible parts. For example, it has been shown that, if the coefficient matrix of the corresponding integer programming problem is totally unimodular, then the linear relaxation of the SPP has an integral optimal solution [START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF][START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF][START_REF] Nisan | Bidding and Allocation in Combinatorial Auctions[END_REF]. In this case, a linear programming solver provides an optimal solution in polynomial time (see for example the column generator algorithm proposed in [START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF]). Another characterization of tractability is based on the concept of maximal cliques of perfect graphs: if the intersection graph of admissible parts is perfect and if all maximal cliques in this graph are induced by the population individuals, then a maximum weighted stable set can be computed in polynomial time [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF]. However, such models of tractability might be too general, and thus too weak in practice. Even if they allow to show that some special versions of the SPP can be solved in polynomial type, they do not imply that linear programming solvers will provide the best possible algorithm. Indeed, in the presence of more specific combinatorial structures, dedicated algorithms might perform better by exploiting the structure more precisely than the general models [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF]. Moreover, it has been argued that in some cases such models do not provide any practical algorithm [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF].

In order to overcome these limitations, this paper proposes to look more carefully at some particular classes of admissibility constraints to derive specialized combinatorial algorithms that optimally exploit such structures. In Section 4, we thus propose a generic framework based on dynamic programming to provide such optimal algorithms. Note that other mixed strategies have been proposed, such as assuming global admissibility constraints to design specialized approximation algorithms (2.2.1) [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF], or by making assumptions regarding the set of admissible parts and the cost function (2.2.2) to design optimal algorithms [START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF]. On the contrary, the framework proposed in this paper both allows to design optimal algorithms and to stay fully general regarding the optimized cost function.

The General SPP and Some Special Versions

This section formalizes the general SPP (3.1) and presents some special versions that have been addressed in previous work (3.2, 3.3, 3.4, 3.5, and 3.6). For each version, we identify applications in Artificial Intelligence and Operational Research by indicating possible semantical and structural interpretations of global admissibility constraints. The third part of Table 2 summarizes the links between the applications and these special versions. We also identify algorithms that have been proposed in previous work to optimally solve these versions (see Table 1).

The General Set Partitioning Problem (SPP)

Preliminary Notations. This paper uses a consistent system of letter cases to properly formalize the SPP and its search space:

• individuals are designated by lowercase letters: x, y, z;

• sets of individuals and parts by uppercase letters: Ω, X, Y , Z;

• sets of parts and partitions by calligraphic letters: P, X , Y, Z; • sets of partitions by Gothic letters. For example: P, R, and C.

A population Ω tx 1 , . . . , x n u is a finite set of individuals and a part is a nonempty subset X Ω. A set of admissible parts P tX 1 , . . . , X m u is a subset of the power set 2 Ω . The size of a population or a part, resp. marked |Ω| and |X|, is the number of individuals it contains. An admissible partition X tX 1 , . . . , X k u P is a set of covering and pairwise disjoint admissible parts: X i P, i X i Ω and X i X j r. The set of admissible partitions P is the set of all partitions that can be generated from the set of admissible parts:

P tX P z X is a partition of Ωu.
We assume that P is such that P $ r, so that the SPP is indeed an optimization problem, and not an existence problem. This is for example the case when the population is admissible, so that the maximal partition is admissible: Ω P ñ tΩu P, or when all singletons are admissibles, so that the minimal partition is admissible: dx Ω, txu P ñ ttxuu xΩ P.

The size of a partition, marked |X|, is the number of parts it contains. A cost function c is an application that associates to each admissible part X P a real value cpXq R. We also define the additive extension of the cost function c on the set of admissible partitions: dX P, cpX q °XX cpXq. Lastly, we mark P ¦ P the set of admissible partitions that minimizes c.

The Set Partitioning Problem. Given a population Ω, a set of admissible parts P, and a cost function c, the weighted Set Partition Problem (SPP) with an additive objective consists in finding a subset X ¦ P that partitions Ω and minimizes c:

X ¦ arg min X P cpX q.
(1)

Tractability of the SPP and its Special Versions. With no further assumption regarding the cost function and the set of admissible parts, the SPP is NPcomplet [START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF]. However, the rest of this section presents special versions of the problem where global admissibility constraints allow to define tractable algorithms.

In the following, we thus indicate the worst-case time complexity of optimization algorithms proposed by previous work according to the size |Ω| n of the population. The algorithmic complexity is thus given relatively to the problem size and we consider a special version tractable if there exists an algorithm that optimally solves any instance of this special version by requiring a number operations that is polynomially bounded in the size of the population. Note however that the input size of the problem is actually the number of admissible parts |P| m. Indeed, the encoding length of any instance of the SPP is in general the number of cost values that have to be specified. In that case, the SPP can easily become intractable because the feeding of the input is itself intractable [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. However, in many work, the costs of admissible parts are actually derived from attributes of the individuals [START_REF] Arabeyre | The Airline Crew Scheduling Problem: A Survey[END_REF][START_REF] Becker | Max-Min Partitioning of Grid Graphs into Connected Components[END_REF][START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF][START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF] or from relations between individuals [START_REF] Bachrach | Optimal Coalition Structure Generation in Cooperative Graph Games[END_REF][START_REF] Bachrach | Cooperative Weakest Link Games[END_REF][START_REF] Becker | Max-Min Partitioning of Grid Graphs into Connected Components[END_REF][START_REF] Brucker | On the Complexity of Clustering Problems[END_REF][START_REF] Pintér | Set partition by globally optimized cluster seed points[END_REF]. This is the case for example in multilevel data analysis when the cost of admissible parts are computed in linear time from the individual attributes according to some information-theoretic measure [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF]. In such cases, the size of the input thus linearly depends on the number of individual, and not on the number of admissible parts. Hence, most of the special versions presented hereafter are linearly solvable with respect to the input size |P| m, but polynomially solvable with respect to the problem size |Ω| n (see Table 1 for a detailed list of the input sizes of the following problems).

The Complete Set Partitioning Problem (CSPP)

The Complete Set Partitioning Problem arises when all subsets of the population are admissible, i.e., when the set of admissible parts is the population's power set: P 2 Ω .

Applications. The CSPP has been extensively used to model coalition structure generation problems assuming that every possible group of agents is an adequate candidate to constitute a coalition [START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]. It has also been applied to corporate tax structuring to find an optimal aggregation of corporate subsidiaries to pay state unemployment compensation tax [START_REF] Yeh | A Dynamic Programming Approach to the Complete Set Partitioning Problem[END_REF].

Combinatorics. Sandholm et al. [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF] have shown that the number of admissible partitions grows considerably faster than the number of admissible parts:

|P| Θp2 n q and |P| ωpn n{2 q.

Algorithmic Results. The CSPP is NP-complete [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]. However, exponential algorithms have been provided to solve small instances of the CSPP: a Op2 n n{2 q enumeration approach [START_REF] Lin | An Efficient Algorithm for the Complete Set Partitioning Problem[END_REF], a Op3 n q dynamic programming algorithm [START_REF] Lehmann | The Winner Determination Problem[END_REF][START_REF] Yeh | A Dynamic Programming Approach to the Complete Set Partitioning Problem[END_REF], and a Opn n q anytime algorithm that quickly generates a suboptimal solution with bound guarantees, then slowly improves this solution by establishing better bounds [START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]. Note that, since any instance of the SPP can be modeled as an instance of the CSPP with infinite cost on non-admissible parts, these algorithms can also be exploited to solve instances of the general problem. However, as it is shown in what follows, when assuming stronger admissibility constraints, more efficient algorithms can be designed.

The Hierarchical Set Partitioning Problem (HSPP)

The Hierarchical Set Partitioning Problem arises when the set of admissible parts is a hierarchy, i.e., when every two admissible parts are either disjoint or one is included in the other:

dpX 1 , X 2 q P 2 , X 1 X 2 r or X 1 X 2 or X 1 X 2 .
If one also assumes that the population and the singletons are admissible: Ω P and dx Ω, txu P, then the hierarchy can be described as a rooted tree2 where the leaves represent the singletons, the nodes represent the admissible parts the root represents the whole population, and the treeorder is the subset relation (see Fig. 1).

Applications. The HSPP has been mainly applied in data aggregation to model systems with multilevel nested structures. This include community representation of networks (individuals are nodes of a graph representing a social structure and admissible parts are highly-connected groups of nodes resulting from a hierarchical community detection algorithm) [START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF], aggregation of geographical data for geographical analysis (individuals are territorial units and admissible parts are defined according to nested geographical partitions of the world into regions, countries, subcontinents, continents, etc.) [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF], and analysis of distributed systems for performance analysis (individuals are the computational resources of a distributed system and admissible parts are defined according to the system's hierarchical communication network: processes, machines, clusters, sites, etc.) [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF].

Combinatorics. For a population of size n, the minimal number of admissible parts is n 1 (singletons and population) and the maximum number is reached for a hierarchy corresponding to a complete binary tree. Thus, |P| Opnq. The number of admissible partitions however depends on the number of levels and branches in the hierarchy. Since an admissible partition of X P is either the maximal partition tXu or the union of admissible partitions of subparts of X, this number can be recursively defined as |PpXq| 1 ± Y X |PpY q|, where pXq is the set of children of X in the tree representing the hierarchy. For a complete binary tree, at each level, the number of admissible partitions is squared. Assuming that n 2 k , where k is the depth of the tree, we thus have |P| U k 1 pU k¡1 q 2 with U 0 1. The sequence pU k q kN is asymptotically bounded by an exponential function α n , with α 1.226 [START_REF] Cloitre | Sequence A003095[END_REF]. Similar results are found for complete ternary trees (with α 1.084 [START_REF] Mcgarvey | Sequence A135361[END_REF]), complete quaternary trees, and so on. Henceforth, for any bounded number of children per node, the number of admissible partitions exponentially grows with the population size.

Results. All algorithms that have been proposed to solve the HSPP consist in a Opnq depth-first search of the tree representing the hierarchy [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF]. A Opn|P|q dynamic algorithm has also been proposed [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF].

h i e r a r c h y h i e r a r c h y h i e r a r c h y The Ordered Set Partitioning Problem arises when a total order is defined on Ω and when the admissible parts are the intervals induced by this order:

P ttx i . . . x j u Ω z i ¤ ju.
This set can be represented as a "pyramid of intervals" (see Fig. 2) and the resulting admissible partitions are sometimes called consecutive partitions [START_REF] Anily | Structured Partitioning Problems[END_REF].

Applications. The OSPP very naturally applies to model any population that has a temporal component (e.g., sets of dates, events, or time periods are naturally or-dered by the "arrow of time"). For example, the OSPP has been addressed for the aggregation of time series [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF] (individuals are time periods and admissible parts are consecutive sequences of such periods) and for the allocation of consecutive processing time to different tasks [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF]. This setting might also receive a unidimensional-space interpretation, such as the North-South geographical ordering of the cities on the East Coast or the mineral rights on tracks forming a single swath of offshore state waters [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. It has also been applied to inventory control and production planing [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF][START_REF] Vidal | Optimal Partition of an Interval -The Discrete Version[END_REF].

Combinatorics. The number of intervals of an ordered population of size n is npn 1q 2

. An admissible partition of size k consists in cutting the population in k ¡1

places. Hence, the number of partitions of size k is n¡1 k¡1 ¨and the total number of partitions is:

|P| °n¡1 k0 n¡1 k ¨ 2 n¡1 .
Results. Chakravarty et al. [START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF] have shown that, when the optimal partition is a sequence of intervals, solving the SPP is equivalent to solving the shortest path problem, resulting in a Opn 2 q optimization algorithm. A Opn 2 q dynamic programming algorithm has also been proposed in independent work [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Vidal | Optimal Partition of an Interval -The Discrete Version[END_REF].

Extensions. Some other order-related structures have been addressed, such as monotone partitions (when the size of intervals increases with the order) [START_REF] Anily | Structured Partitioning Problems[END_REF], extremal partitions (the last individual of each interval can be associated to the next interval without losing optimality) [START_REF] Anily | Structured Partitioning Problems[END_REF], and cyclic orders defining intervals on a circle and leading to a Opn 3 q dynamic algorithm [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF].

The Array Partitioning Problem (APP)

The Array Partitioning Problem consists in partitioning a two-dimensional array into rectangular tiles. It naturally arises when one considers the Cartesian product Ω 1 ¢ Ω 2 of two ordered populations. In that sense, we write APP = OSPP ¢ OSPP. The set of admissible parts is then P tX Ω 1 ¢Ω 2 z hX 1 P 1 , hX 2 P 2 , X X 1 ¢ X 2 u, where P 1 and P 2 are respectively the sets of intervals of Ω 1 and Ω 2 (see the OSPP above).

Applications. As for the OSPP, the APP may be used to model spatial structures such as the rectangular partitioning of geographic locations on a two-dimensional grid [START_REF] Becker | Max-Min Partitioning of Grid Graphs into Connected Components[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. This includes the distribution of individual units of a manufacturing plant among supervisors, the balanced subdivision of a rectangular mining area among mining companies [START_REF] Becker | Max-Min Partitioning of Grid Graphs into Connected Components[END_REF], the clustering of points with fairly uniform color or similar frequencies in image processing, computer graphics, and video compression [START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF], the building of histograms based on rectangular regions to approximate multi-dimensional data distributions in database systems [START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF]. Moreover, the APP has been used to model load balancing problems in parallel computation when the computational space corresponds to a matrix. In this case, the tiles are rectangular in order to respect the computation space topology [START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF] and to reduce the communication costs between subproblems that is proportional to the number of adjacent pairs in the grid [START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF].

Combinatorics. Given the Cartesian product Ω 1 ¢ Ω 2 of a population of size n 1 and a population of size n 2 , the number of rectangular tiles is

|P| |P 1 | ¢ |P 2 | Θpn 2 1 n 2 2 q.
To get a lower bound estimate of |P|, we recall that the number of interval partitions of Ω 1 is 2 n 1 ¡1 (see combinatorics of OSPP above). Thus, by only considering "stacks" of n 2 partitions of Ω 1 , the total number of admissible partitions of the APP is necessarily greater than 2 pn 1 ¡1qn 2 .

Results. Rothkopf et al. [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF] have shown that the APP is NP-complet even if one only considers singletons and 2¢2 rectangles as admissible parts. To the best of our knowledge, no optimal algorithm has yet been proposed.

Extensions. The APP is manageable if one only considers rows, columns, and singletons, for example to represent assets that have two different properties of interest for a collector, as the year and denomination of a coin [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. Other multidimensional versions of the SPP has been addressed, such as the partition of ddimensional hypercubes [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF] or the Cartesian product of a hierarchy and a total order (HSPP ¢ OSPP), leading to a Opn 1 pn 2 q 3 q dynamic algorithm [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF], where n 1 and n 2 are respectively the sizes of the hierarchical and the ordered populations.

Bounds on the Size of Admissible Parts

Some versions of the SPP assume that the size of admissible parts is bounded:

P tX Ω z |X| ¤ ku or P tX Ω z |X| 1 or |X| ¡ n{ku for a given k N.
Applications. Such assumptions are very generic and might apply to any problem bringing in only small groups (or only large groups) of individuals. It has been proposed for example to model slot auctions of airline take-off and landing [START_REF] Müller | Tractable Cases of the Winner Determination Problem[END_REF].

Results. Rothkopf et al. [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF] have shown that, when admissible parts are limited to size k 3, the SPP is still NP-complete, when limited to size k 2, solving the SPP is equivalent to solving the maximum-weight matching problem, leading to a Opn 3 q optimization algorithm, and when only large parts and singletons are admissible, the SPP can be solved in Opn|P| k q time.

|P| |P|

Best Known Algorithm CSPP (3.2)

Θp2 n q ωpn n{2 q NP-complet HSPP (3.3) Binary Tree Θpnq Θpα n q Opnq [28, 43] OSPP (3.4)

Total Order

Θpn 2 q Θp2 n q Opn 2 q [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF] Cyclic Order

Θpn 2 q Θp2 n q Opn 3 q [46] APP (3.5) OSPP ¢ OSPP Θpn 2 1 n 2 2 q Ωp2 n1n2 q NP-complet HSPP ¢ OSPP Θpn 1 n 2 2 q Ωp2 n1n2 q Opn 1 n 3 2 q [20]
Rows & Columns 4 A Generic Algorithmic Framework to Solve Special Versions of the SPP

Θpn 1 n 2 q Θp2 n1 2 n2 q Opn 1 n 2 q [46]
If dynamic programming has been used to solve the general SPP, leading to a Ωp2 n q and Op3 n q optimization algorithm [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF], we have shown in previous section that more efficient algorithms are possible when dealing with special versions of the problem. Dynamic programming has thus been used on many occasions to solve such tractable versions (see for example [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Yeh | A Dynamic Programming Approach to the Complete Set Partitioning Problem[END_REF]). However, these results are very independent from each other and no unified framework have been proposed for their generalization. To fill the gap, the framework proposed in this paper aims at being generic -in the sense that it can be applied to any special version of the SPP to derive a specialized algorithm -but not at being general -in the sense that it would not be efficient to deal with the general unstructured problem. Hence, this framework should be considered as an abstract tool to build optimization algorithms for tractable versions of the SPP. Section 5 gives two examples of such specialized implementations (for the HSPP and the OSPP).

The key principle regarding the application of dynamic programming to the SPP is the following: one needs to compute the optimal partition of an admissible part only once to evaluate all the partitions that are coarser than this part. This principle has been used to straightforwardly solve the general SPP [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF]. In this section, in order to also exploit the particular structure of special versions, we provide a better understanding of the search space that allows to identify and suppress numerous redundant computations when applying this key principle. The search space is first broken down into smaller covering subspaces. Then, thanks to a principle of optimality that fits with the algebraic structure of the partition set, these subproblems are recursively solved. Locally-optimal solutions are then compared to globally solve the initial problem.

The rest of this section is organized as follows. We first formalize the algebraic structure of the search space and we provide a corresponding principle of optimality (4.1). Then, we propose a decomposition of the search space based on this principle (4.2) and we derive a recursive algorithm (4.3). Finally, we propose two improvements based on memoization and non-redundant decomposition to fully exploit the algebraic structures of special versions (4.4). The final algorithm is given at the end of this section.

Algebraic Structure and Principle of Optimality

Rothkopf et al. have argued that the computational complexity of the SPP does not actually depend on the size of the search space, but rather on its structure [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF]. Indeed, as shown in Table 1, restricting the number of admissible parts |P| is not sufficient to restrict the size of the search space |P|. For example, in the case of the OSPP, we have |P| Θpn 2 q and |P| Θp2 n q. Since the number of admissible partitions grows exponentially with the population size in most of the special versions reported in Section 3, the introduction of strong constraints is often not sufficient to make a brute-force search algorithm tractable. Hence, in this subsection, we carefully examine the algebraic structure of the search space and we propose a principle of optimality that exploits this structure to evaluate partitions in a computationally-efficient fashion.

The Algebraic Structure of the Search Space

The set of admissible partitions P is structured by an essential algebraic relation, usually referred to as the refinement relation [START_REF] Davey | Introduction to Lattices and Order[END_REF]. A partition X refines a partition Y (X Y), if and only if each part in X is a subset of a part in Y:

X Y ô dX X , hY Y, X Y
As this binary relation is reflexive, antisymmetric, and transitive, it defines a partial order on the partition set P that consequently forms a poset and can be represented as a Hasse diagram [START_REF] Davey | Introduction to Lattices and Order[END_REF].

The covering relation is the transitive reduction of the refinement relation, that is the binary relation which holds between immediate "neighbors" regarding . Hence, a partition X is covered by a partition Y (X Y), if and only if X $ Y, X refines Y, and there is no other partition "between" them: X Y ô X Y and iZ P, X Z Y

As it is shown in the rest of this section, these two relations give essential algebraic tools to search for optimal partitions. For a given admissible partition X P, we define RpX q as the set of admissible partitions refining X , CpX q as the set of admissible partitions covered by X and, respectively, R ¦ pXq and C ¦ pXq as the sets of optimal partitions among RpX q and CpX q. Note that if the minimal partition ttxuu xΩ is admissible, it refines all admissible partitions: X P, ttxuu xΩ RpX q, and if the maximal partition tΩu is admissible, it is refined by all admissible partitions: RptΩuq P.

A Principle of Optimality for the SPP

In dynamic programming, finding a principle of optimality consists in showing that the search space has an optimal substructure: the solution to the optimization problem can be obtained by recursively combining locally-optimal solutions to several subproblems. Intuitively, in the case of the SPP, one can rely on the fact that the union of optimal partitions on subsets of the population is an interesting candidate to form an optimal partition of the whole population. Hence, by appropriately decomposing the population, one might provide a computationally efficient procedure to build such an optimal solution. Theorem 1. Let Ω be a population and c be an additive cost function defining partition optimality. For any partition Y of Ω, the union of locally-optimal partitions of the parts of Y is optimal among the refinements of Y:

dY Y, Y ¦ Y P ¦ pY q ñ £ ¤ Y Y Y ¦ Y R ¦ pYq (2)
Proof. The proof of this theorem is given in annexe.

Branching the Search Space

Given a admissible part X P for which one wants to compute a locally-optimal admissible partition X ¦ P ¦ pXq, a branching consists in building subspaces P 1 , . . . , P k that cover the search space: P 1 . . .P k PpXq. Then, if one finds locally-optimal partitions X ¦

1 P ¦ 1 , . . . , X ¦ k P ¦
k for each of these subspaces, one can easily solve the optimization problem the following way:

arg min X tX ¦ 1 ,...,X ¦ k u cpX q P ¦ pXq (3)
For that purpose, the covering relation indicates "atomic disaggregations" of a given part. For example, in the case of the OSPP, it consists in dividing the part into two intervals (see Fig. 3). The covering relation can thus be used to branch the search space. First, assuming that the maximal partition tXu is admissible 3 , we know that all admissible partitions of X refine the maximal partition tXu: PpXq RptXuq. Second, for any partition X PpXq, a refining partition of X is either the partition X itself, or a partition that refines a partition covered by X . Hence, the search space can be branched the following way:

PpXq ttXuu ¤ ¥ ¤ Y CptXuq RpYq (4)

A Recursive Algorithm

The computation of an optimal partition thus consists in computing locally-optimal partitions refining the partitions covered by the maximal partition. Thanks to the principle of optimality, such a computation can be recursively performed by recursively applying the algorithm on admissible parts (see Eq. 2 and Fig. 4). Hence, the three branching and recursion equations 2, 3, and 4 allow to define a divide and conquer algorithm that computes a locally-optimal partition X ¦ P ¦ pXq for any X P according to the following recursive formula:

arg min X ttXuu ¤ ¦ ¥ ¤ Y CptXuq 5 ¤ Y Y Y ¦ Y C
cpX q P ¦ pXq [START_REF] Bachrach | Cooperative Weakest Link Games[END_REF] where Y ¦ Y designates a partition in P ¦ pY q. Here are the steps of the resulting algorithm:

(step 1) Compute the set CptXuq of admissible partitions covered by the maximal partition tXu.

Dynamic Programming Improvements

This first algorithm is not computationally-optimal in terms of execution steps. In the rest of this subsection, we thus propose two improvements to reduce its time complexity. The fist one, simply consisting in the recording of intermediary results (see stars), is actually a key principle of dynamic programming [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF]. The second one, consisting in avoiding redundant evaluations in the execution tree (see crosses), is an entirely new feature derived from the algebraic analysis of the search space.

Recording Intermediary Results

According to the dynamic programming paradigm, recursive algorithms can be easily improved by recording the results of time-consuming recursive calls. For each part on which the algorithm is once applied, by keeping trace of the resulting locally-optimal partition, one can immediately return this result when posterior calls occur on the same part. This way, the algorithm is applied only once to each admissible part X P. For example, in Fig. 5, the algorithm is initially applied twice on parts 1 2 , 2 3 , and 3 4 . Thanks to this memoization procedure, one can avoid the second calls (see stars on dashed lines).

Avoiding Redundant Evaluations

The branching of the search space proposed in Eq. 4 is redundant, i.e., subspaces are not disjoints. For example, in Fig. 5, branches 2 and 3 allow the evaluation of partitions 1 2 3 4 and 1 2 3 4 , and branches 4 and 5 the evaluation of partitions 1 2 3 4 and 1 2 3 4 . Hence, 1 2 3 4 is evaluated twice and 5 is useless. In order to avoid such redundant branches, one can keep trace of the covered partitions X 1 , . . . , X k that have already been evaluated during step 2. When the algorithm is recursively applied to a part X X k 1 (step 2.a), one also retains the complementary partition X X k 1 ztXu. Hence, within the "lower" calls, when a covered partition Y CptXuq is considered for branching, one first checks if X Y does not refine any of the previously-evaluated partitions X 1 , . . . , X k . If it does (hi ¤ k, X Y RpX i q), one deduces that the branch has already been evaluated, and steps 2.a and 2.b may be avoided. Fig. 5 indicates the result of this improvement by crosses cutting the plain arrows.

Note however that this improvement should be implemented with the greatest care in order to be computationally efficient. In Section 5, where this generic algorithmic framework is applied to special versions of the SPP, the specific algebraic structures resulting from the covering relation are fully known. We then show how one can directly generate, during step 2, the covered partitions that have not been evaluated yet, without actually recording them into memory. This way, the avoidance of redundant evaluations does not require additional ressources.

The branching method and the two improvements directly lead to the following algorithm:

A Generic Algorithm to Solve the SPP Global Inputs: c a cost function; P a set of admissible parts defining admissible partitions; L a set of locally-optimal admissible partitions of parts on which the algorithm has already been applied.

Local Inputs: X an admissible part; X the complementary partition of X inherited from the "higher" call (X is a partition of ΩzX); D the set of admissible partitions which refinements have already been evaluated during "higher" calls.

Local Output:

X ¦ a locally-optimal admissible partition of X.

• If the algorithm has already been applied to part X, return the locally-optimal partition recorded in L.

• Initialization: X ¦ Ð ttXuu and D I Ð D.

• For each Y CptXuq such that X Y does not refine any partition in D, do the following:

-For each part Y Y, call the algorithm with local inputs X Ð Y , X Ð X YztY u, and D Ð D I to compute a locally-optimal partition Y ¦

Y P ¦ pY q. -Y ¦ Ð Y Y Y ¦ Y . -If cpY ¦ q ¡ cpX ¦ q, then X ¦ Ð Y ¦ . -D I Ð D I tYu.
• Return X ¦ and record this result in L.

From the Generic Framework to Specialized Implementations

The above algorithm can in theory be applied to any set of admissible parts P 2 Ω . In that sense, it provides a dynamic algorithm to solve the general SPP. However, a generic implementation would not be computationally-optimal for special versions of the SPP. Indeed, assuming that one explicitly knows the global structure of the partition set that is meant to be searched, one can adapt the algorithm and the data structures to the problem's specific algebraic structure.

That is what we call deriving a specialized implementation of the algorithm. For example, in the general case, there are 2 n possible admissible parts (where n is the size of Ω), so one needs at least n bits to identify one of them (e.g., a binary string of size n indicating which individuals are contained in the identified part).

In the case of the OSPP, the admissible parts are the 1 2 n pn ¡ 1q intervals of Ω, so one roughly needs 2 log n bits to identify one of them (e.g., two integers indicating the indexes of the interval extrema). This need for dedicated data structures also holds when representing admissible partitions, computing covered partitions, and avoiding redundant evaluations.

Hence, the generic algorithm should be used as a starting point to build specialized ones. This section makes the specialization process explicit for the HSPP and the OSPP by presenting, in both cases, the execution of the generic algorithm, the data structures used for the implementation, the pseudocode of the specialized algorithm, and the resulting computational complexity: linear in case of the HSPP and quadratic in case of the OSPP, thus meeting the results presented in Section 3. These two algorithms have been implemented in C++ within the visualization tool PajeNG for the spatial aggregation of execution traces of distributed computing systems [START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF] and within the Ocelotl module of the FrameSoC platform for the temporal aggregation of traces of embedded systems [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF][START_REF] Pagano | Trace Management and Analysis for Embedded Systems[END_REF]. Please refer to the GitHub repositories of Schnorr [START_REF] Schnorr | PajeNG -Trace Visualization Tool[END_REF] and Dosimont [START_REF] Dosimont | [END_REF] for more details regarding the implementation of the two specialized algorithms presented in this section.

Solving the HSPP

As it has been previously defined, the HSPP arises when the set of admissible parts P forms a hierarchy (see Subsection 3.3 for the formal definition). A Opnq optimal algorithm, based on a depth-first search of the tree representing the hierarchy, has been proposed in independent work [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF][START_REF] Lamarche-Perrin | Evaluating Trace Aggregation for Performance Visualization of Large Distributed Systems[END_REF][START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF]. We show in this subsection how this result can be recovered as a special case of our generic framework.

Execution of the Generic Algorithm. An example of execution of the generic algorithm in the case of a 3-levels hierarchy is presented in Fig 6 . For each admissible part X P, the corresponding maximal partition tXu covers only one admissible partition, that is the set of children of the node X in the tree representing the hierarchy: CpXq tY P z Y X, iZ P, Y Z Xu.

Hence, the branching of the search space proposed in Eq. 4 is not redundant: PpXq ttXuu RpCpXqq. The resulting algorithm is then a simple recursive procedure consisting in a depth-first search of the tree (see Fig. 6): a recursive execution on each Y CpXq (step 2.a), the building of the resulting locally-optimal partition Y CpXq Y ¦ Y (step 2.b), and the comparison of its cost with the one of the maximal partition tXu (step 3). The algorithm is naturally called only once per admissible part (no need for memoization, no stars on dashed lines in Fig. 6) and the branching of the partition set is never redundant (no crosses on plain arrows). h

i e r a r c h y h i e r a r c h y h i e r a r c h y h i e r a r c h y h i e r a r c h y h i e r a r c h y h i e r a r c h y h i e r a r c h y

Figure 6: Execution trace of the optimal partitioning algorithm in the case of a hierarchical population of size 9 (see Fig. 1). Plain numbered arrows represent branchings (step 2). Dashed arrows represent recursive calls (step 2.a).

Data Structures and Implementation. The hierarchy P is implemented by a tree data structure. Each node represents an admissible part X P and has three labels instantiated by the algorithm:

• cost stores the cost cpXq of the corresponding part;

• optimalCost stores the cost cpX ¦ q of a locally-optimal partition of X;

• optimalCut is a Boolean value that is true if and only if the maximal partition tXu is optimal among the admissible partitions of X. It thus provides a cut of the tree which represents an optimal admissible partition.

The pseudocode of the algorithm is given below (see Algorithm 1). The depthfirst search computes the optimalCost and the optimalCut of each node according to its cost and to the sum of the optimalCost of its children. After the execution, the optimal partition of Ω is the union of the higher nodes in the tree such that optimalCut true.

Algorithm 1 for the HSPP Require: A tree with a label cost on each node representing the cost of the corresponding admissible part. Ensure: Each node of the tree has a Boolean label optimalCut representing an optimal partition (optimalCut true if and only if the maximal partition is optimal for this node). Linear Complexity. Since the recording of the three labels needs a constant memory space for each node, the space complexity of this algorithm is bounded by the size of the data tree representing the hierarchy. As it contains between n 1 (only the root and the leaves) and 2n ¡ 1 nodes (in the case of a complete binary tree), the space complexity is linear. The operations needed to instantiate and exploit these labels are all achieved in constant time. Henceforth, the time complexity is the one of a depth-first search and is also linear, meeting the results of past algorithms dedicated to the HSPP (see Subsection 3.3). exploits the results to compare partitions X ¦ r1s tr2, nsu, . . . , X ¦ r1,n¡1s trnsu and it returns one that has the highest cost.

Data Structures and Implementation. Given the population Ω r1, ns, each admissible part ri, js P is represented by a couple of integer pi, jq, with r1, k 1 ¡1srk 1 , k 2 ¡1s . . . rk m , ns. The costs of these optimal partitions are recorded in a vector optimalCost of size n. Each cell optimalCostrjs, with 1 ¤ j ¤ n, gives the cost of the optimal partitions of part r1, js. The algorithm iteratively runs through the triangular matrix to build the two vectors and thus computes an optimal admissible partition of Ω. The pseudocode of the algorithm is given below (see Algorithm 2).

1 ¤ i ¤ j ¤ n.
Algorithm 2 for the OSPP Require: A matrix cost recording the costs of intervals.

Ensure: The vector optimalCut represents an optimal partition (see text above).

procedure SOLVEOSPP(j) Quadratic Complexity. For a population of size n, the upper triangular matrix contains 1 2 npn 1q values and the two vectors each contains n integers. Hence, the space complexity is quadratic. In the proposed implementation, for each part r1, js with 1 ¤ j ¤ n, the algorithm performs j ¡ 1 comparisons to identify the optimal partitions among the covering ones. Hence, overall, pn ¡ 1qpn ¡ 2q{2 comparisons are performed and the time complexity is also quadratic. This result meets the ones of the previous algorithms that have been developed for the OSPP (see Subsection 3.4).

Generalization and Limitation of the Framework

The SPP, as formalized in Subsection 3.1 and in most of the work herein referenced, is usually defined "at the part level". The set of admissible parts is an input of the problem from which the set of admissible partitions (i.e., the search space) is straightforwardly generated; and a cost is associated to each parts from which the cost of partitions (i.e., the objective function) is simply derived by summation. However, the expression of costs and admissibility constraints "at the partition level" might be required to model more complex problems where the feasibility and the quality of partitions cannot be simply derived from the feasibility and the quality of their parts. In this section, we present such cases where "the part level" is not longer sufficient to model the problem. Because the principle of optimality we introduced in Subsection 4.1 does not stand in these cases, we also discuss the strong limitations of the dynamic programming approach when dealing with this more general class of optimization problems (6.1 and 6.2). We also show in the last subsection how the algorithmic framework proposed in this paper can easily be improved to find not one, but all optimal partitions of a given instance (6.3).

Generalization to Decomposable Cost Functions

Most of the work related to the SPP -including this one -is interested in the optimization of an additively decomposable objective: dX P, cpX q °XX cpXq.

This property is also referred to in the literature as the sum property [START_REF] Csiszár | Axiomatic Characterizations of Information Measures[END_REF], blockadditivity [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF], or simply additivity [START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF], and it has been proved to be satisfied by numerous objective functions such as measures based on distances between individuals (e.g., sum/max of diameters/splits clustering [START_REF] Pintér | Set partition by globally optimized cluster seed points[END_REF]), quality measures for graph clustering (e.g., modularity and performance [START_REF] Pons | Post-processing hierarchical community structures: Quality improvements and multi-scale view[END_REF]), classical measures from information theory (e.g., Shannon entropy, Kullback-Leibler divergence [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF]), and other probabilistic measures for model selection [START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF]. To go further, the annexe of this paper shows that the principle of optimality (Subsection 4.1) and its con-verse (Subsection 6.3 below) actually hold for any objective that is decomposable by a monotone operator: h op : R ¦ Ñ R, dX P, cpX q opppcpXqq XX q and x i x I i ñ oppx 1 , . . . , x i , . . . , x n q oppx 1 , . . . , x I i , . . . , x n q. Hence, our framework can be straightforwardly applied to minimize, for example, the product of positive costs: dX P, cpXq ¥ 0 and cpX q ± XX cpXq. However, a more general version of the SPP could be interested in optimizing an objective c : P Ñ R that is defined at the partition level and that might not be decomposable at all: the cost of a partition is not entirely determined by the cost of its parts. This is for example the case with the lumping problem [START_REF] Pfante | Comparision between Different Methods of Level Identification[END_REF], where the state space of a dynamical process needs to be partitioned and aggregated such that the resulting macro-dynamics satisfy some closure property (e.g., informational closure, observational commutativity, Markovianity). In this setting, the quality of an aggregate strongly depends on the way other parts of the system are themselves aggregated. Hence, parts cannot be evaluated independently from the partition in which they appear and, as a consequence, the principle of optimality might not hold. Hence, no optimal substructure possibly helps to exploit the feasibility constraints and to design tractable algorithms. In this case, one surely needs to cling to heuristic or approximation algorithms to solve this more general SPP (see Subsection 2.2.1).

Defining Structural Constraints at the Partition Level

The classical SPP allows to model all kinds of constraints related to the structure of admissible parts, but it cannot express constraints regarding the structure of admissible partitions. Yet, much work is interested in computing optimal partitions with bounded size, thus imposing a constraint on the search space that cannot be expressed as constraints on the set of admissible parts: dX P, |X| k [START_REF] Chakravarty | A partitioning problem with additive objective with an application to optimal inventory groupings for joint replenishment[END_REF] or |X| k [START_REF] Björklund | Set Partitioning via Inclusion-Exclusion[END_REF][START_REF] Brucker | On the Complexity of Clustering Problems[END_REF][START_REF] Farrahi | Two-Way and Multiway Partitioning of a Set of Intervals for Clique-Width Maximization[END_REF][START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF][START_REF] Minoux | A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations[END_REF][START_REF] Muthukrishnan | Approximation algorithms for array partitioning problems[END_REF][START_REF] Pintér | Set partition by globally optimized cluster seed points[END_REF]. For another example, in the case of the APP (see Subsection 3.5), constraints are sometimes related to partition properties in addition to the rectangular shape of admissible parts [START_REF] Becker | Max-Min Partitioning of Grid Graphs into Connected Components[END_REF][START_REF] Mingozzi | Partitioning a matrix with non-guillotine cuts to minimize the maximum cost[END_REF]: hierarchical partitioning requires a nested partitioning where each rectangular subset, beginning from the whole array, can only be partitioned into two subsets (no complex intertwined patterns can arise this way); p ¢ q partitioning is even more specific since it requires that the sides of all rectangles are aligned with each others (the grid is actually partitioned by complete guillotine cuts in the vertical and horizontal axes).

Such constraints cannot be expressed within the classical SPP since, in this more general case, the set of admissible partitions does not fit with the set of partitions that are generated from the set of admissible parts. One problem when dealing with such partition constraints is that the branching scheme that is proposed in Section 4 cannot be used properly. Indeed, this scheme assumes that the admis-sibility of a part is defined independently from the way the rest of the population is partitioned. On the contrary, the partition constraints cannot be preserved while independently looking for locally-optimal admissible partitions in each branch of the search space. As for the generalization to objectives defined at the partition level, one also needs to cling in this case to heuristic or approximation algorithms to solve this more general SPP.

Computing the Whole Set of Optimal Partitions

One might be interested in computing not only one, but all optimal partitions: P ¦ arg min X P cpX q.

Our generic algorithmic framework can easily be adapted by considering the converse of the principle of optimality. Intuitively, a partition is potentially optimal only if its subpartitions also are.

Theorem 2. Let Ω be a population and c be an additive cost function defining partition optimality. For any partition Y of Ω, if a partition is optimal among the refinements of Y, then it is the the union of locally-optimal partitions of the parts of Y:

£ ¤ Y Y Y ¦ Y R ¦ pYq ñ dY Y, Y ¦ Y P ¦ pY q (6)
Proof. The proof of this theorem is given in annexe.

Hence, the set of optimal partitions that refine a given partition is the Cartesian product of the sets of locally-optimal partitions of the parts of that given partition: R ¦ pYq Y Y P ¦ pY q, and Eq. 5 can be replaced by the following formula: P ¦ pXq arg min

X ttXuu ¤ ¦ ¥ ¤ Y CptXuq 5 ¡ Y Y P ¦ pY q C cpX q (7)
This leads to an algorithm very similar to the one presented in Section 4, except that one needs to record sets of partitions and compute their Cartesian product, instead of simply recording partitions and computing their union. Note that, in this setting, the time and space complexity of the resulting specialized implementations may no longer be tractable since, in the worst case, all partitions are optimal and the output set P ¦ pXq hence has an exponential size. However, in practice, one might often assume that -except in extremal cases -the number of optimal partitions is bounded and very small (see for example [START_REF] Lamarche-Perrin | Building the Best Macroscopic Representations of Complex Multi-Agent Systems[END_REF]).

Conclusion and Perspectives

By exploiting strong assumptions regarding the global structure of the search space, dozens of problems have been modeled as tractable versions of the SPP. The algorithmic framework that we propose in this paper provides a unified dynamic programming approach to design such computationally-efficient optimal algorithms by exploiting the algebraic properties of such structures. This last section gives some application and research perspectives for this framework.

Applying the Generic Framework to Other Versions of the SPP

We have shown how the algorithmic framework might be easily applied to solve two well-known versions of the SPP, that is the HSPP and the OSPP. Section 5 made the specialization steps explicit: (1) formalization of the admissible parts and the resulting admissible partitions, (2) analysis of the generic algorithm execution, (3) design of data structures that fits with the induced algebraic structure, and (4) dynamic programing of the corresponding specialized algorithm. By following these steps, our programming method can be applied to numerous other versions of the SPP that might model interesting spatiotemporal structures: e.g., partitioning graphs into connected components [START_REF] Becker | Max-Min Partitioning of Grid Graphs into Connected Components[END_REF] or into spanning trees [START_REF] Lehmann | The Winner Determination Problem[END_REF], partitioning partially ordered sets such as interaction diagrams representing causal relations [START_REF] Lamarche-Perrin | Macroscopic Observation of Large-scale Multi-agent Systems[END_REF], partitioning the state space of dynamical processes, also known as the lumping problem [START_REF] Pfante | Comparision between Different Methods of Level Identification[END_REF], partitioning multidimensional populations mixing spatial and temporal constraints, such as the Cartesian product of a total order and a hierarchy structure [START_REF] Dosimont | A Spatiotemporal Data Aggregation Technique for Performance Analysis of Large-scale Execution Traces[END_REF]. To the best of our knowledge, these special versions of the SPP have not been solved yet, and we believe that they might all benefit from the generic approach presented in this paper. Another interesting research perspective is the following. For any such new version of the SPP, the computational complexity of the corresponding specialized implementation will be bounded from below by the number of admissible parts. Indeed, any algorithm should at least scan the input, that is the costs associated to each admissible part (or at least compute such costs from individual attributes). For both versions addressed in Section 5, the resulting specialized algorithms achieve such lower bounds: Opnq for the HSPP and Opn 2 q for the OSPP. However, this is not always the case. E.g., for a cyclic order, the number of admissible parts is Opn 2 q, but dynamic programming only provides a Opn 3 q algorithm (see [START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF] and Table 1). This leads to interesting the following research questions: For which versions of the SPP does the framework provide an optimization algorithm which complexity is bounded from below by the number of admissible parts? Such version are hence linearly solvable with respect to the size of the instance |P|. If not, is it possible to do better, or does the generic framework provide a computationallyoptimal algorithm? In that case, which algebraic properties of the search space allow to identify problems that can be linearly solved regarding the size of the input?

Enhancement Perspectives for the Generic Algorithmic Framework

Future work may build on the large literature regarding algorithms for special versions the SPP to enhance the generic framework proposed in this paper. Here are some research perspectives in that direction.

• In many real-world applications, costs are actually sparsely defined within the set of admissible parts. This is for example the case in the determination problem when no bid has been provided for many howeverauthorized combinations of assets, thus resulting in "holes" in the algebraic structure [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF][START_REF] Sandholm | BOB: Improved winner determination in combinatorial auctions and generalizations[END_REF]. Algorithms exploiting this sparsity of the cost function have been proposed to provide more efficient optimization procedures (for example in the case of the OSPP [START_REF] Sandholm | Algorithm for optimal winner determination in combinatorial auctions[END_REF]). Generalizing this strategy to enhance our framework would consist in assuming infinite cost for such "holes" and in avoiding branches of the decomposition where they appear, thus speeding up the resulting specialized algorithms.

• Pruning consists in identifying subspaces of the search space that have no potential of containing any optimal solution. An adapted search space representation have been proposed in the case of the CSPP to identify independent subspaces for which one can easily identify upper and lower bounds [START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF][START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF]. Branches of the decomposition that lies outside of such bounds are then safully avoided. One could build on the ideas and results of Sandholm et al. in the case of the CSPP [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF] to generalize this pruning approach to the generic framework.

• An anytime algorithm based on integer-partition has also been proposed in the case of the CSPP for the coalition structure generation problem [START_REF] Rahwan | Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation[END_REF][START_REF] Rahwan | An Anytime Algorithm for Optimal Coalition Structure Generation[END_REF]. It consists in quickly generating a suboptimal solution with bound guarantees by evaluating a reasonable subspace of the search space, then slowly improving this solution and establishing better bounds by evaluating other branches of the decomposition. The algorithm thus always provides a solution if stopped before termination, but it might, in the worst case, search the entire space, resulting in a Opn n q time complexity in the case of the CSPP. Once again, by building on the results of Sandholm et al. [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF], one might identify in a general way to identify subspaces that provide reasonable bounds and to provide a generic framework to build specialized anytime algorithms.

• Because of the optimal substructure of the SPP and the branching we proposed in Section 4, the computational approach presented in this paper is easily parallelizable. For example, the depth-first search of the hierarchy that solves the HSPP (see Subsection 5.1) can be performed in sublinear time with a linear number of processors [START_REF] Freeman | Parallel Algorithms for Depth-First Search[END_REF]. In the case of the coalition structure generation problem [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF] and the interaction-analysis of multiagent executions [START_REF] Lamarche-Perrin | Macroscopic Observation of Large-scale Multi-agent Systems[END_REF], it has also been proposed to distribute the optimization process among agents and coalitions, so that they share the burden of computation. These examples encourage us to generalize our algorithmic framework, exploiting the dynamic approach as well as classical distributed computation tools in order to build specialized parallel algorithms for versions of the SPP.

Annexe

In this annexe, we prove the principle of optimality (Theorem 1 in Subsection 4.1) and its converse (Theorem 2 in Subsection 6.3). As mentioned in Subsection 6.1, these two principles hold for any cost function that is decomposable according to a monotone operator. Hence, this proof is more general than the classical SPP considering only additive objectives. Let c be a cost function which is decomposable by a monotone operator op (see 6.1 for details). The proof is given for any partition Y tY 1 , Y 2 u of Ω and can easily be generalized to any partition Y tY 1 , . . . , Y k u. Because of decomposability, for any couple of partitions Y 1 PpY 1 q and Y 2 PpY 2 q, we have cpY 1 Y 2 q oppcpY 1 q, cpY 2 qq, and because of monotonicity, if cpY 1 q cpY I 1 q, then oppcpY 1 q, cpY 2 qq oppcpY I 1 q, cpY 2 qq. Proof of the Principle of Optimality (Th. 1). Let Y 1 P ¦ pY 1 q and Y 2 P ¦ pY 2 q.

Since op is monotone, for any partition Y I 1 Y I

2 RptY 1 , Y 2 uq, we have: cpY 1 Y 2 q oppcpY 1 q, cpY 2 qq ¤ oppcpY I 1 q, cpY I 2 qq cpY I 1 Y I 2 q Therefore, Y 1 Y 2 R ¦ ptY 1 , Y 2 uq. 2 RptY 1 , Y 2 uq, we have cpY 1 Y 2 q ¤ cpY I 1 Y I 2 q. By contradiction, let us assume that Y 1 P ¦ pY 1 q. Hence, there is a partition Y I 1 PpY 1 q such that cpY I 1 q cpY 1 q. Hence, since op is monotone, we have: cpY I 1 Y 2 q oppcpY I 1 q, cpY 2 qq oppcpY 1 q, cpY 2 qq cpY 1 Y 2 q

Since Y I 1 Y 2 RptY 1 , Y 2 uq, there is a contradiction. This also holds for Y 2 P ¦ pY 2 q. Therefore, Y 1 P ¦ pY 1 q and Y 2 P ¦ pY 2 q.

Figure 1 :Figure 2 :

 12 Figure 1: A 3-levels hierarchy defined on a population of size 9

Figure 3 :

 3 Figure 3: Decomposition of the search space according to the covering relation in the case of an ordered population of 5 individuals

(step 2 )

 2 For each partition Y CptXuq, do the following: (step 2.a) for each part Y Y, recursively compute a locally-optimal admissible partition Y ¦ Y P ¦ pY q; (step 2.b) compute the union Y ¦ Y Y Y ¦ Y of these partitions. The principle of optimality ensures that Y ¦ R ¦ pYq. (step 3) Return a partition that minimizes c among tXu and the Y ¦ R ¦ pYq computed for each Y CptXuq.

Fig. 5

 5 Fig. 5 gives an example of execution of this algorithm in the case of the OSPP with an ordered population of size 4. The starting point is the maximal partition at the top 1 2 3 4 . The plain numbered arrows represent the sequence of branchings executed by the algorithm (step 2): for example branching 1 evaluates the covering partition 1 2 3 4 . The dashed arrows represent the recursive calls on an admissible part (step 2.a): for example 1 2 3 4 corresponds to the execution of the algorithm on the first part of the partition 1 2 3 4 . Crosses and stars are explained in the next subsection.

Figure 4 :

 4 Figure 4: Recursive application of the algorithm

Figure 5 :

 5 Figure 5: Execution trace of the recursive algorithm (Subsection 4.3) for an ordered population of size 4. Plain numbered arrows represent branchings (step 2). Dashed arrows represent recursive calls (step 2.a). Crosses and stars give the cuttings of branches that may improve the algorithm (Subsection 4.4).

  Proof of its Converse(Th. 2). Let Y 1 Y 2 R ¦ ptY 1 , Y 2 uq.For any partition Y I 1 Y I

Table 1 :

 1 Combinatorics and optimal algorithms of special versions of the SPP

	Operational Research	Artificial Intelligence
	Scheduling, Delivery,	Winner Determination	Coalition Structure
	Transportation (2.1.2)	Problem (2.1.3)	Generation (2.1.4)

  The costs of admissible parts are recorded in a n ¢ n upper triangular matrix cost. Each cell costri, js, with 1 ¤ i ¤ j ¤ n, gives the cost cpri, jsq of the corresponding part. Optimal partitions are encoded in a vector optimalCut containing n integers such that, for all 1 ¤ j ¤ n, optimalCutrjs is the indice of the first individual of the last part of an optimal partition of r1, js. Hence, optimalCutrns k indicates that part rk, ns is in the optimal partition of r1, ns and, if k ¡ 1, then optimalCutrk ¡ 1s again indicates the first individual of the last part of an optimal partition of r1, k ¡ 1s, and so on. The optimal partition of r1, ns thus consists in a sequence of indices k 1 , . . . , k m recorded in optimalCut and indicating the m individuals where the population is divided:

In this context, the bidders are willing to pay for any combination of pairwise disjoint collections a price equal to the sum of the bid prices they expressed for these collections[START_REF] Lehmann | The Winner Determination Problem[END_REF].

Note that, if the population or the singletons are not admissible, but if the union of all admissible parts is: XP X P P, then the hierarchy can still be represented as a rooted tree. In any case, the hierarchy can be represented as a forest of rooted trees and the algorithms solving the HSPP can easily be generalized by a sequential execution to each tree of the forest.

If not, the following approach can easily be generalized by sequentially applying the algorithm to all maximal partitions, i.e. maximal elements in the poset of partitions induced by the refinement relation.

Acknowledgment

This work was partially supported by the French Agence Nationale de la Recherche under grant agreement ANR-12-CORP-0009 (GEOMEDIA project) and by the European Commission's 7th Framework Programme under grant agreement #318723 (MatheMACS project).

Solving the OSPP

As it has been previously defined, the OSPP arises when the admissible parts are the intervals of Ω induced by a total order (see Subsection 3.4 for the formal definition). A Opn 2 q dynamic programming algorithm has been proposed in independent work to solve this problem [START_REF] Anily | Structured Partitioning Problems[END_REF][START_REF] Jackson | An algorithm for optimal partitioning of data on an interval[END_REF][START_REF] Rothkopf | Computationally Manageable Combinational Auctions[END_REF][START_REF] Vidal | Optimal Partition of an Interval -The Discrete Version[END_REF]. Here again, we show how this result can be recovered as a special case of our generic framework.

Execution of the Generic Algorithm. An example of execution of the generic algorithm for an ordered population of size 4 has been given in Fig. 5. Given a population Ω of n ordered individuals x 1 . . . x n , for each interval x i , x j tx i , . . . , x j u with 1 ¤ i ¤ j ¤ n, the admissible partitions covered by the maximal partition t x i , x j u are the couples of subintervals t x i , x k , x k 1 , x j u with i ¤ k j. In the following, for the sake of conciseness, we simply mark such an interval ri, js and its covered partitions ri, ksrk 1, js. We thus have the following branching: Cpri, jsq trisri 1, js, . . . , ri, j ¡ 1srjsu.

The generic algorithm is applied to Ω r1, ns. Let us assume that the covered partitions are evaluated (step 2) in the following order: r1, n ¡ 1srns, r1, n ¡2srn¡1, ns, . . . , r1sr2, ns (see for example arrows 1 , 6 and 9 in Fig. 5). The covered partition r1, n ¡ 1srns is evaluated first ( 1 ). The algorithm is thus recursively applied (step 2.a) on part r1, n ¡ 1s ( 2 ), then on part r1, n ¡ 2s ( 3 ), and so on, until locally-optimal partitions of parts r1s, r1, 2s, . . . , r1, n ¡ 1s have been computed and recorded. All that remains is the computation of an optimal partition of part r1, ns. For the k th evaluation, with 1 k n, the covered partition r1, n ¡ ksrn ¡ k 1, ns has to be evaluated (for example 6 ) knowing that the covered partitions tr1, n ¡ isrn ¡ i 1, nsu 1¤i k have already been evaluated along with their refined partitions. The algorithm is recursively applied to parts r1, n ¡ ks and rn ¡ k 1, ns (step 2.a):

• Since the algorithm has already been applied to part r1, n ¡ ks during the first evaluation, the optimal partition is simply read from memory (see cross below 1 2 in Fig. 5).

• Regarding part rn ¡ k 1, ns, all covered partitions are now considered for evaluation. However, since rn ¡ k 1, n ¡ isrn ¡ i 1, ns refines r1, n ¡ isrn ¡ i 1, ns for all 1 ¤ i k, each covered partition has already been evaluated during the previous evaluations. Hence, steps 2.a and 2.b may be avoided (see star on arrow 8 in Fig. 5) and the algorithm uses the maximal partition rn ¡ k 1, ns.

To sum up, in order to compute an optimal partition X ¦ r1,ns , the generic algorithm recursively computes locally-optimal partitions X ¦ r1s , X ¦ r1,2s , . . . , X ¦ r1,n¡1s . Then, it