Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies

DOI10.1016/J.EJOR.2015.01.029zbMATH Open1346.90672arXiv1501.07035OpenAlexW2009650852MaRDI QIDQ319183FDOQ319183

Authors: Michael Patriksson, Christoffer Strömberg 

Publication date: 6 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1501.07035

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

zbMATH Keywords

applicationsconvex optimizationnumerical analysisresource allocationLagrangian duality

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonlinear programming (90C30) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cites Work

• Title not available (Why is that?)
• Benchmarking optimization software with performance profiles.
• Title not available (Why is that?)
• An iterative row-action method for interval convex programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A library for continuous convex separable quadratic knapsack problems
• Validation of subgradient optimization
• Algorithms for bound constrained quadratic programming problems
• A survey on the continuous nonlinear resource allocation problem
• Handbook of optimization. From classical to modern approach
• A special newton-type optimization method
• Title not available (Why is that?)
• Linear probing and graphs
• Title not available (Why is that?)
• Solving Bicriterion Mathematical Programs
• A finite algorithm for finding the projection of a point onto the canonical simplex of \({\mathbb R}^ n\)
• The nonlinear knapsack problem - algorithms and applications
• Breakpoint searching algorithms for the continuous quadratic knapsack problem
• New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
• On Floyd and Rivest's SELECT algorithm
• A polynomially bounded algorithm for a singly constrained quadratic program
• A Newton's method for the continuous quadratic knapsack problem
• An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
• Variable fixing algorithms for the continuous quadratic Knapsack problem
• On the continuous quadratic knapsack problem
• Allocation of resources according to a fractional objective
• Quadratic resource allocation with generalized upper bounds
• An \(O(n)\) algorithm for projecting a vector on the intersection of a hyperplane and a box in \(\mathbb R^n\)
• Nonlinear integer programming for optimal allocation in stratified sampling
• Solving the continuous nonlinear resource allocation problem with an interior point method
• A linear-time median-finding algorithm for projecting a vector on the simplex of \({\mathbb{R}}^ n\)
• Optimal tax depreciation lives and charges under regulatory constraints
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• A Newton-type algorithm for solving problems of search theory
• Constrained multi-item inventory systems: An implicit approach
• On linear-time algorithms for the continuous quadratic Knapsack problem
• Production and inventory management under multiple resource constraints
• Convergent Lagrangian heuristics for nonlinear minimum cost network flows
• Towards strong duality in integer programming
• An approximate dynamic programming approach to convex quadratic knapsack problems
• Algorithms for separable nonlinear resource allocation problems
• The theory of search: optimum distribution of search effort
• Dual Ascent Methods for Problems with Strictly Convex Costs and Linear Constraints: A Unified Approach
• Resource allocation in multisite service systems with intersite customer flows
• A Parallel Projection for the Multicommodity Network Model
• Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
• A lagrangean relaxation algorithm for the constrained matrix problem
• Convex quadratic programming with one constraint and bounded variables
• Quasi-Newton Updates with Bounds
• Tradeoff Curves, Targeting and Balancing in Manufacturing Queueing Networks
• Title not available (Why is that?)
• Efficient Algorithms for a Selection Problem with Nested Constraints and Its Application to a Production-Sales Planning Model
• Technical Note—Computational Comparison among Three Multicommodity Network Flow Algorithms
• Simple Ranking Methods for Allocation of One Resource
• Disaggregation and Resource Allocation Using Convex Knapsack Problems with Bounded Variables
• Solution techniques for some allocation problems
• Computational development of a lagrangian dual approach for quadratic networks
• Massively Parallel Algorithms for Singly Constrained Convex Programs
• Technical Note—Allocation of Effort Resources among Competing Activities
• A Branch and Bound Procedure for a Class of Discrete Resource Allocation Problems with Several Constraints
• Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems
• HEURISTIC AND EXACT SOLUTION METHOD FOR CONVEX NONLINEAR KNAPSACK PROBLEM
• Minimizing Single-Machine Completion Time Variance
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
• A Projection Method for the Integer Quadratic Knapsack Problem
• The Nonlinear Resource Allocation Problem
• The optimum distribution of effort
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex separable minimization subject to bounded variables
• A pegging algorithm for the nonlinear resource allocation problem
• Linear time algorithms for some separable quadratic programming problems
• A breakpoint search approach for convex resource allocation problems with bounded variables
• Semismooth support vector machines.
• An O(n) algorithm for quadratic knapsack problems
• Convex programming with single separable constraint and bounded variables
• A unified method for a class of convex separable nonlinear knapsack problems

Cited In (35)

• 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 level-set method for convex optimization with a feasible solution path
• A penalty algorithm for solving convex separable knapsack problems
• Resource allocation problems in decentralized energy management
• 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
• The Nonlinear Resource Allocation Problem
• A two-phase method for solving continuous rank-one quadratic knapsack problems
• Fast projection onto the simplex and the \(l_1\) ball
• Continuous equality knapsack with probit-style objectives
• On the optimal design of the randomized unbiased Monte Carlo estimators
• A fast algorithm for quadratic resource allocation problems with nested constraints
• A breakpoint search approach for convex resource allocation problems with bounded variables
• 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
• An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives
• Algorithms for separable nonlinear resource allocation problems

Uses Software

• NAPHEAP

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)