Minimum cost factoring in abelian groups

Question

I have a certain optimization problem, and I'm wondering if there is a clever approach for solving it. (This may well have been extensively studied and I just don't know what name to look it up under.)

I have a (EDIT: free) finitely generated Abelian group, G, on n generators. I also have a set P of elements of G, each labeled with a strictly-positive cost. All of the generators of G appear in P, so it is always possible to express any element of G as a product of elements of P or their inverses. The cost of any such product is the sum of the costs of the elements of P that appear in it, taking into account how often they appear. The cost of the nullary product, which expresses the identity element of G, is zero.

Given an element of the group I'd like a way to find a minimum-cost product that expresses it in terms of elements of P.

It's straightforward to translate this into a shortest-path problem without negative dicycles (on an infinite graph, but for any given element you only need a finite part of it near the identity element). It's also straightforward to translate it into an integer linear programming problem.

It may be that one of those translations is the way to go? Or does the additional structure of this problem lead to an easier way to do it? In my actual problems 5 <= n <= 10 and the elements I'm interested in never have multiplicities of any of the generators bigger than roughly +/- 20.

I'm working in Haskell, so functional approaches would be preferred to stateful ones, but stateful approaches are OK too.

Answer 1

Warning: Untested Pseudocode

This is pseudocode.  It isn't finished and probably won't even compile.

minCost :: element -> [generator] -> number -> Maybe [generator]
minCost _ [] _ = Nothing
minCost x _ c | (elemCost x) + c > cutoff = Nothing
minCost e _ _ = Just [] -- The factorization of the identity is the nullary product.
minCost x gs _ | elem x gs = Just [x]
minCost x gs _ | elem x ps = Nothing -- in P but not in gs.
minCost x gs c  =
  argmin
    pathCost
    [maybeCons g (minCost (x-g) [h| h <- gs, h <= g, h /= -g] (c+(elemCost g))) | g<-gs]

maybeCons :: a -> Maybe [a] -> Maybe [a]
maybeCons _ Nothing = Nothing
maybeCons x (Just xs) = Just (x:xs)

elemCost :: element -> number
pathCost :: [element] -> number
pathCost = sum . map elemCost

argmin :: (a -> n) -> [Maybe a] -> Maybe a
-- Return the item with the lowest cost, or Nothing if there isn't one.

There's a little bit of handwaving here, but the logic should, I hope, be clear. We have to impose an arbitrary total ordering on P and argmin has to handle results of Nothing, representing that there's no way to generate x from that subset of P. My pseudocode doesn't have quite the right syntax to do this, for readability.

Excluding h > g from the allowed generators is safe, because any solution containing h would be found by the minCost (x-h) branch, up to permutation (and G is Abelian, so any solutions that are permutations are equivalent). Excluding -g is safe because g + (-g + a) = a, but at strictly higher cost, so no such solution could be optimal.

The algorithm needs a way to prune branches such as, when P = {1,-1,i,-i}, testing (2+i) {1,-1,-i}, (2+2i) {1,-1,-i}, ad infinitum. This probably requires pruning the search when the cost exceeds a cutoff. With that fix, it terminates because each recursion reduces the size of gs or the number of steps until x reduces to a generator, until it reaches one of the base cases or the cost accumulates above the threshold. (This might be improved by passing up the lowest cost calculated on any parallel branch so far.) It cannot repeat a computation because we have excluded the inverses of all previous steps in the path.

Afterthoughts

Saying that e generates itself even if not in P is incorrect by requirements and unnecessary for correctness: the algorithm never adds an element to its own inverse, so this can only occur if we ask explicitly how to generate the identity. And that's a valid query: complex roots of unity?

On further reflection, thanks for the suggestion to represent the identity as the nullary product. Otherwise, we'd fail because we never check generators against their inverses! It has the right type, too!

There's a case to make the return type [[generator]] instead of Maybe [generator] and return all optimal productions, representing Nothing as []. The definition of maybeCons would become just map ((:)g). However, this risks exponential blow-up if there are a lot of equally-cheap paths.

Returning the cost along with the factorization, in a tuple, would both let us prune any later parallel branch with a higher cost sooner. Or we could use pathCost for this.

The particular lattice structure of your group might suggest more ways to prune, although I'm not thinking of any others in general. For instance, for the complex integers under addition, we can easily detect what the two (at most) generators must be just from the real and imaginary coefficients. In many groups, we can easily detect that something is not a product of a particular generator by which subset of G it is in. These could be additional guards that tail-recurse with a proper subset of gs.

The generator type has to be the same as element or an instance of it, because of the cost function. The ordering relation might be defined only for generators, or their structure might be simpler. It might have a different name if the group has a natural ordering that happens to be less efficient for the algorithm.

I'll leave in the note that the code isn't supposed to compile because I'm pretty sure I wrote at least one bug.