CODEWITHSUNDEEP
algorithmpuzzlelinear-programming
dlm
dlm

Reputation: 21

Is this integer programming?

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

Upvotes: 2

Views: 411

Answers (4)

jc W
jc W

Reputation: 99

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.

Upvotes: 0

codehippo
codehippo

Reputation: 1447

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.

Upvotes: 4

hugomg
hugomg

Reputation: 69934

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)

Upvotes: 0

dfens
dfens

Reputation: 5515

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

Upvotes: 0

Related Questions