You are given a set $A$ of integers of size $n$ and a common divisor $r$ called the "anchor", which isn't in $A$ and isn't necessarily the greatest common divisor, either. Let $M$ be the least common multiple of all elements in $A$. The cost of $A$ is then defined as $\frac{M}{r} \cdot n$.
For example, if $A = \{25, 30, 50\}$ and $5$ is the anchor, the cost will be $\frac{150}{5} \cdot 3 = 90$.
You want to minimize the cost of $A$. In order to reduce the cost of $A$, you can "spin off" $A$ by creating a set $S$ and moving $k$ elements from $A$ there, which must be divisible by some element $a\in A$ where $a > r$. The element $a$ becomes the anchor of $S$, which cannot be in $S$. The cost of $S$ is then $\frac{M}{a} \cdot k$. $S$ and $A$ after spin-off must be mutually exclusive. The cost of $A$ after spin-off is the sum of the costs of $A$ and all of its spin off sets.
For example, if you spin off $A$ by defining $S$ to be $\{50\}$, $A$ would be left with just $\{25, 30\}$. The cost of $A$ after spin-off would be $\frac{150}{5} \cdot (3 – 1) = 60$ and the cost of $S$ would be $\frac{150}{25} \cdot 1 = 6$. The total cost of $A$ would be $60 + 6 = 66$, which is smaller than $A$ before spin-off.
You can spin off $S$ and in turn spin off its own spin-off sets and so on. You can also add an element to a set to serve as the anchor of its spin-off set.
For example, if $A = \{20, 30, 50\}$ and $5$ is the anchor, the cost will be $\frac{300}{5} \cdot 3 = 180$. However, if you spin $A$ off by adding $10$ and moving the rest, you will have $A = \{10\}$ and $S = \{20, 30, 50\}$. The cost of $A$ after spin-off is $\frac{300}{5} \cdot 1 = 60$ and $S$ is $\frac{300}{10} \cdot 3 = 90$, for a total of $150$.
The goal is to minimize the total cost of $A$ by spinning it off, recursively if necessary.
How do you go about doing this? Is this a non-linear optimization problem?
This is not homework. I'm a programmer and this is actually for my work which I've abstracted. I've taken a few university level math courses like $10$ years ago, but I barely remember high-school math now…
Thank you in advance.
Best Answer
If I understand the question correctly, a solution to the problem will have the form of a (rooted) tree. Each vertex of the tree will be labeled with a set of positive integers, which is either what remains of $A$, at the root, or a spin-off of $A$, a spin-off of a spin-off of $A$, etc. at vertices which are not the root. The sets of positive integers must fulfill the following constraints:
(1) They are nonempty and disjoint;
(2) All integers in all sets divide the original lcm, $M$;
(3) The union of the sets contains the original set $A$;
(4) For each set, its gcd is divisible by its anchor, which is a member of the set at its parent vertex (if the set is not at the root) or a fixed, given, number $r$ not appearing in any set (if the set is at the root.)
Given such a tree, its cost is $M \sum_v (\#S_v)/a_v$, where $v$ ranges over the vertices of the tree, $S_v$ is the set at vertex $v$, and $a_v$ is the anchor of the set at vertex $v$.
First, observe that if a vertex is labeled with a set of size larger than 1, $\{c_1,\ldots,c_t\}$, say, we can split it into $t$ vertices, labeled with $\{c_1\}$, $\{c_2\}$, $\dots$, $\{c_t\}$, and reapportion its child vertices among these vertices so that each child set is beneath its anchor. This does not change the cost of the tree, so after doing this repeatedly, we may assume that all sets have size 1, i.e., each vertex is labeled with a single number. Second, observe that we may add a vertex above the root labeled with the original anchor. These two steps reduce the problem to the problem of finding a rooted tree whose vertices are labeled with distinct positive integers which satisfies
(a) All labels divide $M$;
(b) The root is labeled with $r$, the original anchor;
(c) The set of labels contains the original set $A$; and
(d) the label at the top of each edge divides the label at the bottom,
and which has minimum cost, where the cost is now $M$ times the sum over all edges of the reciprocal of the label at the top of the edge. Also, we may now allow $r$ to be a member of $A$, and we observe that there is no need to require the vertex labels to be distinct, since if we had two vertices with the same label, we could construct a cheaper tree by deleting one of them and reapportioning all its children to the other.
Let $T$ be an minimum-cost tree for $r$, $M$ and $A$. Observe that:
(i) Each of the leaves of $T$ must be labeled with a member of $A$, since otherwise we could construct a cheaper tree by removing a leaf.
(ii) If a vertex other than the root has exactly 1 child, it must be labeled with a member of $A$, since otherwise it would be cheaper to remove the vertex and reapportion its child to its parent.
(iii) If a vertex other than the root has 2 or more children and is not labeled with a member of $A$, we can assume that its label equals the gcd of the labels of its children, since otherwise we could make a cheaper tree by relabeling it with the gcd of the labels of its children.
(iv) Fix some parent vertex $v$ of leaves, and let it have label $l$ and leaf children $w_1$, $\ldots$, $w_t$ with labels $s_1$, $\ldots$, $s_t$. Then if we delete $w_1$, $\ldots$, $w_t$ from $T$, the remaining tree, $T'$, must be minimum-cost for $r$, $M$, and the set $A\cup\{l\}\setminus\{s_1,\ldots,s_t\}$, since if there was a cheaper tree, $T''$, say, for this set, we could make a tree cheaper than $T$ for $A$ by attaching the children $w_1$, $\ldots$, $w_t$ to the vertex labeled $l$ in $T''$.
Rules (i)-(iv) give us a recursive algorithm for finding an optimal tree $T$. If $A$ is empty or $A=\{r\}$, we are done since the optimal tree consists of only the root vertex and has cost 0. Otherwise, $T$ must have at least one leaf, and since, by (i), all leaves are labeled with a member of $A$, there must be some subset $\emptyset\ne S\subseteq A$ and some vertex $v$ such that $v$ has only leaf children and $S$ contains the set of labels of the set of leaves, $W$, which are children of $v$. Then, by (ii) and (iii), the label of $v$, $l$, must be either $r$, some member of $A$, or $\gcd(S)$. Now, let $T'$ be $T$ with the vertices in $W$ removed; by (iv), we can compute $T'$ by calling the algorithm again to find an optimal tree for $A\cup\{l\}\setminus S$, and then $T$ can be reconstructed by reattaching the children $W$ to $v$. Performing this step for all possible choices of $S$ and $l$ will give a set of possibilities for $T$ from which we can take the best possible answer.