2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the perturbation a variable of the problem or a parameter that you specify beforehand? $\endgroup$ – Septimus G Jan 30 '18 at 3:23
  • $\begingroup$ Perturbation is specified according to our requirements $\endgroup$ – Janson 7 Jan 30 '18 at 8:54
  • $\begingroup$ 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. $\endgroup$ – Deathbreath Feb 12 '18 at 17:48
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.