A nonlinear Knapsack problem

doi:10.1016/0167-6377(95)00009-9

Operations Research Letters

Volume 17, Issue 3, April 1995, Pages 103-110

https://doi.org/10.1016/0167-6377(95)00009-9 Get rights and content

Abstract

The nonlinear Knapsack problem is to minimize a separable concave objective function, subject to a single “packing” constraint, in nonnegative variables. We consider this problem in integer and continuous variables, and also when the packing constraint is convex. Although the nonlinear Knapsack problem appears difficult in comparison with the linear Knapsack problem, we prove that its complexity is similar. We demonstrate for the nonlinear Knapsack problem in n integer variables and knapsack volume limit B, a fully polynomial approximation scheme with running time $O ̃ ((1/ε^{2}) (n + 1/ε^{2}))$ (omitting polylog terms); and for the continuous case an algorithm delivering an ε-accurate solution in O(n log(B/ε)) operations.

References (18)

P. Brucker
An O(n) algorithm for quadratic Knapsack problems
Oper. Res. Lett.
(1984)
G.N. Frederickson et al.
The complexity of selection and ranking in X + Y and matrices with sorted columns
J. Comput. Systems Sci.
(1982)
S. Martello et al.
Knapsack Problems: Algorithms and Computer Implementations
(1990)
K. Bretthauer et al.
The nonlinear resource allocation problem
(1993)
K. Bretthauer et al.
A branch and bound algorithm for integer quadratic knapsack problems
S. Cosares et al.
A strongly polynomial algorithm for the quadratic transportation problem with fixed number of suppliers
Math. Oper. Res.
(1994)
D.S. Hochbaum
Lower and upper bounds for the allocation problem and other nonlinear optimization problems
Math. Oper. Res.
(1994)
D.S. Hochbaum et al.
Convex separable optimization is not much harder than linear optimization
J. Assoc. Comput. Mach.
(1990)
O.H. Ibarra et al.
Fast approximation algorithms for the Knapsack and sum of subset problems
J. Assoc. Comput. Mach.
(1975)

There are more references available in the full text version of this article.

Cited by (92)

On the paper “Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem”
2024, European Journal of Operational Research
In the paper Torrealba et al. (2021) an augmented Lagrangian algorithm was proposed for resource allocation problems with the intriguing characteristic that instead of solving the box-constrained augmented Lagrangian subproblem, they propose projecting the solution of the unconstrained subproblem onto such box. A global convergence result for the quadratic case was provided, however, this is somewhat counterintuitive, as in usual augmented Lagrangian theory, this strategy can fail in solving the augmented Lagrangian subproblems. In this note we investigate further this algorithm and we show that the proposed method may indeed fail when the Hessian of the quadratic is not a multiple of the identity. In the paper, it is not clear enough that two different projections are being used: one for obtaining their convergence results and other in their implementation. However, despite the lack of theoretical convergence, their strategy works remarkably well in some classes of problems; thus, we propose a hybrid method which uses their idea as a starting point heuristics, switching to a standard augmented Lagrangian method under certain conditions. Our contribution consists in presenting an efficient way of determining when the heuristics is failing to improve the KKT residual of the problem, suggesting that the heuristic procedure should be abandoned. Numerical results are provided showing that this strategy is successful in accelerating the standard method.
Approximating single- and multi-objective nonlinear sum and product knapsack problems
2023, Discrete Optimization
We present a fully polynomial-time approximation scheme (FPTAS) for a very general version of the well-known knapsack problem. This generalization covers, with few exceptions, all versions of knapsack problems that have been studied in the literature so far and allows for an objective function consisting of sums or products of possibly nonlinear, separable item profits, while the knapsack constraint states an upper bound on the sum of possibly nonlinear, separable item weights. Moreover, we extend our FPTAS to a multi-objective fully polynomial-time approximation scheme (MFPTAS) for the multi-objective version of the problem.
As applications of our general algorithms, we obtain the first FPTAS for the recently-introduced 0–1 time-bomb knapsack problem as well as FPTASs for a variety of robust knapsack problems. Moreover, we extend our FPTAS to the minimization version of our general problem, which, in particular, allows us to explicitly state an FPTAS for the classical minimization knapsack problem, which has been missing in the literature so far.
Maximizing power production in path and tree riverine networks
2019, Sustainable Computing: Informatics and Systems
A majority of electricity generation in the US is produced by thermoelectric power plants which require a constant supply of water for cooling. Many of these plants consequently eject large quantities of hot water into an adjacent river, causing thermal pollution, which harms the local ecosystems and aquatic life. Plants commonly lie within interconnected river networks, whence thermal pollution from plants upstream flows to downstream plants, causing less-effective cooling, and decreases in efficiency. Plants are managed individually, and government regulations combating thermal pollution take the form of local river temperature constraints. We propose analyzing this situation regionally, as an optimization problem, where we seek to balance the trade-off between satisfying power demand and obeying temperature limits.
Our primary focus is fractional variants of this problem where we can specify the amount of power a plant will generate, up to its maximum capacity. After providing optimal schedules or algorithms for several special cases of this problem, we provide an optimal polynomial-time algorithm for this problem on river topologies taking the form of (a) a path graph and (b) a “merge-only” tree. We also investigate a 0/1 version of the problem (plants are either fully on or off), which is NP-hard already for path graphs. We provide a dynamic programming FPTAS for this case.
Finally, we carry out an extensive performance evaluation comparing our fractional optimal algorithms to baseline heuristics in simulation. These experiments are performed both on synthetically generated problem instances and on problem instances constructed using real-world river network data, in particular the power plant network along the Hudson River in New York State. These experiments provide insight as to when naive greedy algorithms diverge from the optimal and on which problem instance parameters optimal performance is more sensitive too.
Approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints
2018, European Journal of Operational Research
We consider a fairly general model of “take-or-leave” decision-making. Given a number of items of a particular weight, the decision-maker either takes (accepts) an item or leaves (rejects) it. We design fully polynomial-time approximation schemes (FPTASs) for optimization of a non-separable non-linear function which depends on which items are taken and which are left. The weights of the taken items are subject to nested constraints. There is a noticeable lack of approximation results on integer programming problems with non-separable functions. Most of the known positive results address special forms of quadratic functions, and in order to obtain the corresponding approximation algorithms and schemes considerable technical difficulties have to be overcome. We demonstrate how for the problem under consideration and its modifications FPTASs can be designed by using (i) the geometric rounding techniques, and (ii) methods of K-approximation sets and functions. While the latter approach leads to a faster scheme, the running times of both algorithms compare favorably with known analogues for less general problems.
Routing design and fleet allocation optimization of freeway service patrol: Improved results using genetic algorithm
2018, Physica A: Statistical Mechanics and its Applications
Freeway service patrol (FSP), is considered to be an effective method for incident management and can help transportation agency decision-makers alter existing route coverage and fleet allocation. This paper investigates the FSP problem of patrol routing design and fleet allocation, with the objective of minimizing the overall average incident response time. While the simulated annealing (SA) algorithm and its improvements have been applied to solve this problem, they often become trapped in local optimal solution. Moreover, the issue of searching efficiency remains to be further addressed. In this paper, we employ the genetic algorithm (GA) and SA to solve the FSP problem. To maintain population diversity and avoid premature convergence, niche strategy is incorporated into the traditional genetic algorithm. We also employ elitist strategy to speed up the convergence. Numerical experiments have been conducted with the help of the Sioux Falls network. Results show that the GA slightly outperforms the dual-based greedy (DBG) algorithm, the very large-scale neighborhood searching (VLNS) algorithm, the SA algorithm and the scenario algorithm.
Multi-channel sensing and resource allocation in energy constrained cognitive radio networks
2017, Physical Communication
We consider a cognitive radio network in a multi-channel licensed environment. Secondary user transmits in a channel if the channel is sensed to be vacant. This results in a tradeoff between sensing time and transmission time. When secondary users are energy constrained, energy available for transmission is less if more energy is used in sensing. This gives rise to an energy tradeoff. For multiple primary channels, secondary users must decide appropriate sensing time and transmission power in each channel to maximize average aggregate-bit throughput in each frame duration while ensuring quality-of-service of primary users. Considering time and energy as limited resources, we formulate this problem as a resource allocation problem. Initially a single secondary user scenario is considered and solution is obtained using decomposition and alternating optimization techniques. Later we extend the analysis for the case of multiple secondary users. Simulation results are presented to study effect of channel occupancy, fading and energy availability on performance of proposed method.

View all citing articles on Scopus

View full text

A nonlinear Knapsack problem

Abstract

Oper. Res. Lett.

J. Comput. Systems Sci.

The nonlinear resource allocation problem

A branch and bound algorithm for integer quadratic knapsack problems

A strongly polynomial algorithm for the quadratic transportation problem with fixed number of suppliers

Math. Oper. Res.

Lower and upper bounds for the allocation problem and other nonlinear optimization problems

Math. Oper. Res.

Convex separable optimization is not much harder than linear optimization

J. Assoc. Comput. Mach.

Fast approximation algorithms for the Knapsack and sum of subset problems

J. Assoc. Comput. Mach.