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

Question

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.

Answer 1

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$.

There seems to be a Python snippet at code review s.e.. No guarantees on the correctness or effiency of this snippet. You could also use the GNU Linear Programming Kit (GLPK) through the CVXOPT package. I don't know if these tools can provide all feasible solutions or if they would stop if an optimal (i.e. the equality constraint is satisfied; i.e. the knapsack is completely full) combination is found.

Answer 2

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.