A decomposition algorithm for nested resource allocation problems

DOI10.1137/140965119MaRDI QIDQ2810553zbMATH OpenOpenAlexFDO

Authors T. Vidal, Patrick Jaillet, Nelson Maculan

Publication date 3 June 2016

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

resource allocationlot sizingseparable convex optimizationspeed optimizationnested constraintsproject crashing

Mathematics Subject Classification ID

Convex programming (90C25) Deterministic scheduling theory in operations research (90B35) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Convex functions and convex programs in convex geometry (52A41) Transportation, logistics and supply chain management (90B06)

Abstract: We propose an exact polynomial algorithm for a resource allocation problem with convex costs and constraints on partial sums of resource consumptions, in the presence of either continuous or integer variables. No assumption of strict convexity or differentiability is needed. The method solves a hierarchy of resource allocation subproblems, whose solutions are used to convert constraints on sums of resources into bounds for separate variables at higher levels. The resulting time complexity for the integer problem is $O(nlogmlog(B/n))$, and the complexity of obtaining an $epsilon$-approximate solution for the continuous case is $O(nlogmlog(B/epsilon))$, $n$ being the number of variables, $m$ the number of ascending constraints (such that $m<n$), $epsilon$ a desired precision, and $B$ the total resource. This algorithm attains the best-known complexity when $m=n$, and improves it when $logm=o(logn)$. Extensive experimental analyses are conducted with four recent algorithms on various continuous problems issued from theory and practice. The proposed method achieves a higher performance than previous algorithms, addressing all problems with up to one million variables in less than one minute on a modern computer.

Recommendations

• A faster algorithm for the resource allocation problem with convex cost functions
• A fast algorithm for quadratic resource allocation problems with nested constraints
• Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
• An efficient algorithm for the parametric resource allocation problem
• Algorithms for separable nonlinear resource allocation problems

Cites work

• scientific article; zbMATH DE number 3174053 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 544186 (Why is no real title available?)
• A Combinatorial Lemma for Complex Numbers
• A Dynamic Programming Solution to Cost-Time Tradeoff for CPM
• A Problem in Optimum Allocation
• A few remarks on the assortment problem
• A linear-time algorithm for a special case of disjoint set union
• A network flow computation for project cost curves
• A survey on the continuous nonlinear resource allocation problem
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
• 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 separable integer programming problem with cumulatively bounded variables
• Analysis of an exact algorithm for the vessel speed optimization problem
• Application of a technique for research and development program evaluation
• Bicriterion Single Machine Scheduling with Resource Dependent Processing Times
• Convex separable optimization is not much harder than linear optimization
• Decentralized Resource Allocation in Dynamic Networks of Agents
• Determination of optimal capacities of service for facilities with a linear measure of inefficiency
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient Algorithms for a Selection Problem with Nested Constraints and Its Application to a Production-Sales Planning Model
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• On Hochbaum's Proximity-Scaling Algorithm for the General Resource Allocation Problem
• On implementing a primal-dual interior-point method for conic quadratic optimization
• On solving convex optimization problems with linear ascending constraints
• PERT and crashing revisited: Mathematical generalizations
• Production Planning Over Time and the Nature of the Expectation and Planning Horizon
• Random convex hulls and extreme value statistics
• Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case
• Separable convex optimization problems with linear ascending constraints
• The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
• The Theory of Dynamic Programming as Applied to a Smoothing Problem
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• The vehicle routing problem with flexible time windows and traveling times

Cited in

(11)

• A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints
• Resource allocation problems in decentralized energy management
• Algorithms for separable convex optimization with linear ascending constraints
• Separable convex resource allocation problem with \(L_1\)-distance constraint
• A fast algorithm for quadratic resource allocation problems with nested constraints
• Solving nested-constraint resource allocation problems with an interior point method
• A faster algorithm for the resource allocation problem with convex cost functions
• scientific article; zbMATH DE number 6796293 (Why is no real title available?)
• scientific article; zbMATH DE number 4001887 (Why is no real title available?)
• Decomposition of uniform resource allocation problems
• On a Reduction for a Class of Resource Allocation Problems

This page was built for publication: A decomposition algorithm for nested resource allocation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810553)