3

I have the following problem:

Given a set of sums of variables like { a + b, b + c, c + d, a + a + d, b }, find positive integer values for the variables such that all sums are distinct and the highest sum is as small as possible.

Is there an algorithm to find or approximate a solution to this kind of problems?

fuz
  • 88,405
  • 25
  • 200
  • 352
  • 1
    Reminds me of Boolean satisfiability, which in general is NP-complete, I'm thinking the same applies here. In this case, you could probably get a good fast approximation, in `O(N^2)` or better. You might want to consider making a guess as to what the highest sum will be then trying to see if it's possible. The higher the guessed sum compared to the actual sum, the easier it should be to find an valid (if not optimal) solution. – Nuclearman Dec 03 '14 at 13:17
  • What kind of constraints do you have? e.g. how many terms in each sum, how many sums, how many variables, how many times can a single variable be repeated in a single sum? – Peter de Rivaz Dec 03 '14 at 13:34
  • @PeterdeRivaz In the concrete instances I have, there is for each variable one sum containing only that variable as well as some other sums. About half of the variables only appear once (in the sum where they appear alone). My concrete instance has about 25 variables and 52 sums. Each sum has no more than 3 addends. In each sum, each variable appears not more often than twice. I can write down the instance if that helps you. – fuz Dec 03 '14 at 13:39
  • Not sure of a good algorithm for this, but you could try using an integer optimization tool such as [glpsol](http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit) – Peter de Rivaz Dec 03 '14 at 13:51
  • I would try a constraint solver (e.g., z3). A MIP solver won't handle the all-distinct constraint very well. – David Eisenstat Dec 03 '14 at 13:59

1 Answers1

1

I have created a possible solution and an implementation in C#. Hope it is what you need. It would be nice if someone proves it is correct/incorrect but it works and results look correct. The details on theory are below. Its complexity is something about O(N!*M^3*Log2(N)) where N is number of variables and M is number of summands all sums.

BTW, for your example it gives this result:

c=3, a=2, d=2, b=1
{a+b=3; b+c=4; c+d=5; a+a+d=6; b=1}
max=6

UPDATE

Theory of the algorithm.

Assume the variables are ordered, e.g. a >= b >= c >= .... Lets say a set of sums is a Bag if all sums in it are distinct. All sums in a Bag can be divided into two groups: sums that do not contain variable a and sums that do contain. Lets call the first group as Head and the second as Tail. Note that both are Bags because they contain distinct sums. We can subtract a from each sum in Tail so that all sums remain distinct (i.e. the Tail is still a Bag). This way we get two bags both without variable a.

Similar way we exclude variable b from two Bags and get four Bags. This operation we repeat for each variable until we get sums with last variable (lets say it is d). The smallest value of d is 1.

After that we can return to the previous step and include variable c in sums from tails. Remember that we have many pairs Head-Tail and need to join them back. To do that we add c to each sum in each Tail so that sums from the Tail have to be distinct from the Head.

How to calculate c? The idea is to calculate its invalid values and then take the smallest value that is not invalid and also is equal or greater than d. Calculating invalid values is trivial, using condition HeadSum != TailSum + c => c != HeadSum - TailSum. For each combination of tail sum and head sum we get all invalid values.

Collapsing all pairs Head-Tail back and calculating each variable we get the solution for the case a >= b >= c >= d. Then we calculate a solution for each permutation of a >= b >= c >= d and find the smallest one.

PS It would be great if someone provide better solution because I think my algorithm is somewhat of approximation (but a good approximation) or even better to prove it. The worst thing is N! complexity because of permutations and I still have no idea how to get rid of it.

neleus
  • 2,230
  • 21
  • 36