# Integer combination

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

$8x + 9y \le 124$

The module will return all possible positive integer for $x$ and $y$.Eg. $x=2$, $y=12$. It does not necessary be exactly $124$, could be any number less or equal to $124$. Must be as close as possible to $124$ 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?

-
Will the formula always be less than or equal to? And that simple? (i.e., in the form $a x + b y \le c$ for integers a, b, and c)? –  VF1 Aug 24 '12 at 17:27
I am not sure if this should be tagged in "optimization" and "linear programming". You are not maximizing/minimizing a function. –  Kartik Audhkhasi Aug 24 '12 at 17:32
en.wikipedia.org/wiki/Diophantine_equation, maybe this is where you are looking for? You can use Euclids' Algorithm to solve $ax+by=c$. en.wikipedia.org/wiki/Euclidean_algorithm –  Kevin Aug 24 '12 at 19:02
The number of variable could be any not just x and c, could be n variable. Thanks for tiping, all is welcome. –  zero Aug 25 '12 at 17:14
X and Y sory fot the typo –  zero Aug 25 '12 at 17:21

You are trying to solve

$${\rm maximize} 8x + 9y$$ subject to $$8x + 9y \le 124$$ $$x, y \in \mathbb{Z}^+$$

Which is essentially a special case of the knapsack problem. $${\rm maximize} \sum_i a_i x_i \le b$$ subject to $$\sum_i a_i x_i \le b$$ $$x_i \in \mathbb{Z}^+$$ This can be solved with a MIP solver.

-
Thanks for the tips, looking into it and will update u guys –  zero Aug 25 '12 at 17:22
Assuming $x,y\geq 0$ for the Knapsack problem. –  Daryl Oct 30 '12 at 22:00

Given a finite set $U$ of positive integers, and positive integers $B$ and $K$, the problem of determining whether there are non-negative integers $a(u)$ such that $K\le\sum_{u{\rm\ in\ }U}a(u)u\le B$ is NP-complete (which implies that it is computationally infeasible now and, perhaps, forever). This is discussed under the heading Integer Knapsack on page 247 of Garey and Johnson, Computers and Intractability. As has been pointed out already, it's easy if $\#U=2$.

-

Considering the equal case, if you analyze some of the data points that produce integer solution to the original inequality:

$$...,(-34,44), (-25,36), (-16,28), (-7,20),(2,12),(11,4),...$$

you can see that: $$x_{i}=x_{i-1}+9$$

to get $y$ values, re-write the inequality as follows (and use the equal part):

$$y = \frac{124-8x}{9}$$

using the above equations you can find $(x,y)$ values in a given range of $x$ values without brute force.

-