The problem: n variables (x) add up to be a constent. x1+x2+..+xn = const, where each x can only take p (say 5) positive integer values. We want to find the solution where the difference between x's are minimized, i.e. they are most evenly distributed. Is this an integer programming problem?
dlm
Yes this is an integer programming problem. You can write it as:
minimize |x1 - x2| + |x2 - x3| + ... + |xn-1 - xn|
subject to x1 + x2 + x3 + ... + xn == c,
xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n,
yi1 + yi2 + ... + yip == 1, i=1,...,n,
yij binary for i=1,...,n j=1,...,p,
xi integer for i=1,...,n,
here the Aij are known input data that describe what integers a particular value of xi may take on. Below is a concrete example with 3 variables (n=3), where each xi can take on one of two integer values (p=2). That is x1 can be 1 or 3, x2 can be 3 or 4, x3 can be 2 or 3.
minimize |x1 - x2| + |x2 - x3|
subject to x1 + x2 + x3 == 8,
x1 == 1*y11 + 3*y12,
x2 == 3*y21 + 4*y22,
x3 == 2*y31 + 3*y32,
y11 + y12 == 1,
y21 + y22 == 1,
y31 + y32 == 1,
yij binary i=1,2,3 j=1,2
xi integer i=1,2,3
You can reformulate the above problem as a MIP (a mixed integer program) by creating a new set of variables u to represent the objective function.
minimize u1 + u2 + ... + un
subject to ui >= xi - xi+1, i=1,...,n-1,
ui >= xi+1 - xi, i=1,...,n-1,
x1 + x2 + x3 + ... + xn == c,
xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n,
yi1 + yi2 + ... + yip == 1, i=1,...,n,
yij binary for i=1,...,n j=1,...,p,
xi integer for i=1,...,n,
ui real for i=1,...,n-1,
You can use any standard MIP solver to solve the above problem.
It seems to be np-complete problem, at real you need to search whole space of solutions to get proper distribution. Maybe try this
I. Greedy algorithm
foreach x in xses
if current_sum < desired_sum:
take maximal p for x
else take_minimal p for x
As you see this will not bring you to proper solution, probably you will have some SUM greater than DESIRED_SUM
but after this you can start to optimize your distribution: now we have set of greedy selected xses
foreach x:
if current_sum > desired_sum
change taken P to minimal P for x
else
break
this will bring you to close solution
II. Evolutionary algorithm
Strict definition of your problem brings you to genetic algorithms. Populations will be vectors of X=[x1,x2,x3,x4...xn] fitness function it's obvious (difference between desired sum and computed sum from X)
just do proper evolutionary operations on vectors and it should bring you to optimized solution in short time
Do you have any bounds (or extra info) on the integers? If they aren't too big, it can be feasible to do an algorithm that goes through all possible sums (without doing all the combinations):
function adds_up_to(xs, N):
sums := {0}
for i from 1 to n:
new_sums := {}
for sum in sums:
for value in values:
new_sums := new_sums U {sum + value}
sums := new_sums
return (N in sums)
(This just searches for a satisfying solution. The algorithm needs to be beefed up to handle the difference-minimizing, whatever that means)
As for the obejctive function, it is trick when you want to minimize the difference among the set. The simple form could be the Sum(ABS(Xi-Xj)) where i>j. which can be linearized. However if you want to use sample variant, that would become a QIP and a bit more time consuming to solve.
