Solving the continuous nonlinear resource allocation problem with an interior point method

DOI10.1016/J.ORL.2014.07.001MaRDI QIDQ1785268zbMATH OpenOpenAlexWikidataFDO

Authors Stephen E. Wright, James J. Rohal

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

interior point methodsconvex programmingcontinuous knapsack

Mathematics Subject Classification ID

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

Abstract: Resource allocation problems are usually solved with specialized methods exploiting their general sparsity and problem-specific algebraic structure. We show that the sparsity structure alone yields a closed-form Newton search direction for the generic primal-dual interior point method. Computational tests show that the interior point method consistently outperforms the best specialized methods when no additional algebraic structure is available.

Recommendations

• Solving nested-constraint resource allocation problems with an interior point method
• Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
• Solving a nonlinear integer program for allocating resources
• A survey on the continuous nonlinear resource allocation problem
• Augmented Lagrangian algorithms for solving the continuous nonlinear resource allocation problem
• The Nonlinear Resource Allocation Problem
• A specially structured nonlinear integer resource allocation problem
• scientific article; zbMATH DE number 970360
• An interior point method for the nonlinear complementarity problem
• scientific article; zbMATH DE number 1097715

Cites work

• A Newton's method for the continuous quadratic knapsack problem
• A Newton-type algorithm for solving problems of search theory
• A survey on the continuous nonlinear resource allocation problem
• An Efficient Method for a Class of Continuous Nonlinear Knapsack Problems
• An O(n) algorithm for quadratic knapsack problems
• An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
• Breakpoint searching algorithms for the continuous quadratic knapsack problem
• Massively Parallel Algorithms for Singly Constrained Convex Programs
• On the continuous quadratic knapsack problem
• Solving certain singly constrained convex optimization problems in production planning

Cited in

(6)

• Solving nested-constraint resource allocation problems with an interior point method
• The Nonlinear Resource Allocation Problem
• A penalty algorithm for solving convex separable knapsack problems
• A Newton-type algorithm for solving problems of search theory
• Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies
• On a Reduction for a Class of Resource Allocation Problems

Describes a project that uses

Uses Software

• NAPHEAP

This page was built for publication: Solving the continuous nonlinear resource allocation problem with an interior point method

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