I am trying to make myself a little script or something that can help me find the lowest amount of combinations needed to reach a target set of values. But I am having problems finding a way to do this as all I can find is similar problems but with just a single sum, not a set of numbers.

Consider this table:

   | X | Y | Z
A  | 4       4
B  |     5   5
C  | 4   4
D  | 3   3   3

A, B, C, D are different sets that yields different amounts of X, Y, Z.

Now let's say that our target is 40X, 80Y, 60Z.

By manual trial and error the lowest combination of sets I could find was 21, and there are multiple variations that reaches this target.

For example: 0A, 9B, 7C, 5D = 43X, 88Y, 60Z But also 1A, 8B, 6C, 6D = 46X, 82Y, 62Z

Both are valid as they both use 21 total combinations and reach the target values. Some are slightly over, but that is ok, the important part is the least amount of sets without going under any of the target values.

My question: How would I go about finding out if 21 is the lowest possible, and if not, what the combination that would give a lower amount would be?

CodePudding user response：

Floating-point solution

This is a very classic linear programming problem.

The problem can be formulated as:

minimise: qA qB qC qD

under constraints:

• qA * 4 qC * 4 qD * 3 >= 40;
• qB * 5 qC * 4 qD * 3 >= 80;
• qA * 4 qB * 5 qD * 3 >= 60.
• qA >= 0, qB >= 0, qC >= 0, qD >= 0.

In python, there is scipy.optimize.linprog which will solve these kinds of problems for you.

• https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html

from scipy.optimize import linprog
from numpy import array

c = array([1, 1, 1, 1])
A_ub = -array([[4,0,4,3],[0,5,4,3],[4,5,0,3]])
b_ub = -array([40, 80, 60])
res = linprog(c, A_ub=A_ub, b_ub=b_ub)

print('Results')
print('qA, qB, qC, qD =', res.x)
print('qA   qB   qC  qD =', res.fun)

Output:

qA, qB, qC, qD = [0.         8.         5.         6.66666667]
qA   qB   qC  qD = 19.666666666666668

Integer solution

If you want the extra constraints qA,qB,qC,qD are integers, then instead of a simple linear programming problem, we have an integer linear programming problem.

Integer linear programming looks similar to continuous linear programming; but under the hood:

• solving a continuous linear problem is done efficiently with real-numbers linear algebra;
• solving an integer linear problem requires solving an NP-hard combinatorial problem.

However, integer linear problems are so extensively used that optimisation techniques to try to solve practical problems despite the NP-hard theory have been developed and compiled into pretty efficient programming libraries. In the general case, there is no going around the fast that this is an NP-hard problem that can be intractable when the values become large; but with your small example it's still very easy.

Instead of using scipy.optimize.linprog, you'll have to use a dedicated mixed-integer linear programming library, for instance PuLP.

We'll define the same vectors and matrices as before, to represent the objective function and the constraints. However, pulp also allows a formulation with symbolic equations instead of matrices, which is maybe easier to read depending on your taste.

from pulp import LpProblem, LpMinimize, LpInteger, LpVariable
from pulp import LpStatus, value

problem = LpProblem('Minimum Combination', LpMinimize)

qA = LpVariable("quantity of A", 0, None, LpInteger)
qB = LpVariable("quantity of B", 0, None, LpInteger)
qC = LpVariable("quantity of C", 0, None, LpInteger)
qD = LpVariable("quantity of D", 0, None, LpInteger)

problem  = qA   qB   qC   qD, 'Number of multisets'

problem  = qA * 4   qC * 4   qD * 3 >= 40, 'X target'
problem  = qB * 5   qC * 4   qD * 3 >= 80, 'Y target'
problem  = qA * 4   qB * 5   qD * 3 >= 60, 'Z target'

problem.solve()

print("Status:", LpStatus[problem.status])

for q in problem.variables():
    print(q.name, "=", q.varValue)

print("Total number of multisets = ", value(problem.objective))

Output:

Status: Optimal
quantity_of_A = 0
quantity_of_B = 8
quantity_of_C = 5
quantity_of_D = 7
Total number of multisets =  20

From continuous to integer?

If you start with the continuous solution that we found with scipy.optimize.linprog, which was (0,8,5,6.6667), and round up all the variables to integers, then you'll have a solution to the integer problem, (0,8,5,7).

In this case, that solution happens to be the same as the optimal solution to the integer problem found by pulp.

However, in general:

• rounding a solution of the continuous problem gives a solution to the integer problem; but
• there is no guarantee that rounding an optimal solution to the continuous problem will give an optimal solution to the integer problem.

So, in this case, if we had only used scipy and then rounded the variables up, we would have known that there is a solution with objective value 20, which is already better than the 21 you found; but we wouldn't have known whether 20 was optimal or not.

By using pulp, we made sure that 20 is indeed optimal.