The bound improving sequence algorithm

DOI10.1016/0167-6377(85)90047-1MaRDI QIDQ1061001zbMATH OpenOpenAlexFDO

Authors Paulo Barcia

Publication date 1985

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

Full work available at URL https://doi.org/10.1016/0167-6377(85)90047-1

zbMATH Keywords

Computational experienceduality gapknapsack problemLagrangean relaxationsequence of bounds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Boolean programming (90C09) Integer programming (90C10)

Review text

The purpose of this paper is to report on a new tool to help solve 0-1 LP's. It consists of a sequence of bounds that, under proper conditions, bridge the duality gap, i.e., converges in a finite number of steps to the optimal value of the objective function of the problem studied. As a by-product an optimal solution for that problem is produced. Computational experience is reported.

Recommendations

• A revised bound improvement sequence algorithm
• The bounded simplex method to solve the 0-1 linear integer programming problem
• Constructive dual methods for discrete programming
• scientific article; zbMATH DE number 4199965
• scientific article; zbMATH DE number 1069803

Cites work

• A bound-improving approach to discrete programming problems
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• scientific article; zbMATH DE number 3748742 (Why is no real title available?)

Cited in

(8)

• Constructive dual methods for discrete programming
• A revised bound improvement sequence algorithm
• A survey of algorithms for the generalized assignment problem
• A bound-improving approach to discrete programming problems
• The multidimensional 0-1 knapsack problem: an overview.
• The bounded simplex method to solve the 0-1 linear integer programming problem
• Data dependent worst case bound improving techniques in zero-one programming
• Improved Lagrangean decomposition: An application to the generalized assignment problem

This page was built for publication: The bound improving sequence algorithm

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