Solving a discrete optimization problem

Question

Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative functions of $x_i$. Values of both functions are given for all values of $x_i$. Now consider the optimization problem \begin{align}\max_{x_1,\dots,x_n}&\sum_jf_j(x_j) \\\text{s.t.}&\sum_jg_j(x_j)\leq B&\end{align}where $B$ is a given positive constant. The straightforward solution is to do a brute-force search. However, this will be exponentially complex. Is this problem studied in literature? What are the known approaches to this? If you are familiar with solution approaches or relevant references, please point them out.

Answer 1

Complexity

Your problem is NP-hard. Therefore, you should not expect any efficient algorithm that will always find the optimal solution.

In particular, your problem is a generalization of the knapsack problem. Suppose we insist that $f_i(5)=f_i(6)=\cdots=f_i(4999)=0$ for all $i$ (but $f_i(5000)$ can be any positive integer), and the same for the $g_i$. Then the problem becomes exactly the knapsack problem. In particular, the knapsack problem is a special case of your problem, which means your problem is at least as hard as the knapsack problem, as any algorithm for your problem could also be used to solve the knapsack problem. Moreover, the knapsack problem is NP-hard, so your problem is too.

Therefore, you're going to have to make some compromises. You could look for heuristics that produce the optimal solution and sometimes run fast, but in the worst case might take exponential time. Or, you could look for heuristics that produce an approximate solution (not optimal, but hopefully close to it). I'll outline several approaches.

Exact solutions

Suppose you want the exact optimum solution. Then I know of two reasonable approaches, depending on how large $B$ is.

If $B$ is small, you can adapt the standard dynamic programming algorithm for the knapsack problem to this situation. The running time will be roughly proportional to $B$, so if $B$ is not too large, this is reasonable, but if $B$ is a 100-bit integer, this is completely infeasible.

Alternatively, you can use integer linear programming. Introduce zero-or-one variables $v_{i,k}$, with the intended meaning that $v_{i,k}=1$ means that you've set $x_i$ to $k$. Add constraints to ensure that $x_i$ is set to a single value ($v_{i,5} + \dots + v_{i,5000}=1$) and that $g_1(x_1)+\dots+g_n(x_n)\le B$ (namely, $\sum_{i,k} v_{i,k} g_i(k) \le B$), and then maximize the objective function $\sum_{i,k} v_{i,k} f_i(k)$. Feed this to an off-the-shelf ILP solver, and it might find a solution for you, if you are lucky and the size of the problem is not too large.

Approximate solutions

If you're willing to accept an approximate solution that isn't necessarily optimal but should be close to optimal, there are several possible approaches.

One approach is to create the ILP problem above, run the ILP solver for a limited amount of time, then stop the solver and ask it to give you the best solution it has found so far. Many ILP solvers have the ability to do that.

Another approach is to round to a limited precision. Pick a constant $c>1$, and replace each $g_i(x)$ with $\lfloor g_i(x)/c \rfloor$ and replace $B$ with $\lfloor B/c \rfloor$. In other words, divide all the $g$'s and $B$ by $c$, and then round to an integer. Now solve the resulting problem. This is an instance of your problem, but with smaller numbers and a smaller $B$, so you can now try to find an exact solution to this smaller problem -- for instance, using dynamic programming. The optimal solution to this smaller problem will correspond to a close-to-optimal solution to the original problem. You can tune the value of $c$: the larger $c$ is, the more efficient this will be, but the worse the quality of the solution.

There may be other methods. You could study the literature on the knapsack problem to see what techniques have been considered there and see how to adapt them to your situation. But the above is probably a pretty good starting point.

Answer 2

Without more information about f and g, this problem is NP-hard to solve. The topic is quite broad, check the family of Branch and Bound algorithms, depending of additional information you can do better than NP-hard, in particular, it makes use of monotonicity to guide its search.

Worth to mention too are Genetic algorithms and Simulated Annealing, which, in general, gives you a good enough solution.

Answer 3

This problem is well studied in the literature, and is the integer version of Linear Programming, known as Integer Linear Programming.

You can use a solver for Linear Programming problems. There are free options, like GLPK, or COIN. There are some APIs that use these solvers available for Python, Java, etc... Most of them support integer variables/sets like your problem.