Continuous linear knapsack problems revisited
*Stefan M. StefanovCorresponding authorstefm@swu.bgDepartment of MathematicsSouth-West University “Neofit Rilski”Blagoevgrad, 2700, BulgariaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 05 Apr 2022
- Published Online:
- 10 Oct 2023
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1184
- Pages:
- 909–922
Abstract
Keywords
Subject Classifications
References
[1] G. R. Bitran and A. C. Hax, “Disaggregation and resource allocation using convex knapsack problems with bounded variables”, Management Science, Vol. 27(4), pp. 431-441 (1981).
[2] P. Brucker, “An O(n) algorithm for quadratic knapsack problems”, Operations Research Letters, Vol. 3(3), pp. 163-166 (1984).
[3] J.-P. Dussault, J. A. Ferland, and B. Lemaire, “Convex quadratic programming with one constraint and bounded variables”, Mathematical Programming, Vol. 36(1), pp. 90-104 (1986).
[4] R. Helgason, J. Kennington, and H. Lall, “A polynomially bounded algorithm for a singly constrained quadratic program”, Mathematical Programming, Vol. 18(3), pp. 338-343 (1980).
[5] N. Katoh, T. Ibaraki, and H. Mine, “A polynomial time algorithm for the resource allocation problem with a convex objective function”, Journal of the Operational Research Society, Vol. 30(5), pp. 449-455 (1979).
[6] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, Springer, Berlin–Heidelberg (2004).
[7] H. Luss and S. K. Gupta, “Allocation of effort resources among competing activities”, Operations Research, Vol. 23(2), pp. 360-366 (1975).
[8] J. J. Moré and G. Toraldo, “Algorithms for bound constrained quadratic programming problems”, Numerische Mathematik, Vol. 55(4), pp. 377-400 (1989).
[9] P. M. Pardalos and N. Kovoor, “An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds”, Mathematical Programming, Vol. 46(3), pp. 321-328 (1990).
[10] P. M. Pardalos, Y. Ye, and C.-G. Han, “Algorithms for the solution of quadratic knapsack problems”, Linear Algebra and Its Applications, Vol. 152, pp. 69-91 (1991).
[11] A. G. Robinson, N. Jiang, and C. S. Lerme, “On the continuous quadratic knapsack problem”, Mathematical Programming, Vol. 55(1), pp. 99-108 (1992).
[12] S. M. Stefanov, A Lagrangian Dual Method for Solving Variational Inequalities, Kluwer Series in Mathematical Programming and Operations Research, Working Paper WP-KSMPOR-99-11, 10 pp (February 1999).
[13] S. M. Stefanov, On the Solution of Variational Inequality Problems by Using Cutting Plane Methods, Kluwer Series in Mathematical Programming and Operations Research, Working Paper WP-KSMPOR-99-12, 9 pp (February 1999).
[14] S. M. Stefanov, “On the implementation of stochastic quasigradient methods to some facility location problems”, Yugoslav Journal of Operations Research, Vol. 10(2), pp. 235-256 (2000).
[15] S. M. Stefanov, Convex Separable Programming: Theory and Methods, Kluwer Academic Publishers, Dordrecht-Boston-London (2000).
[16] S. M. Stefanov, “Convex separable minimization subject to bounded variables”, Computational Optimization and Applications. An International Journal, Vol. 18(1), pp. 27-48 (2001).
[17] S. M. Stefanov, “Polynomial algorithms for projecting a point onto a region defined by a linear constraint and box constraints in ”, Journal of Applied Mathematics, Vol. 2004(5), pp. 409-431 (2004).
[18] S. M. Stefanov, “An efficient method for minimizing a convex separable logarithmic function subject to a convex inequality constraint or linear equality contraint”, Journal of Applied Mathematics and Decision Sciences, Vol. 2006, 19 pages, Article ID 89307 (2006).
[19] S. M. Stefanov, “Minimization of a convex linear-fractional separable function subject to a convex inequality constraint or linear equality constraint and bounds on the variables”, Applied Mathematics Research eXpress, Vol. 2006(4), 24 pages, Article ID 36581 (2006).
[20] S. M. Stefanov, “Minimization of a strictly convex separable function subject to convex separable inequality constraint and box constraints”, Journal of Interdisciplinary Mathematics, Vol. 12(5), pp. 647-673 (2009).
[21] S. M. Stefanov, “Solution of some convex separable resource allocation and production planning problems with bounds on the variables”, Journal of Interdisciplinary Mathematics, Vol. 13(5), pp. 541-569 (2010).
[22] S. M. Stefanov, “Well-posedness and primal-dual analysis of some convex separable optimization problems”, Advances in Operations Research, Vol. 2013, 10 pages, Article ID 279030 (2013).
[23] S. M. Stefanov, “On the solution of multidimensional convex separable continuous knapsack problem with bounded variables”, European Journal of Operational Research, vol 247(2), pp. 366-369 (2015).
[24] S. M. Stefanov, Separable Programming: Theory and Methods, 4th rev. enld. ed., Springer Science+Business Media, B.V., Dordrecht (2016).
[25] S. M. Stefanov, “Strictly convex separable optimization with linear equality constraints and bounded variables”, Journal of Statistics and Management Systems, Vol. 21(2), pp. 261-272 (2018).
[26] S. M. Stefanov, “Characterization of the optimal solution of the convex generalized nonlinear transportation problem”, Journal of Interdisciplinary Mathematics, Vol. 22(5), pp. 745-756 (2019).
[27] S. M. Stefanov, “Characterization of the optimal solution of the convex separable continuous knapsack problem and related problems”, Journal of Information and Optimization Sciences, Vol. 42(1), pp. 1-16 (2021).
[28] S. M. Stefanov, “On the numerical solution of separable stochastic inventory control problems”, Journal of Information and Optimization Sciences, Vol. 42(3), pp. 533-561 (2021).
[29] S. M. Stefanov, Separable Optimization: Theory and Methods, Springer Optimization and Its Applications, Vol. 177, Springer, Cham (2021).
[30] S. M. Stefanov, “Numerical solution of systems of non linear equations defined by convex functions”, Journal of Interdisciplinary Mathematics, Vol. 25(4), pp. 951-962 (2022).
[31] V. A. Yemelichev and V. I. Komlik, Method for Constructing Sequence of Feasible Solutions for Solving Discrete Optimization Problems, Nauka, Moscow, (in Russian) (1981).
