0

If I have a linear equation like

$$ c_1x_1 + c_2x_2 + ... + c_nx_n = m \leq M $$

with the constraint $x_i \in \mathbb{N}$ for $0 \le i \le n$, where $M$ and the $c_i$ are constants, and where the $c_i$ are rational, how do I maximize $m$?

A friend suggested looking at the least squares method, which I didn't really understand, or possibly at trying to find the least common multiple of a subset of the $c_i$ values and checking if that divides M, but that's a little more trial-and-error than I'm hoping for.

Note: I apologize if this has been answered elsewhere; I didn't see any solutions that matched this problem but I also didn't really know how to search for it.

mvw
  • 34,562
Ross Tajvar
  • 35
  • 4
  • 1
    What kind of numbers are the $c_i$? Does your $\mathbb{N}$ include $0$? So your $x_i$ are to be chosen optimal? – mvw Oct 15 '16 at 20:59
  • The $c_i$ are rational numbers and $\mathbb{N}$ does include 0. And yes, I want to pick the $x_i$ so that $m$ is as large as possible while still less than $M$. – Ross Tajvar Oct 15 '16 at 22:15

1 Answers1

1

Knowing your $\mathbb{N}$ does contain the zero, you can model this problem as integer linear program $$ \max_{x \in \mathbb{Z}^n} \left\{ c^\top x \mid A x \le b , x \ge 0\right\} $$ where $A = c^\top \in \mathbb{R}^{1 \times n}$ and $b = M \in \mathbb{R}^1$.

For an actual calculation, your could try standard software like lpsolve.

mvw
  • 34,562