A branch and search algorithm for a class of nonlinear knapsack problems

doi:10.1016/0167-6377(83)90047-0

Operations Research Letters

Volume 2, Issue 4, November 1983, Pages 155-160

https://doi.org/10.1016/0167-6377(83)90047-0 Get rights and content

Abstract

This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.

References (6)

M.W. Cooper
Survey of methods for pure nonlinear integer programming
Management Science
(1981)
B. Faaland
An integer programming algorithm for portfolio selection
Management Science
(1974)
H. Greenberg et al.
A branch and search algorithm for the knapsack problem
Management Science
(1970)

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

Cited by (43)

A general purpose exact solution method for mixed integer concave minimization problems
2023, European Journal of Operational Research
In this article, we discuss an exact algorithm for solving mixed integer concave minimization problems. A piecewise inner-approximation of the concave function is achieved using an auxiliary linear program that leads to a bilevel program, which provides a lower bound to the original problem. The bilevel program is reduced to a single level formulation with the help of Karush–Kuhn–Tucker (KKT) conditions. Incorporating the KKT conditions lead to complementary slackness conditions that are linearized using BigM, for which we identify a tight value for general problems. Multiple bilevel programs, when solved over iterations, guarantee convergence to the exact optimum of the original problem. Though the algorithm is general and can be applied to any optimization problem with concave function(s), in this paper, we solve two common classes of operations and supply chain problems; namely, the concave knapsack problem, and the concave production-transportation problem. The computational experiments indicate that our proposed approach outperforms the customized methods that have been used in the literature to solve the two classes of problems by an order of magnitude in most of the test cases.
A branch-and-bound algorithm for the quadratic multiple knapsack problem
2022, European Journal of Operational Research
Citation Excerpt :
Productivity in this application depends on the individual productivity of each person, as well as on the pairwise productivities of team members. Other applications can be found in capacity planning in computer networks (Gerla, Kleinrock, & Gerla, 1977), capital budgeting (Mathur, Salkin, & Morito, 1983), product-distribution system design (Elhedhli & Coffin, 2005), and in the steel industry (Dawande, Kalagnanam, Keskinocak, Ravi, & Salman, 2000). Since the work of Hiley & Julstrom (2006), who introduced a greedy heuristic, a hill-climbing algorithm, and a genetic algorithm, several heuristic approaches have been proposed.
We present a new branch-and-bound algorithm for the Quadratic Multiple Knapsack Problem. A key component of our algorithm is a new upper bound that divides the pairwise item values among individual items, estimates the maximum potential value contributed by each individual item, and calculates the upper bound via a transportation model. A local search is used to adjust the division of pairwise item values in order to improve the upper bound. Reduced costs from the solution of the transportation problem are used to forbid some item-to-knapsack assignments. Information from the upper bound is also used in selecting the item to branch on next. Computational experiments are carried out on three sets of benchmark instances from the literature, two sets of smaller instances with 20–35 items and 3–10 knapsacks per instance, and one set of larger instances with 40–60 items and 3–10 knapsacks per instance. Our algorithm finds and verifies optimal solutions for all small benchmark instances in less than one hour of CPU time apiece and outperforms the best previously proposed algorithms for the problem in terms of both the average computation time and the number of instances for which optimality is verified. For the larger benchmark instances, our algorithm obtains smaller average gaps than the best previously proposed methods.
Indefinite multi-constrained separable quadratic optimization: Large-scale efficient solution
2019, European Journal of Operational Research
Citation Excerpt :
Quadratic programming with one negative eigenvalue is NP-hard (Pardalos & Vavasis, 1991), and thus, solving the problem even with a single knapsack constraint is notoriously difficult (Sahni, 1974; Vavasis, 1992b). Yet, such problems are of immense importance in varied applications, such as capacity planning in computer networks (Gerla & Kleinrock, 1977), capital budgeting (Mathur, Salkin, & Morito, 1983), and production-distribution system design (Elhedhli & Goffin, 2005). Furthermore, the class of problems addressed in this paper can also serve as a basic building block for solving discrete optimization models (Nakagawa, James, Rego, & Edirisinghe, 2014).
Multi-constrained indefinite separable quadratic optimization occurs in many practical applications. However, it is an NP-hard problem and its solution even for problems of moderate size is computationally tedious. Extending our previous work on singly constrained problems, we develop the necessary theory and computational procedures for problems with multiple linear constraints, by employing iterative constraint aggregation, known as surrogation. The surrogate dual solution is obtained using a cutting plane technique over the multiplier search space, which then is used to develop a monotonic sequence of upper bounds that yields a near-global optimal solution. A detailed numerical analysis indicates the method is extremely efficient for quadratic programs with hundreds of thousands of variables. While the number of constraints affects the computational efficiency, it is still an order of magnitude superior, both in speed and quality, compared to leading commercial global optimization software. Preliminary results with application to mixed integer quadratic indefinite optimization further reveal the performance superiority of the proposed methodology relative to the standard techniques.
Inverse optimization for linearly constrained convex separable programming problems
2010, European Journal of Operational Research
Citation Excerpt :
In this paper, we will study inverse problem of another type of continuous optimization problems: the convex separable programming (CSP) problems. Separable programs are an important class of nonlinear optimization problems which arise from many industrial and managerial areas, for example, production and inventory management [5,8,30,44,52], allocation of resources [5,25,28,53], facility location [42], nonlinear knapsack problems [7,9,31,35,36,38,40,43], agricultural price-endogenous sector modelling [32], stratified sampling [13], optimal design of queueing network models in manufacturing [6], computer systems [16], and so on. Separable programs are nonlinear optimization problems in which the objective function and/or constraints can be expressed as the sum of nonlinear functions, and each nonlinear term involves only one variable.
In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with $ℓ_{1}$ and $ℓ_{2}$ norms. These inverse optimization problems are either linear programming when $ℓ_{1}$ norm is used in the formulation, or convex quadratic separable programming when $ℓ_{2}$ norm is used.
Solving knapsack problems with S-curve return functions
2009, European Journal of Operational Research
Citation Excerpt :
A number of efficient procedures have been developed subsequent to this for solving single-resource-allocation problems under objective function and constraint assumptions that lead to convex programming problems, including Zipkin [29], Bitran and Hax [3], Bretthauer and Shetty [4,5], and Kodialam and Luss [15]. In addition, several papers have focused on non-linear knapsack problems satisfying these convexity assumptions, when the variables must take integer values, including Hochbaum [11], Mathur et al. [19], and Bretthauer and Shetty [4,5]. Surprisingly little literature exists on continuous knapsack problems involving the minimization of a concave objective function (where the KKT conditions are not sufficient for optimality).
We consider the allocation of a limited budget to a set of activities or investments in order to maximize return from investment. In a number of practical contexts (e.g., advertising), the return from investment in an activity is effectively modeled using an S-curve, where increasing returns to scale exist at small investment levels, and decreasing returns to scale occur at high investment levels. We demonstrate that the resulting knapsack problem with S-curve return functions is NP-hard, provide a pseudo-polynomial time algorithm for the integer variable version of the problem, and develop efficient solution methods for special cases of the problem. We also discuss a fully-polynomial-time approximation algorithm for the integer variable version of the problem.
A survey on the continuous nonlinear resource allocation problem
2008, European Journal of Operational Research
Our problem of interest consists of minimizing a separable, convex and differentiable function over a convex set, defined by bounds on the variables and an explicit constraint described by a separable convex function. Applications are abundant, and vary from equilibrium problems in the engineering and economic sciences, through resource allocation and balancing problems in manufacturing, statistics, military operations research and production and financial economics, to subproblems in algorithms for a variety of more complex optimization models. This paper surveys the history and applications of the problem, as well as algorithmic approaches to its solution. The most common techniques are based on finding the optimal value of the Lagrange multiplier for the explicit constraint, most often through the use of a type of line search procedure. We analyze the most relevant references, especially regarding their originality and numerical findings, summarizing with remarks on possible extensions and future research.

View all citing articles on Scopus

^☆: Part of this work was supported by the Office of Naval Research under ONR contract No. N00014-78-C-0028.

View full text

A branch and search algorithm for a class of nonlinear knapsack problems☆

Abstract

Survey of methods for pure nonlinear integer programming

Management Science

An integer programming algorithm for portfolio selection

Management Science

A branch and search algorithm for the knapsack problem

Management Science