CODEWITHSUNDEEP
mathematical-optimization
user1622801
user1622801

Reputation: 31

integer combination

i want write a module to find the integer combination for a multi variable fomula. For example

  8x + 9y <= 124

The module will return all possible positive integer for x and y.Eg. x=2, y=12. It does not neccessary be exactly 124, could be any number less or equal to 124. Must be as close as posible to124 if no exact solution could be found.

I do not want to solve with brute force as the number of variable could be any...(5,10,100,...n)

Any algorithm could solve this?

Upvotes: 1

Views: 115

Answers (1)

Ram Narasimhan
Ram Narasimhan

Reputation: 22516

You can solve this by recasting your problem as an integer programming problem.

Rewrite your equation as a constraint.

8x + 9y < = 124 as

8x + 9y + z = 124

Notice that we have introduced a slack variable z. We want z to be as small as possible, so make the objective function to be Minimize z Any solver will try all possible integer values of x and y before incrementing z.

Your full IP will be:

Min z
8x + 9y + z = 124
x,y,z >=0 and Integer

Solve using any commercial or open-source LP/IP solver. (R's optim package is one possibility, Excel Solver will also do.)

If for any reason, you want x or y to be larger or smaller, you can control those as well with the objective function co-efficients.

More generally, Min Cx x + Cy y + Cz z and control the weights of cost parameters Cx Cy and Cz to suit your needs.

Hope that helps.

Upvotes: 1

Related Questions