1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The most suitable technique will probably depend on the nature of the functions $f_i,g_j$. The more you can tell us about them, the more likely that we can suggest relevant techniques. Also, are you looking for the optimal solution, or an approximation to it? This is related to the knapsack problem, and is at least as hard as the knapsack problem; you might look at techniques for that problem to get some ideas. $\endgroup$ – D.W. Oct 11 '17 at 21:42
  • $\begingroup$ non-negative non-decreasing is the only information I have. Can you some idea of what you were hoping for? $\endgroup$ – dineshdileep Oct 12 '17 at 4:23
  • $\begingroup$ If you have no information about the $f_i,g_i$, you can't solve the problem. How were you planning to solve the problem without knowing what $f_i,g_i$ are? I'd recommend that your first step should be to go investigate what those functions are, where they come from, and how they will be specified in the inputs (as a truth table? some other way?). When dealing with a hard problem, it's important to have as much information as possible. $\endgroup$ – D.W. Oct 12 '17 at 6:07
  • $\begingroup$ @D.W. I have the complete values of $f_i$ and $g_i$ at all possible values of their arguments. So if $b\in\{5,6,\dots,5000\}$, then I know all values of $f_i(b)$ and $g_i(b)$ for all $i$. These are given as data to me. $\endgroup$ – dineshdileep Oct 12 '17 at 7:02
  • $\begingroup$ OK. Makes sense, thanks for the clarification. How large are the values of $f_i$, $g_i$, and $B$? In particular, about how large is $B$, in the applications you care about? $\endgroup$ – D.W. Oct 12 '17 at 15:42
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I fail to see why this is a version of ILP, if the functions $f_i,g_j$ aren't linear. $\endgroup$ – D.W. Oct 11 '17 at 21:41
  • $\begingroup$ I appologize. When I read non-decresing I tought immediately in a linear function. $\endgroup$ – klaus Oct 12 '17 at 22:02
  • $\begingroup$ But what are these functions like? It might be possible to convert it to linear form. If not, you can follow this path: Linear Programming -- (if not linear) --> Quadratic/Convex Optimization --(if not quadratic/convex) --> Non-linear optimization $\endgroup$ – klaus Oct 12 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.