Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard. I will informally state the problem and some of the properties, since describing the problem as a whole would be too lengthy.
Non-linear Constrained Optimal Exact Cover
Consider a finite set $C=\{1,2,\ldots,m\}$ of elements and a vector $\mathbf{w}=\{w_j ~|~ j\in C\}$ of associated weights. The collection $S=\{s_1,s_2,\ldots, s_n | s_i\subset C\}$ contains every subset of combinations of elements of $C$ that fulfills: $$f(\mathbf{w}_{s_i})\ge 0, \forall s_i\in S;\quad \text{ where } \mathbf{w}_{s_i}=\{w_j ~|~ j\in s_i\}. $$ Find the subcollection ${S}^{*}$ of $S$ such that
($i$) each element in $C$ is contained in exactly one subset of ${S}^{*}$
($ii$) $g(S^*)=\sum\limits_{i=1,\ldots,n} g(\mathbf{w}_{s_i})$ is maximized.
Example: $C=\{1,2,3,4\}$ and $\{w_1,w_2,w_3,w_4\}$.
Given the weights, the non linear constraint $f(\mathbf{w_{s_i}})\ge 0$ implies: $$S=\{\{1\},\{2\},\{3\},\{4\},\{1,2\},\{2,3\},\{1,4\},\{1,2,3\},\{1,3,4\}\}$$ having each subset $s_i\in S$: $$\{g(\mathbf{w_{s_i}}) ~|~ s_i\in S\}=\{4,2,1,5,2,7,8,2,3\}.$$ Solution: $S^*=\{\{2,3\},\{1,4\}\},$ since each of the elements of $C$ is contained in exactly one subset of $S^*$ and $g(S^*)$ is the maximum possible.
Note that the Minimum Exact Cover Problem is related but deals with a different objective function (minimize the cardinality of the set) and the general description of the problem does not constrain the subsets that can appear in an instance for S (unlike this problem).
My feeling is that the problem is NP-Hard, since as increasing the size of $C$, the possible set of partitions increase quickly (Catalan numbers). However, I do understand that the reduction in the feasible space may vary the complexity.
My goal is to find the conditions on the functions such that the problem remains NP-Hard or, if none if it is NP-hard for any pair besides the trivial functions. I have been working a bit into that, but this is not my field of expertise and I am suspicious that a similar work has been done or that a reduction in trivial for expert eyes or at least a categorization of the problem.
Notes
- $ ~ f$ and $g$ are non linear functions that depends on the partition. It is hard to define them hereby, but they aim to evaluate the subset similarity, e.g., $f(\mathbf{w}_{s_i})\ge 0$ ensure that the elements weights are similar enough among each other.
- For any instance of the problem there exists at least one feasible partition. The partition that includes each element in a subset ${S}^{'}=\{\{1\},\{2\},\ldots,\{m\}\}$ is feasible (fulfills condition ($i$)), but it may not be optimal.
- Clearly, there are some functions for which the problem seems trivial, i.e., if the constraints are $f(\mathbf{w}_{s_i})=-|\mathbf{w}_{s_i}|+1 \ge 0$ then only the partition $S^{'}$ is feasible and then the solution can be obtained in O(1).
