Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
From MaRDI portal
(Redirected from Publication:319183)
Abstract: Patriksson (2008) provided a then up-to-date survey on the continuous,separable, differentiable and convex resource allocation problem with a single resource constraint. Since the publication of that paper the interest in the problem has grown: several new applications have arisen where the problem at hand constitutes a subproblem, and several new algorithms have been developed for its efficient solution. This paper therefore serves three purposes. First, it provides an up-to-date extension of the survey of the literature of the field, complementing the survey in Patriksson (2008) with more then 20 books and articles. Second, it contributes improvements of some of these algorithms, in particular with an improvement of the pegging (that is, variable fixing) process in the relaxation algorithm, and an improved means to evaluate subsolutions. Third, it numerically evaluates several relaxation (primal) and breakpoint (dual) algorithms, incorporating a variety of pegging strategies, as well as a quasi-Newton method. Our conclusion is that our modification of the relaxation algorithm performs the best. At least for problem sizes up to 30 million variables the practical time complexity for the breakpoint and relaxation algorithms is linear.
Recommendations
- A pegging algorithm for the nonlinear resource allocation problem
- A survey on the continuous nonlinear resource allocation problem
- Algorithms for separable nonlinear resource allocation problems
- The Nonlinear Resource Allocation Problem
- Methods and algorithms for solving the resource allocation problem
Cites work
- scientific article; zbMATH DE number 3668345 (Why is no real title available?)
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 3807359 (Why is no real title available?)
- scientific article; zbMATH DE number 2124285 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- scientific article; zbMATH DE number 274399 (Why is no real title available?)
- scientific article; zbMATH DE number 3216838 (Why is no real title available?)
- scientific article; zbMATH DE number 6263683 (Why is no real title available?)
- scientific article; zbMATH DE number 3247810 (Why is no real title available?)
- scientific article; zbMATH DE number 3302125 (Why is no real title available?)
- scientific article; zbMATH DE number 3052220 (Why is no real title available?)
- scientific article; zbMATH DE number 3067835 (Why is no real title available?)
- A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
- A Branch and Bound Procedure for a Class of Discrete Resource Allocation Problems with Several Constraints
- A Newton's method for the continuous quadratic knapsack problem
- A Newton-type algorithm for solving problems of search theory
- A Parallel Projection for the Multicommodity Network Model
- A Projection Method for the Integer Quadratic Knapsack Problem
- A breakpoint search approach for convex resource allocation problems with bounded variables
- A finite algorithm for finding the projection of a point onto the canonical simplex of \({\mathbb R}^ n\)
- A lagrangean relaxation algorithm for the constrained matrix problem
- A library for continuous convex separable quadratic knapsack problems
- A linear-time median-finding algorithm for projecting a vector on the simplex of \({\mathbb{R}}^ n\)
- A pegging algorithm for the nonlinear resource allocation problem
- A polynomially bounded algorithm for a singly constrained quadratic program
- A special newton-type optimization method
- A survey on the continuous nonlinear resource allocation problem
- A unified method for a class of convex separable nonlinear knapsack problems
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- Algorithms for bound constrained quadratic programming problems
- Algorithms for separable nonlinear resource allocation problems
- Allocation of resources according to a fractional objective
- An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems
- An O(n) algorithm for quadratic knapsack problems
- An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in R^n
- An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
- An approximate dynamic programming approach to convex quadratic knapsack problems
- An iterative row-action method for interval convex programming
- Benchmarking optimization software with performance profiles.
- Breakpoint searching algorithms for the continuous quadratic knapsack problem
- Computational development of a lagrangian dual approach for quadratic networks
- Constrained multi-item inventory systems: An implicit approach
- Convergent Lagrangian heuristics for nonlinear minimum cost network flows
- Convex programming with single separable constraint and bounded variables
- Convex quadratic programming with one constraint and bounded variables
- Convex separable minimization subject to bounded variables
- Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables
- Dual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach
- Efficient Algorithms for a Selection Problem with Nested Constraints and Its Application to a Production-Sales Planning Model
- HEURISTIC AND EXACT SOLUTION METHOD FOR CONVEX NONLINEAR KNAPSACK PROBLEM
- Handbook of optimization. From classical to modern approach
- Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
- Linear probing and graphs
- Linear time algorithms for some separable quadratic programming problems
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
- Massively Parallel Algorithms for Singly Constrained Convex Programs
- Minimizing Single-Machine Completion Time Variance
- New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
- Nonlinear integer programming for optimal allocation in stratified sampling
- On Floyd and Rivest's SELECT algorithm
- On linear-time algorithms for the continuous quadratic Knapsack problem
- On the continuous quadratic knapsack problem
- Optimal tax depreciation lives and charges under regulatory constraints
- Production and inventory management under multiple resource constraints
- Quadratic resource allocation with generalized upper bounds
- Quasi-Newton Updates with Bounds
- Resource allocation in multisite service systems with intersite customer flows
- Semismooth support vector machines.
- Simple Ranking Methods for Allocation of One Resource
- Solution techniques for some allocation problems
- Solving Bicriterion Mathematical Programs
- Solving the continuous nonlinear resource allocation problem with an interior point method
- Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
- Technical Note—Allocation of Effort Resources among Competing Activities
- Technical Note—Computational Comparison among Three Multicommodity Network Flow Algorithms
- The Nonlinear Resource Allocation Problem
- The nonlinear knapsack problem - algorithms and applications
- The optimum distribution of effort
- The theory of search: optimum distribution of search effort
- Towards strong duality in integer programming
- Tradeoff Curves, Targeting and Balancing in Manufacturing Queueing Networks
- Validation of subgradient optimization
- Variable fixing algorithms for the continuous quadratic Knapsack problem
Cited in
(35)- An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives
- Algorithms for separable nonlinear resource allocation problems
- On the paper ``Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem
- Methods and algorithms for solving the resource allocation problem
- A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints
- Variable fixing method by weighted average for the continuous quadratic knapsack problem
- On Hochbaum's Proximity-Scaling Algorithm for the General Resource Allocation Problem
- A centre-free approach for resource allocation with lower bounds
- A penalty algorithm for solving convex separable knapsack problems
- Resource allocation problems in decentralized energy management
- A level-set method for convex optimization with a feasible solution path
- A decomposition algorithm for nested resource allocation problems
- A feasibility-ensured Lagrangian heuristic for general decomposable problems
- Addendum: A Finite Algorithm for Solving Nonlinear Allocation Problems
- Fast projection onto the simplex and the l₁ ball
- The Nonlinear Resource Allocation Problem
- A two-phase method for solving continuous rank-one quadratic knapsack problems
- On the optimal design of the randomized unbiased Monte Carlo estimators
- Continuous equality knapsack with probit-style objectives
- A breakpoint search approach for convex resource allocation problems with bounded variables
- A fast algorithm for quadratic resource allocation problems with nested constraints
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- A pegging algorithm for the nonlinear resource allocation problem
- Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem
- Solving nested-constraint resource allocation problems with an interior point method
- A survey on the continuous nonlinear resource allocation problem
- Allocating resources via price management systems: a dynamic programming-based approach
- Solving the continuous nonlinear resource allocation problem with an interior point method
- A Newton-type algorithm for solving problems of search theory
- Resource allocation problems with expensive function evaluations
- A distributed primal-dual hybrid gradient algorithm for fair resource allocation
- Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time
- Minimum variance allocation among constrained intervals
- COMPUTING OPTIMAL ALLOCATIONS FOR DISCRETE‐TIME NONLINEAR NATURAL RESOURCE MODELS
- On a Reduction for a Class of Resource Allocation Problems
This page was built for publication: Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q319183)
