I'm trying to figure out if there is a common name for the following optimization problem of computing products of subsequences of a sequence:
Given a set $S$ of $m$ sets $\{S_1,\dots, S_m\}$, where $S_i = \{j_0, \dots, j_{k_i}\}$ s.t. each $j_\ell$ is an index i.e. $0\leq j_\ell \leq n$, and a sequence of elements $X = (x_0,\dots, x_n)$, find the minimal number of multiplications it will take to compute all sets, assuming that for computing each set $S_i$ we need to multiply all elements with the corresponding indices i.e. $X(S_i) = \prod_{j \in S_i} x_j$.
For example, suppose we have $S= \{S_1,S_2,S_3,S_4\}$:
$S_1 = \{0,1,3,4\} \\ S_2 = \{0,1,2,3,4\} \\S_3 = \{0,1,2,5,6\}\\ S_4 = \{0,1,3,4,5,6\}$
The minimal number of multiplications will be $8$ (as far as I can tell):
$y_1 =x_0x_1\\ y_2 = y_1x_2\\ y_3 =x_3x_4\\ y_4 = x_5x_6\\ X(S_1) = y_1y_3\\ X(S_2) = y_2y_3\\ X(S_3) = y_2y_4\\ X(S_4) = X(S_1)y_4$
It's not exactly a set cover problem, though it's very similar. Generalized matrix chain multiplication is close too, seems even a better fit than the set cover, but maybe there is something else. I was wondering if some problem in graphs might be a better match.
Do you have any idea, what this problem might be called? Or to which one is it the closest?
Not sure if this problem has a name, but you can solve it via integer linear programming as follows, where I have changed the meaning of $S$, $x$, and $y$. For each subset $S \subseteq \{0,\dots,6\}$, let binary decision variable $x_S$ indicate whether subset $S$ is formed. The problem is to minimize $\sum\limits_{S:|S|>1} x_S$ subject to \begin{align} x_S &= 1 &&\text{for the (four) target subsets $S$} \tag1\\ x_S &\le \sum_{\emptyset \not= T \subsetneq S} x_T x_{S \setminus T} &&\text{for all $S$ such that $|S|>1$} \tag2 \end{align} Constraint $(1)$ forces the formation of the specified target subsets. Constraint $(2)$ forces each formed subset to arise from the disjoint union of two other proper subsets. You can linearize this constraint by introducing a new binary variable $y_{T,S \setminus T}$ and replacing $(2)$ with \begin{align} x_S &\le \sum_{\emptyset \not= T \subsetneq S} y_{T,S \setminus T} &&\text{for all $S$ such that $|S|>1$} \tag{2a} \\ y_{T,S \setminus T} &\le x_T &&\text{for all $S$ and $T$ such that $\emptyset \not= T \subsetneq S$ and $|S|>1$} \tag{2b} \\ y_{T,S \setminus T} &\le x_{S \setminus T} &&\text{for all $S$ and $T$ such that $\emptyset \not= T \subsetneq S$ and $|S|>1$} \tag{2c} \end{align} For your four target sets, the optimal objective value is indeed $8$, attained by taking $x_S = 1$ for all $S$ with $|S|\le 1$, $$x_{01}=x_{34}=x_{56}=x_{0156}=x_{0134}=x_{01234}=x_{01256}=x_{013456}=1,$$ and all other $x_S=0$.
In terms of graph theory, you can interpret $x_S$ as a node variable and $y_{T,S \setminus T}$ as an edge variable in an undirected graph. The problem seems like a generalization of minimum edge cover for which only the target nodes need to be covered.