# Find combinations of variables with variable bounds to get summed up to a required value (using Python)

Let's say I have n variables. Each variable has lower and upper bounds. I want to find all suitable combinations of these variables to sum up to a required value.

An example with two variables:

$$x_1 + x_2 = 100\\ 0 <= x_1 <= 70 \\ 0 <= x_2 <= 60$$

So the result would look like

$$(x_1, x_2) \in \{(70, 30), (69.8, 30.2), \cdots\}$$

These variables could take integer and decimal values as given above. The perturbation values for each of these variables can be chosen according to the requirements. The perturbation values used here are Pert[X1,X2]=[0.2,0.2].

This problem of solving for two variables is comparatively simple than having n number of variables.

Is there an algorithm available in Python to solve such a problem ? It would be even more helpful, if a Python code using the algorithm to solve a similar problem could be provided.

• Is the perturbation a variable of the problem or a parameter that you specify beforehand? – Septimus G Jan 30 '18 at 3:23
• Perturbation is specified according to our requirements – Janson 7 Jan 30 '18 at 8:54
• As written this is a linear program? $$\min s$$ subject to $s\ge 100$, $x_1+x_2=s$ and your box constraints. You could use PuLP or any of the other linear programming solvers available in python to solve this problem. – Deathbreath Feb 12 '18 at 17:48

This problem could be written as the "restricted knapsack" problem: given a set of items each with a weight $w_i$, fill up your knapsack with at most a certain number $c_i$ of each item respecting the total weight of the knapsack. Mathematically, this is written as:
$\textrm{max} \sum_{i=1}^{N} w_{i} x_{i} \ \mathrm{s.t.}\ \sum_{i=1}^{N} w_{i} x_{i} < W \ \mathrm{and}\ x_{i} \leq c_{i}$
In your case, the weight of each variable should correspond to the perturbation. Then you solve the above optimization problem where your values are the $w_i$'s and your upper limits the $c_{i}$'s.
In your case you could set: $w_1 = 0.2,\, w_2 = 0.2,\, c_1 = 350,\, c_2 = 300$.
With the constraints you have listed, you may declare $x_i$ as integer, then solve with an IP solver (see the open-source coin-or solvers, and cplex or gurobi if you have access to them) to enumerate all feasible integer solutions. From here you can easily calculate the perturbed values, and find the target set.