optimizing Frobenius instance solutions

Question

The papers I've found about the Frobenius instance problem (given a set of distinct positive integers, find the positive integer coefficients that make a linear combination of some of them add up to a given integer) seem interested in computational efficiency with very large numbers or just finding the Frobenius number.

Instead, I have an application with relatively small problems (less than a hundred numbers to obtain a sum up to a few thousands) that are likely to have many solutions, and I want to choose the best solution with various criteria such as using as many different numbers as possible, preferring to use larger numbers, minimizing the variation between coefficients, etc.

I can compromise on not finding the best solution, but not on missing a solution if one exists; my best plan so far is growing solutions by dynamic programming or with an A* search (choosing pieces that seem good), at the cost of not using the most appropriate cost functions.

I'd like to hear about previous work about

• this kind of optimization over all solutions;
• algorithms to enumerate all solutions rather than finding an arbitrary one;
• algorithms to find the number of solutions (nice to know before evaluating them brute-force);
• sensible ways to split a problem into smaller ones.

Thank you in advance.

Answer 1

Mathematica finds all solutions to modest-size Frobenius problems. I think it is using the classic paths-in-graphs approach -- a modern approach to which as in my paper....

Faster algorithms for Frobenius numbers, Dale Beihoffer, Jemimah Hendry, and Albert Nijenhuis, Stan Wagon, Electronic Journal of Combinatorics, 12:1 (2005) R27 (www.combinatorics.org) or stanwagon.com/wagon/papers/FrobeniusByGraphs.pdf

If you don't have Mathematica go to http://wolframalpha.com and enter

FrobeniusSolve[{16, 119, 202}, 5000]

and you will see all solns.

This web page times out at some point, so a much larger problem might fail. Feel free to contact me if you want me to try this in Mathematica for you. wolframalpha allows almost all simple Mathematica commands to be tried, and the folks at WRI have done an amazing job with the Frobenius problem.

Stan Wagon

Answer 2

I was reading some fascicles of Knuth's volume 4 on combinatorial enumeration. It seems that he was using Binary Decision Diagrams (BDDs) and variations to calculate quickly similar numbers. Perhaps this will help.

Also, your description suggests to me that solutions will exist, that they can be found greedily, and that optimizing them may gain very little for the effort involved. For example, to get a representation involving many of the stamp values, I would start by forming partial sums of the stamp values in increasing order until I came close to the target or ran out of values. Then I would use standard methods to represent the difference, and voila, I have made the target using the most stamp values possible. If you want a better answer than this, provide a couple of explicit examples to communicate the feel of the problem (e.g. "using stamps in prime values from 23 to 199 cents, make 2010 cents in postage without using more than two of any single denomination, while using as few of the stamps over 100 cents as possible") .

There also were some recent papers in arxiv.org that talked about algorithms used to solve the postage stamp problem with large stamp values. It may be that some dual exists where you can use large numbers of small stamp values to accomplish your goal.

I hope this "soft answer" jogs some neurons into something that will work for you.

Gerhard "Ask Me About System Design" Paseman, 2010.01.15

Answer 3

The number of solutions is relatively straightforward to compute (although I don't have anything intelligent to say about the computational complexity of the method I'm about to propose). The number of ways to write $n$ as a non-negative linear combination of the integers $a_1, a_2, ... a_k$ is the coefficient of $x^n$ in the generating function

$$\prod_{i=1}^{k} \frac{1}{1 - x^{a_i}}.$$

The coefficients of this generating function are a quasi-polynomial, and it is straightforward if tedious to compute all of the relevant coefficients (essentially partial fraction decomposition). In particular, it is very easy to determine the asymptotic behavior: for large $n$, the leading term is $\frac{n^{k-1}}{(k-1)! a_1 a_2 ... a_k}$. (There is a nice way to think about this geometrically as computing the volume of a large simplex.)

This method is only likely to be useful to you if $n$ is much larger than $\text{max } a_i$, I think.