On a discrete nonlinear and nonseparable knapsack problem (Q920849)

The author considers a problem of the type \[ (EXI):\;\text{ minimize } f(\hat x)=\sum_{j\in A}(p^*_ j-p_ j)\cdot \exp (-\sum_{k\in K}d_{jk}x_ k) \] subject to \(\sum \beta_ kx_ k\leq B\), \(x_ k=0,1,2,...\), \(\forall k\in K\), where \(p_ j\) is the initial probability and \(p^*_ j\) is the limiting probability \((p^*_ j>p_ j)\). This problem with \(x_ k\geq 0\), \(\forall k\in K\), and \(\sum \beta_ kx_ k=B\), is of the type (EX). To solve problem (EX), the quadratic knapsack problem (EXQ) is considered. On the basis of an algorithm solving (EX) a branch-and-bound algorithm for the solution of problem (EXI) is developed and computational results are presented. The algorithm obtained is an efficient algorithm to solve discrete nonlinear and nonseparable knapsack problems.