Algorithm: maximize sum of increasing functions

[Pereskia]

Hi!

(Not sure which forum to pick for this question. This looked like the best one. I apologies if it is not)

I have a number of functions (say m functions) with integer domain. All functions are increasing. (Increasing in the sense not decreasing, $f(n+1) \ge f(n)$.) I want an algorithm to find $n_i$ for $1 \le i \le m$ such that $\sum_i^m n_i \le N$ that maximizes $\sum_i^m f(n_i)$.

$m$ is usually small (2 or 3) but can be larger as well and $m$ = 2 can be solved reasonably fast by exhaustive search, $m\ge3$ takes more time. Typically $N\approx 500$.

Is there any known algorithm?

Regards
David

 

[I like Serena]

Hi!

(Not sure which forum to pick for this question. This looked like the best one. I apologies if it is not)

I have a number of functions (say m functions) with integer domain. All functions are increasing. (Increasing in the sense not decreasing, $f(n+1) \ge f(n)$.) I want an algorithm to find $n_i$ for $1 \le i \le m$ such that $\sum_i^m n_i \le N$ that maximizes $\sum_i^m f(n_i)$.

$m$ is usually small (2 or 3) but can be larger as well and $m$ = 2 can be solved reasonably fast by exhaustive search, $m\ge3$ takes more time. Typically $N\approx 500$.

Is there any known algorithm?

Regards
David

Hi Pereskia! Welcome to MHB! (Wave)

How do the different functions tie in?
I only see the single $f$, so we seem to have $m$ numbers instead of $m$ functions.

 

[Pereskia]

Hi!

Sorry, I want to maximize $\sum_{i=1}^m f_i(n_i)$. I lost the index $i$.

Regards
David

 

[I like Serena]

Then I think you are looking for the Downhill Simplex method (Nelder-Mead), which is also called the Amoeba method.

 

[Pereskia]

Then I think you are looking for the Downhill Simplex method (Nelder-Mead), which is also called the Amoeba method.

Thank you. I will add this method to my tool box.

I will however need the optimum in this case. It will be one part of a larger optimization algorithm. I don't know how the other parts will work with heuristic solutions to the subproblems.

Regards
David