An algorithm for solving a structured class of linear programming problems

DOI10.1016/0167-6377(86)90032-5MaRDI QIDQ1078069zbMATH OpenOpenAlexFDO

Authors S. Selcuk Erenguc

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0167-6377(86)90032-5

zbMATH Keywords

advertisingintervalknapsacklinear programmingportfolio selectionproduction planningsequence of continuous knapsack problemsspecially structured linear programsweighted selection algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Applications of mathematical programming (90C90)

Review text

The author presents a procedure for solving the following class of specially structured linear programs: maximize \(Z_{PN}=\sum_{j\in J}c_ jx_ j\) subject to \(\ell_ i\leq \sum_{i\in J(i)}a_ jx_ j\leq b_ i,\) \(i=1,2,...,m,\) \(d_ j\leq x_ j\leq u_ j,\) \(j\in J,\) where \(b_ i,\) \(c_ j\) and \(a_ j\) are positive and \(d_ j\) are nonnegative scalars, \(J=\cup^{m}_{i=1}J(i)\) and the sets J(i) are assumed to be nested: if \(i\neq k\) then either J(i) and J(k) are disjoint or one set is properly contained in the other. The proposed algorithm consists of solving a sequence of continuous knapsack problems each of which requires linear time to solve. The computational effort required by the procedure is proportional to the number of non-zero entries in the constant matrix.

Recommendations

• scientific article; zbMATH DE number 4143769
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• An O(n log n)-algorithm for solving a special class of linear programs
• An efficient algorithm for solving a special class of LP's
• A linear-time algorithm for solving continuous maximin knapsack problems

Cites work

• A Decomposition Method for Interval Linear Programming
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• An algorithm for indefinite integer quadratic programming
• Flows in Arborescences

Cited in

(15)

• An efficient algorithm for solving a special class of LP's
• A strictly improving linear programming Phase I algorithm
• An algorithm for solving mathematical programming problems
• Un algorithme pour la résolution du programme linéaire général
• scientific article; zbMATH DE number 4211802 (Why is no real title available?)
• On the solution of special generalized upper-bounded problems: The LP/GUB knapsack problem and the λ-form separable convex objective function problem
• scientific article; zbMATH DE number 3987051 (Why is no real title available?)
• scientific article; zbMATH DE number 4068606 (Why is no real title available?)
• ALPO: Another Linear Program Optimizer
• scientific article; zbMATH DE number 1131737 (Why is no real title available?)
• The construction of a solution of the alternative linear programming problem
• Near-Regular Structure Discovery Using Linear Programming
• scientific article; zbMATH DE number 5182668 (Why is no real title available?)
• A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints
• An O(n log n)-algorithm for solving a special class of linear programs

This page was built for publication: An algorithm for solving a structured class of linear programming problems

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