A branch and search algorithm for a class of nonlinear knapsack problems☆
References (6)
Survey of methods for pure nonlinear integer programming
Management Science
(1981)An integer programming algorithm for portfolio selection
Management Science
(1974)- et al.
A branch and search algorithm for the knapsack problem
Management Science
(1970)
Cited by (43)
A general purpose exact solution method for mixed integer concave minimization problems
2023, European Journal of Operational ResearchA branch-and-bound algorithm for the quadratic multiple knapsack problem
2022, European Journal of Operational ResearchCitation 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.
Indefinite multi-constrained separable quadratic optimization: Large-scale efficient solution
2019, European Journal of Operational ResearchCitation 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).
Inverse optimization for linearly constrained convex separable programming problems
2010, European Journal of Operational ResearchCitation 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.
Solving knapsack problems with S-curve return functions
2009, European Journal of Operational ResearchCitation 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).
A survey on the continuous nonlinear resource allocation problem
2008, European Journal of Operational Research
- ☆
Part of this work was supported by the Office of Naval Research under ONR contract No. N00014-78-C-0028.