System of equations with multiple answers, but only natural numbers (and other constraints)

88 Views Asked by At

Okay so basically I want the solution with the smallest sum when you add up the integer variable solutions that give a solution to:

$975a + 880b + 790c + 585d + 487e + 440f + 292g + 260h + 530i + 195j + 125k = 1002$

What I mean by this is, say we have one possible solution that's like $a = 1, b = 2, c = 3, d = e = \cdots = j = k = 0$ (which isn't a solution to the problem I gave, of course), the sum of these is $6$. Out of all the possible solutions, I would like the one that gives the smallest sum in this manner.

On top of this, the second restraint(s?) is:

$0 \leq a \leq 27 \\ 0 \leq b \leq 37 \\ 0 \leq c \leq 14 \\ 0 \leq d \leq 15 \\ 0 \leq e \leq 1 \\ 0 \leq f \leq 2 \\ 0 \leq g \leq 1 \\ 0 \leq h \leq 6 \\ 0 \leq i \leq 1 \\ j \in \mathbb{N} \\ k \in \mathbb{N}$

(So $j$ and $k$ can be any natural number including $0$, and everything else is a natural number within these respective given ranges.)

How would I go about finding this answer with the constraints?

1

There are 1 best solutions below

4
On

Linear optimization problems with integer variables are called "integer (linear) programming" and this one is also a variation on the Knapsack and Bin Packing problems.

The number of possible assignments of the variables is on the order of thousands. That is small enough to check exhaustively without running an IP solver.